Cod sursa(job #1076195)

Utilizator andreiiiiPopa Andrei andreiiii Data 9 ianuarie 2014 22:41:26
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

const int N=200005;

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

long long a[2*N];
int dqp[2*N];

int main()
{
    int n, i, st, dr, solx=N, soly=N;
    long long sol=-200000000000;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>st>>dr;
        if(dr) a[i]=st;
        else a[i]=-st;
        a[i]+=a[i-1];
    }
    for(i=n+1;i<=2*n;i++) a[i]=a[i-n]+a[i-1]-a[i-n-1];
    st=dr=1;
    for(i=1;i<=2*n;i++)
    {
        while(st<=dr&&i-dqp[st]>n) st++;
        if(a[i]-a[dqp[st]]>sol)
        {
            sol=a[i]-a[dqp[st]];
            soly=i-dqp[st];
            solx=dqp[st];;
        }
        else if(a[i]-a[dqp[st]]==sol&&dqp[st]<solx)
        {
            sol=a[i]-a[dqp[st]];
            soly=i-dqp[st];
            solx=dqp[st];
        }
        while(st<=dr&&a[i]<a[dqp[dr]]) dr--;
        dqp[++dr]=i;
    }
    fout<<sol<<" "<<solx+1<<" "<<soly;
    fin.close();
    fout.close();
}