Editing 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 <code>skyline.in</code> va conține numărul <code>n</code> de segmente orizontale din linie. Pe următoarele <code>n</code> linii vor fi trecute perechi de numere <code>h l</code>, reprezentând înălțimea și lungimea fiecărui segment.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 40.000</code>;
* <code>0 ≤ h ≤ 2.000.000.000</code>;
* <code>1 ≤ l ≤ 50.000</code>;
* Dreptunghiul maximal are laturile verticale şi orizontale.

= Exemplu: =
<code>skyline.in</code>
 7
 4 3
 11 6
 8 2
 9 4
 2 2
 4 9
 8 9
<code>skyline.out</code>
 96

=== Explicație ===
Cel mai mare dreptunghi care se poate înscrie începe la coordonatele <code>(3, 0)</code> şi are laturile de lungime <code>12</code> şi <code>8</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
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()


</syntaxhighlight>