Cod sursa(job #2561942)

Utilizator bogdan_gatiGati Bogdan Iulian Dumitru bogdan_gati Data 29 februarie 2020 11:14:10
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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


long long h[40005];
int l[40005];
int st[40005];
int dr[40005];
vector<int>s1;
vector<int>s2;
bool x;


int i,j,k,a,y,maximilian,aria;


int main()
{
    cin>>a;

    for (i=1;i<=a;i++){
        cin>>h[i]>>l[i];
}

    s1.push_back(h[1]);
    st[1]=l[1];
    for (i=2;i<=a;i++){
        st[i]=l[i];
        x=0;
         while (x==0){
            x=s1.empty();
            if (x==0){
                if (s1.back()>h[i]){
                st[i]+=st[s1.back()];
                s1.pop_back();

}}
        s1.push_back(h[i]);
}
    s2.push_back(h[a]);
    }
    dr[1]=l[a];


    for (i=a-1;i>=1;i--){
        dr[i]=l[i];
        x=0;
        while (x==0){
            x=s2.empty();
            if (x==0){
                if (s2.back()>h[i]){

                    dr[i]+=dr[s2.back()];
                    s2.pop_back();
}}}
        s2.push_back(h[i]);
}

    for (i=1;i<=a;i++){
        aria=(st[i]+dr[i]-l[i])*h[i];
        if (aria>maximilian){
            maximilian=aria;
}}
    cout<<maximilian;
    return 0;

}