Cod sursa(job #329964)

Utilizator freak93Adrian Budau freak93 Data 8 iulie 2009 11:58:07
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#define maxn 400002

using namespace std;

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

int a[maxn],i,j,deque[maxn],n,s[maxn],p,q,x,y,tmax;

void add(int x)
{
    while(q>=p&&s[deque[q]]>=s[x])
        --q;

    deque[++q]=x;
}

void calib(int x)
{
    while(deque[p]<=x)
        ++p;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>a[i]>>j;
        if(!j)
            a[i]=-a[i];
        a[n+i]=a[i];
    }
    n*=2;
    s[1]=a[1];
    for(i=2;i<=n;++i)
        s[i]=s[i-1]+a[i];

    p=1;
    q=1;

    x=1;
    y=1;
    tmax=-0x3f3f3f3f;
    for(i=1;i<n;++i)
    {
        if(s[i]-s[deque[p]]>tmax)
            tmax=s[i]-s[deque[p]],x=deque[p]+1,y=i;
        add(i);
        if(i>(n>>1))
            calib(i-(n>>1));
    }

    g<<tmax<<" "<<x<<" "<<y-x+1<<"\n";
    f.close();
    g.close();

    return 0;
}