Cod sursa(job #1324883)

Utilizator gapdanPopescu George gapdan Data 22 ianuarie 2015 21:25:46
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<cstdio>
#include<deque>
#define NMAX 200005
using namespace std;
deque<int>d;
int x,y,smax,l,p,i,n;
int v[NMAX],sum[NMAX];
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for  (i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        if (y==0) v[i]=v[i+n]=(-1)*x;
            else v[i]=v[i+n]=x;
        sum[i]=sum[i-1]+v[i];
    }
    for (i=n+1;i<=2*n;++i)
        sum[i]=sum[i-1]+v[i];
    smax=-10001;
    for (i=1;i<=2*n;++i)
    {
        while(!d.empty() && sum[i]<=sum[d.back()])
            d.pop_back();
        d.push_back(i);
        if (d.front()==i-n) d.pop_front();
        if (smax<sum[i]-sum[d.front()])
        {
            smax=sum[i]-sum[d.front()];
            if (i>n) {p=d.front()+1; l=i-d.front();}
                else {p=d.front()+1; l=d.front()-i;}

        }
    }
    printf("%d %d %d\n",smax,p,l);
    return 0;
}