Найти площадь максимального прямоугольника, который можно вырезать из фигуры

@NichTo · Регистрация: 10.07.2020

Студворк — интернет-сервис помощи студентам

Прямоугольники
Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0,0), вправо на оси OX вплотную друг за другом. Требуется найти M — площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N (1≤N≤105). Далее идут N строк. В каждой строке содержатся два числа: ширина и высота i-го прямоугольника (1<wi≤3⋅104, 0≤hi≤3⋅104).

Формат выходных данных

Выведите искомое число M.
3
4 3
2 1
2 5 12

3
4 3
2 1
3 5 15

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stack>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int* a = new int[n];
 
    stack <int> stack;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
    
        if (!stack.empty() && stack.top() < a*b)
        {
            stack.pop();
        }
        
        stack.push(a * b);
    }
    cout << stack.top();
}

@NichTo · 12.07.2020, 12:53 **[ТС]**

К сожалению, программа не всегда работает корректно:

3
4 3
2 1
3 5

Выдает: 17

@SmallEvil · 12.07.2020, 13:27

мой косяк, исправил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(t_rect_iter i = rects.begin(); i!=rects.end(); i++)
    {
        Mtmp = i->S;
        for (t_rect_iter j = i+1 ; j!=rects.end(); j++)
        {
 
            if (j->height < i->height)
            break;
            Mtmp = Mtmp + j->S;
        }
 
        if (Mtmp>M)
            M=Mtmp;
    }

@zayats80888 · 12.07.2020, 13:30

Сообщение от dmitrii2000

Пишет неверный формат вывода

Если ты про мой вариант, то попробуй заменить все double на unsigned long long

@SmallEvil · 12.07.2020, 13:34

щас дотестирую, сорри

Новые блоги и статьи Все статьи Все блоги /
Главный вопрос моделирования сукцессии anaschu 27.06.2026 главный вопрос. Если эктомикориза лучше добывает недоступный фосфор. И ее масса максимальна из всех. А широколиственный лес тоже имеет самую крутую биомассу. То почему не возникло их симбиоза? Это. . .	сукцессия 6. Питон реализация энилоджиковской модели, картинка про Центральную часть будущей модели anaschu 26.06.2026 Етить. ИИ мне на основе моего старого файла R создал вот эту вот хмерь на пайтоне. Это уже новая модель, модель сукцессии грибной. потоки фосфора, азота. Углерода. 5 видов организмов. Я даже. . .	Как замкнутый ядерный цикл решит проблему недостатки фосфора? Био миграция фосфора со дна океана anaschu 26.06.2026 Биологический лифт: Концепция подъема фосфора со дна океана с помощью ЗЯТЦ Предлагаю на обсуждение альтернативу тяжелому промышленному бурению океанического дна. Вместо сложной инженерии мы можем. . .	сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .
сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .	сукцессия 3 anaschu 25.06.2026 Примерный план работ по модели	сукцессия 2 anaschu 25.06.2026 параметризировочная калибровочная таблица будущей модели	Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал (мат мет мод 29) anaschu 23.06.2026 Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал Материалы для обсуждения с МГСУ · 2026 Рисунки внутри приложенного ворд файла. Что за. . .

@NichTo 0 / 0 / 0 Регистрация: 10.07.2020 Сообщений: 11
	12.07.2020, 12:53 [ТС]
	К сожалению, программа не всегда работает корректно: 3 4 3 2 1 3 5 Выдает: 17 0

@SmallEvil 4086 / 2975 / 813 Регистрация: 29.06.2020 Сообщений: 11,000
	12.07.2020, 13:34
	щас дотестирую, сорри 0