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

<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>