Cod sursa(job #431827)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 1 aprilie 2010 14:17:37
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
using namespace std;
FILE *f=fopen("buline.in","r");
FILE *g=fopen("buline.out","w");
int semn[2]={-1,1};
int n,i,s[400001],a[200001],x,p,u,d[400001],maxim,max_poz,max_l;
int main(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
	fscanf(f,"%d",&a[i]);
	fscanf(f,"%d",&x);
	a[i]*=semn[x];
	s[i]=s[i-1]+a[i];	
}
for(i=1;i<=n;i++)
  s[i+n]=s[i+n-1]+a[i];	
u=1;
p=1;
d[p]=0;
for(i=1;i<=2*n;i++){
	while( i-d[p] > n && p<=u )
		   p++;
	if(p<=u){
	   if(s[i]-s[d[p]] > maxim ){
           maxim=s[i]-s[d[p]];
           max_poz=d[p]+1;
           max_l=i-d[p];
	   }		   
	}
	while( s[d[u]] >= s[i] && u>=p )
		    u--;
	d[++u]=i;	
}
fprintf(g,"%d %d %d",maxim,max_poz,max_l);
return 0;
}