Cod sursa(job #1729227)

Utilizator liviu23Liviu Andrei liviu23 Data 14 iulie 2016 14:23:15
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <deque>
#include <fstream>
#define DIM 200005
#define ll long long
using namespace std;

deque<int> d;
int n,c[DIM];
ll s[2*DIM];

int main()
{
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    fin>>n;
    int color;
    for(int i=1;i<=n;i++) {
        fin>>c[i]>>color;
        if(!color)
            c[i]*=-1;
        s[i]=c[i]+s[i-1];
    }
    for(int i=1;i<=n;i++)
        s[i+n]=s[i+n-1]+c[i];
    int left=0,l=1,p=1;
    ll maxim=s[1];
    for(int i=1;i<=2*n;i++) {
        while(!d.empty()&&s[i]<=s[d.back()])
            d.pop_back();
        d.push_back(i);
        if(d.front()==i-n)
            d.pop_front();
        if(maxim<s[i]-s[d.front()]) {
            maxim=s[i]-s[d.front()];
            p=d.front()+1;
            l=i-d.front();
        }
    }
    fout<<maxim<<" "<<p<<" "<<l;
    return 0;
}