Cod sursa(job #501264)

Utilizator cat_red20Vasile Ioana cat_red20 Data 14 noiembrie 2010 17:31:20
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
FILE *fin,*fout;
int q[400001],s[400001],i,n,p,u,max,poz,l,a[200001],semn;
int main(){
fin=fopen("buline.in","r");
fout=fopen("buline.out","w");
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++){
	fscanf(fin,"%d %d",&a[i],&semn);
	if(!semn){
		a[i]=-a[i];
	}
	s[i]=s[i-1]+a[i];
}
for(i=n+1;i<=2*n+1;i++){
s[i]=s[i-1]+a[i-n];

}
p=u=1;
for(i=1;i<=2*n;i++){
	while(i-q[p]>n && p<u){
		p++;
	}
	if(s[i]-s[q[p]]>max){
		max=s[i]-s[q[p]];
		poz=q[p]+1;
		l=i-q[p];
	}
	while(s[i]<=s[q[u]] && u>=p){
		u--;
	}
	u++;
	q[u]=i;
}
fprintf(fout,"%d %d %d",max,poz,l);
return 0;}