Fişierul intrare/ieşire: | skyline.in, skyline.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 8192 kbytes |
Scorul tău | N/A | Dificultate |
Skyline (clasa a 7-a)
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ţă
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 vom avea 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 skyline.
Restricţii
- 1 ≤ n ≤ 40000
- 0 ≤ h ≤ 2000000000
- 1 ≤ l ≤ 50000
- Dreptunghiul maximal are laturile verticale şi orizontale
Exemplu
skyline.in | skyline.out | Explicaţie |
---|---|---|
7 4 3 11 6 8 2 9 4 2 2 4 9 8 9 | 96 | Cel mai mare dreptunghi care se poate înscrie începe la coordonatele (3, 0) şi are laturile de 12 şi 8. |