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

skyline.out

Explicație

Cel mai mare dreptunghi care se poate înscrie începe la coordonatele (3, 0) şi are laturile de lungime 12 şi 8.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Skyline:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2728 Skyline

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2728 Skyline de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2728 Skyline