Cod sursa(job #989409)

Utilizator thewildnathNathan Wildenberg thewildnath Data 25 august 2013 16:38:59
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include<deque>
using namespace std;

deque <int> d;
long long v[400005];

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int n,i,c,m,s,l;
    long long sol=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%lld %d",&v[i],&c);
        if(c==0)
            v[i]=-v[i];
        v[i]+=v[i-1];
    }
    m=2*n;
    for(i=1;i<n;++i)
        v[i+n]=v[i+n-1]+v[i]-v[i-1];
    for(i=1;i<m;++i)
    {
        if(!d.empty()&&i-d.front()==n)
            d.pop_front();
        while(!d.empty()&&v[d.back()]>v[i])
            d.pop_back();
        d.push_back(i);
        if(v[i]-v[d.front()]>sol)
        {
            sol=v[i]-v[d.front()];
            s=d.front()+1;
            l=i-s+1;
        }
    }
    printf("%lld %d %d\n",sol,s,l);
    return 0;
}