Cod sursa(job #1525528)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 15 noiembrie 2015 10:45:10
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

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


int n,x,bilet[400010],suma[400010],deque[400010];
bool culoare;

int main()
{
    int i,st,dr,max,pornire=0,lungime=0;
    max=-int(2e9);
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>x>>culoare;
        if(culoare==0) x=x*(-1);
        bilet[i]=bilet[i+n]=x;
        suma[i]=suma[i-1]+bilet[i];
    }
    for(i=n+1;i<=2*n;i++) suma[i]=suma[i-1]+bilet[i];

    st=1;
    dr=0;

    for(i=1;i<=2*n;i++)
    {
        while(suma[i]<=suma[deque[dr]] && st<=dr) dr--;
        dr++;
        deque[dr]=i;
        if(deque[st]==i-n) st++;
        if(max<suma[i]-suma[deque[st]])
        {
            max=suma[i]-suma[deque[st]];
            pornire=deque[st]+1;
            lungime=i-deque[st];
        }
    }
    out<<max<<" "<<pornire<<" "<<lungime;
    in.close();
    out.close();
    return 0;
}