Cod sursa(job #238707)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 2 ianuarie 2009 23:27:58
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<stdio.h>
#define NMAX 200000

int main(){
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
int n,n2,v[2*NMAX+1],i,smax,s[2*NMAX+1],t[2*NMAX+1],p,l,tip,x,st,max,sc;
scanf("%d",&n); n2=2*n;
for(i=1;i<=n;++i){
	scanf("%d%d",&x,&tip);
	if(tip) v[i]=x;
	else v[i]=-x;
	v[i+n]=v[i];
	}
s[0]=t[0]=0;max=-10000;
for(i=1;i<=n2;++i) {
	s[i]=s[i-1]+v[i];
	if(max<s[i]) max=s[i];
	if(max>s[i]) t[i]=max;
	else t[i]=s[i];
	}
smax=-10000;
p=1;l=n;
for(i=1;i<=n2;++i){
	sc=s[n]+t[i]-s[i];
	if(smax<sc) smax=sc;
	}
printf("%d %d %d",smax,p,l);
return 0;
}