Помогите решить задачу "Прямоугольники"

Question

Дана последовательность 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)

Answer 1

function maxArea(rs) {
  var a = 0;
  for (var i = 0; i < rs.length; i++) {
    var r = rs[i];
    var ai = r[0] * r[1] + back(r[1], i) + forward(r[1], i);
    a = Math.max(a, ai);
  }
  return a;
  
  function back(h, idx) {
    var a = 0;
    for (var j = idx - 1; j >= 0; j--) {
      if (rs[j][1] >= h)
        a += rs[j][0] * h;
      else
        break;
    }
    return a;
  }
  function forward(h, idx) {
    var a = 0;
    for (var j = idx + 1; j < rs.length; j++) {
      if (rs[j][1] >= h)
        a += rs[j][0] * h;
      else
        break;
    }
    return a;
  }
}

var rs1 = [[4, 3], [2, 1], [2, 5]];
var rs2 = [[4, 3], [2, 1], [3, 5]];

console.log(maxArea(rs1));
console.log(maxArea(rs2));

Answer 2

"Перевел" код Igor на Python:

def maxArea(rs):
    a = 0
    for i in range(len(rs)):
        r = rs[i]
        ai = r[0] * r[1] + back(rs, r[1], i) + forward(rs, r[1], i)
        a = max(a, ai)
    return a

def back(rs, h, idx):
    a = 0
    for j in range(idx-1, -1, -1):
        if rs[j][0] >= h:
            a += rs[j][0] * h
        else:
            break
    return a

def forward(rs, h, idx):
    a = 0
    for j in range(idx+1, len(rs)):
      if rs[j][1] >= h:
        a += rs[j][0] * h
      else:
        break
    return a

rs1 = [[4, 3], [2, 1], [2, 5]]
rs2 = [[4, 3], [2, 1], [3, 5]]

print(maxArea(rs1))
print(maxArea(rs2))

БЛОГ НА HUSL

Помогите решить задачу "Прямоугольники"

Ответы (2 шт):