Cod sursa(job #1524812)

Utilizator MarghescuGabriel Marghescu Marghescu Data 14 noiembrie 2015 14:25:52
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include<deque>
#define nmax 400010
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
deque<int>d;
int s,p,l,n;
int v[nmax],sum[nmax];
int main()
{
    int i,x,y;
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>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];
    s=-10000;
    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 (s<sum[i]-sum[d.front()])
        {
            s=sum[i]-sum[d.front()];
            p=d.front()+1;
            l=i-d.front();
        }
    }
    g<<s<<" "<<p<<" "<<l;
    return 0;
}