Дана последовательность 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
Ограничения
Время выполнения: 5 секунд
Помогите, пожалуйста. У меня есть код без учёта разной ширины столбцов, пыталась сделать это через префиксные суммы, но у меня совсем не получается.
def push(stack, elem):
stack.append(elem)
return elem
def top(stack):
return stack[-1]
def pop(stack):
return stack.pop()
def size(stack):
return len(stack)
def power(a, n):
if n == 0:
return 1
elif n % 2 == 0:
return power(a * a, n // 2)
else:
return power(a, n - 1) * a
inf = 2 * power(10, 9) + 1
n = int(input())
wide = []
a = []
for i in range(n):
ww, aa = map(int, input().split())
wide.append(ww)
a.append(aa)
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = p[i - 1] + wide[i -1]
h = [-inf] + a + [-inf]
ans = [[0, 0] for i in range(n + 2)]
stack = []
push(stack, 0)
for i in range(1, n + 2):
curr = h[i]
while h[top(stack)] > curr:
ans[pop(stack)][1] = i
push(stack, i)
stack = []
push(stack, 0)
for i in range(n + 1, 0, -1):
curr = h[i]
while h[top(stack)] > curr:
ans[pop(stack)][0] = i
push(stack, i)
m = -inf
b = 0
for i in range(1, n + 1):
S = h[i] * (p[i] - p[i] - 1)
b = 0
m = max(m, S)
print(m)