Cod sursa(job #1801045)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 8 noiembrie 2016 16:28:09
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <stack>
#define nmax 40010

using namespace std;

ifstream fin("skyline.in");
ofstream fout("skyline.out");

int N, hist[nmax], B[nmax];

int main()
{
    fin>>N;
    for(int x, y, i=0; i<N; ++i)
    {
        fin>>hist[i]>>B[i];
    }

    stack <int> s;
    int max_area = 0;
    int tp;
    int area_with_top;
    int i = 0;
    while (i < N)
    {
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);
        else
        {
            tp = s.top();
            s.pop();
            area_with_top = hist[tp]*(s.empty() ? i : i-s.top()-1);
            area_with_top *= B[i];
            max_area = max(max_area, area_with_top);
        }
    }
    while (s.empty() == false)
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp]*(s.empty() ? i : i-s.top()-1);
        area_with_top *= B[i];
        max_area = max(max_area, area_with_top);
    }
    fout<<max_area*2<<'\n';
    return 0;
}