Skyline

#include <fstream>
#define N 40001
using namespace std;

int main()
{
    int n;
    ifstream f("skyline.in");
    f>>n;
    int H[N],L;
    long long sum[N];
    for(int i=1;i<=n;++i)
    {
        f>>H[i];
        f>>L;
        sum[i]=sum[i-1]+L;
    }
    f.close();
    int ST[N],D[N];
    ST[0]=n+1;
    int vf=0;
    for(int i=n;i>=1;--i)
    {
        while(vf>0&&H[i]<=H[ST[vf]])
            --vf;
        D[i]=ST[vf];
        ST[++vf]=i;
    }
    ST[0]=0;
    vf=0;
    int S[N];
    for(int i=0;i<=n;++i)
    {
        while(vf>0&&H[i]<=H[ST[vf]])
            --vf;
        S[i]=ST[vf];
        ST[++vf]=i;
    }
    long long MAX=0;
    for(int i=1;i<=n;++i)
        MAX=max(MAX,H[i]*(sum[D[i]-1]-sum[S[i]]));
    ofstream g("skyline.out");
    g<<MAX;
    g.close();
}