# PBinfo #2728 – Skyline – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int S[40005], D[40005], v[40005];
long long sum[40005], maxarea;
int main()
{
    ifstream fin("skyline.in");
    ofstream fout("skyline.out");
    int n, vf, stiva[40005], i;
    fin >> n;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        fin >> vf;
        sum[i] = sum[i-1] + vf;
    }
    vf = 0; stiva[vf] = n + 1;
    for(i = n; i >= 1; --i) {
        while(vf > 0 && v[i] <= v[stiva[vf]]) --vf;
        D[i] = stiva[vf];
        stiva[++vf] = i;
    }
    vf = 0; stiva[vf] = 0;
    for(i = 0; i <= n; ++i) {
        while(vf > 0 && v[i] <= v[stiva[vf]]) --vf;
        S[i] = stiva[vf];
        stiva[++vf] = i;
    }
    for(i = 1; i <= n; ++i)
        maxarea = max(maxarea, v[i] * (sum[D[i] - 1] - sum[S[i]]));
    fout << maxarea;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2728)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2728/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2728/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)