Cod sursa(job #2130666)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 13 februarie 2018 20:09:03
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<stdio.h>
FILE*fin,*fout;
long int i,j,n,s[200001],x[200001],max,p,u,d[200001],inc,l,tip;
int main(){
fin=fopen("buline.in","r");
fout=fopen("buline.out","w");
fscanf(fin,"%ld",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%ld %ld",&x[i],&tip);
if(tip==0){x[i]=-x[i];}
s[i]=s[i-1]+x[i];

}

for(i=n+1;i<=2*n;i++){

s[i]=s[i-1]+x[i%n];
if(i==2*n){s[i]=s[i-1]+x[n];}

}
p=u=1;
max=-10001;
for(i=1;i<=2*n;i++){
while(i-d[p]>n&&p<u){p++;}
if(s[i]-s[d[p]]>max){max=s[i]-s[d[p]];inc=d[p]+1;
l=i-inc;}

while(s[i]<=s[d[u]]&&u>=p){u--;}
u++;
d[u]=i;
}
fprintf(fout,"%ld %ld %ld",max,inc,l+1);

return 0;}