Raul: Pagină nouă: 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ăt...

2023-12-21T15:55:18Z

Pagină nouă: 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ăt...

New page

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>

2728 - Skyline - Revision history