Cod sursa(job #2099886)

Utilizator luanastLuana Strimbeanu luanast Data 4 ianuarie 2018 19:52:18
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int n,i,x,sgn,v[400001],deq[400001],sum[400001],p,smax,minim,st,dr,l;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x>>sgn;
        if(!sgn)
            x*=-1;
        v[i]=x;
    }
    for(i=1;i<n;i++)
        v[n+i]=v[i];
    //sum = vector de sume partiale
    //suma partiala de i este suma tuturor elementelor cu nr de ord mai mic sau egal cu i
    //ca sa aflii suma dintre pozitiile a si b faci sp[a]-sp[b]
    //aici faci deque ca sa aflii s.p. maxima dintre oricare 2 elemente
    deq[++dr]=1;
    sum[1]=v[1];
    for(i=2;i<2*n;i++){
        sum[i]=v[i]+sum[i-1];
        minim=sum[deq[st]];
        if(sum[i]-minim>smax){
            smax=sum[i]-minim;
            p=deq[st]+1;
            l=i-p+1;
        }
        while(st<=dr && sum[i]<sum[deq[dr]])
            --dr;
        deq[++dr]=i;
        if(deq[st]<i-n+1)
            ++st;
    }
    fout<<smax<<" "<<p<<" "<<l;
    return 0;
}