Cod sursa(job #130631)

Utilizator razvi9Jurca Razvan razvi9 Data 1 februarie 2008 16:36:39
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<cstdio>
int n,a[200001],i,x,y,s[200001][2],j,smax,pmax,lmax,s2,l;
int main()
{freopen("buline.in","r",stdin);
 freopen("buline.out","w",stdout);
 scanf("%d",&n);
 for(i=1;i<=n;i++){
	 scanf("%d %d",&x,&y);
	 a[i]=y?x:-x;}
 s[1][0]=a[1];s[1][1]=1;
 for(i=2;i<=n;i++){
	 if(s[i-1][0]+a[i]>a[i]) s[i][0]=s[i-1][0]+a[i],s[i][1]=s[i-1][1]+1;
	 else s[i][0]=a[i],s[i][1]=1;}
 smax=s[1][0]-1;
 for(i=1;i<=n;i++)
	 if(s[i][0]>smax) smax=s[i][0],pmax=i-s[i][1]+1,lmax=s[i][1];
 s2=s[n][0];
 if(s2>0)
	 for(i=1;i<n-s[n][1];i++){
		 s2=s2+a[i];
		 if(s2<=0) break;
		 if(s2>smax) {smax=s2;pmax=n-s[n][1]+1;lmax=s[n][1]+i;}}
 if(s[n][0]+s[j][0]>smax) smax=s[n][0]+s[j][0],pmax=n-s[n][1]+1,lmax=s[n][1]+j;
 printf("%d %d %d\n",smax,pmax,lmax);
 fclose(stdout);
 return 0;}