2728 - Skyline

Uitându-ne din New Jersey către New York, Manhattan, departe, în zare, se văd zgârie norii. De la distanță, nu distingem clădirile, ci numai o linie formată din segmente orizontale și verticale, așa numita skyline.

Cerința

Determinați care este aria celui mai mare dreptunghi care se poate înscrie în skyline.

Date de intrare

Prima linie a fișierului skyline.in va conține numărul n de segmente orizontale din linie. Pe următoarele n linii vor fi trecute perechi de numere h l, reprezentând înălțimea și lungimea fiecărui segment.

Date de ieșire

Fișierul de ieșire skyline.out va conține un singur număr, aria celui mai mare dreptunghi conținut în skyine.

Restricții și precizări

• 1 ≤ n ≤ 40.000;
• 0 ≤ h ≤ 2.000.000.000;
• 1 ≤ l ≤ 50.000;
• Dreptunghiul maximal are laturile verticale şi orizontale.

Exemplu:

skyline.in

7
4 3
11 6
8 2
9 4
2 2
4 9
8 9

skyline.out

96

Explicație

Cel mai mare dreptunghi care se poate înscrie începe la coordonatele (3, 0) şi are laturile de lungime 12 şi 8.

Încărcare soluție

Lipește codul aici

import sys

def main():
    sys.stdin = open('skyline.in', 'r')
    sys.stdout = open('skyline.out', 'w')

    S = [0] * 40005
    D = [0] * 40005
    v = [0] * 40005
    sum = [0] * 40005
    maxarea = 0

    n = int(input())
    for i in range(1, n + 1):
        v[i], vf = map(int, input().split())
        sum[i] = sum[i-1] + vf

    vf = 0
    stiva = [0] * 40005
    stiva[vf] = n + 1
    for i in range(n, 0, -1):
        while vf > 0 and v[i] <= v[stiva[vf]]:
            vf -= 1
        D[i] = stiva[vf]
        vf += 1
        stiva[vf] = i

    vf = 0
    stiva = [0] * 40005
    stiva[vf] = 0
    for i in range(n + 1):
        while vf > 0 and v[i] <= v[stiva[vf]]:
            vf -= 1
        S[i] = stiva[vf]
        vf += 1
        stiva[vf] = i

    for i in range(1, n + 1):
        maxarea = max(maxarea, v[i] * (sum[D[i] - 1] - sum[S[i]]))

    print(maxarea)

if __name__ == "__main__":
    main()