Cod sursa(job #238725)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 3 ianuarie 2009 00:05:25
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#define NMAX 200000

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