Cod sursa(job #519902)

Utilizator alexamiu2008Miu Alexandra alexamiu2008 Data 6 ianuarie 2011 20:58:46
Problema Buline Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 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];

}
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;}