Cod sursa(job #1712757)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 3 iunie 2016 17:10:27
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#define MAXN 200000
int v[2*MAXN+1],deq[2*MAXN+1];
long long sp[2*MAXN+1];
int main(){
    FILE*fi,*fout;
    int i,n,poz1,lung,x,b,e;
    long long max;
    fi=fopen("buline.in" ,"r");
    fout=fopen("buline.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=1;i<=n;i++){
       fscanf(fi,"%d%d" ,&v[i],&x);
       if(x==0)
        v[i]=-v[i];
       sp[i]=sp[i-1]+v[i];
    }
    for(i=n+1;i<=2*n;i++)
        sp[i]=sp[i-1]+v[i-n];
    b=e=0;
    max=0;
    for(i=1;i<=2*n;i++){
        if(i-deq[b]>n)
           b++;
        while(e>=b&&sp[deq[e]]>=sp[i])
             e--;
        deq[++e]=i;
        if(max<sp[i]-sp[deq[b]]){
            max=sp[i]-sp[deq[b]];
            poz1=deq[b]+1;
            lung=i-poz1+1;
        }
    }
    fprintf(fout,"%lld %d %d" ,max,poz1,lung);
    fclose(fi);
    fclose(fout);
    return 0;
}