Cod sursa(job #1702911)

Utilizator Bodo171Bogdan Pop Bodo171 Data 15 mai 2016 19:50:56
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include<fstream>
#include<deque>
using namespace std;
deque<int> d;
int sum[400005],i,n,x,summax,p,l;
bool semn;
int main()
{
    ifstream f("buline.in");
    ofstream g("buline.out");
    f>>n;
    for(i=1;i<=n;i++)
    {f>>x>>semn;
    if(semn)sum[i]=sum[i-1]+x;
    else sum[i]=sum[i-1]-x;
    }
    for(i=1;i<=n;i++)
    {
        sum[n+i]=sum[i]+sum[n];
    }
    for(i=1;i<=2*n;i++)
    {
        if(!d.empty()&&i-d.front()>=n) d.pop_front();
        while(!d.empty()&&sum[i]<sum[d.back()])
            d.pop_back();
        d.push_back(i);
        if(sum[i]>summax&&i<=n) {summax=sum[i];l=i;p=1;}
        if(sum[i]-sum[d.front()]>summax)
        {summax=sum[i]-sum[d.front()];p=d.front()+1;l=i-d.front();}
    }
    g<<summax<<' '<<p<<' '<<l;
    return 0;
}