Cod sursa(job #214972)

Utilizator zlatebogdanZlate Bogdan zlatebogdan Data 17 octombrie 2008 09:20:43
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>  
#define N 400070
#define inf -1500000000  
int v[N],lung,n,p,x,u,smax=-2000000000,k,i;  
void citire()  
{  
    int i,x;  
    scanf("%d",&n);    
    for (i=1;i<=n;++i)  
    {	  
		scanf("%d%d",&v[i],&x);  
		v[i+n]=v[i];
		if (x==0){ 
			v[i]=-v[i];  
			v[i+n]=v[i];
		}
	}  
}  

void suma()  
{  
	int sc=0;
	int poz=1, nrp=1;;
	for(int i=1;i<=2*n;++i){
		sc=sc+v[i];
		nrp++;
		if (sc>smax){
			smax=sc;
			p=poz;
			u=i;
		}
		if ((sc<=0)||(nrp>n)){
			sc=0;
			poz=i+1;
			nrp=0;
		}
	}
}
	/*	t[1]=0;  
		nr[1]=0;  
		for (i=1;i<=n;i++){  
			sum[i]=v[i]+sum[i-1];  
			if (t[i-1]>s[i-1]){  
				nr[i]=nr[i-1];  
				t[i]=t[i-1];
			}  
			else{  
				nr[i]=i-1;  
				t[i]=s[i-1];  
			}  
		}  
		smax=inf;  
		for (i=1;i<=n;++i){  
			sc=t[i]+sum[n]-sum[n-i];  
			if (t[i]+sum[n]-sum[i-1]>smax){  
				smax=sc;  
				p=i;  
				lung=n-i+1+nr[i];  
			}
	}  
     
	}*/
     
void calcul()  
{  
	suma();  
     
	printf("%d %d %d\n",smax , p, u-p+1);  
}  
    
int main()  
{  
	freopen("buline.in","r",stdin);  
	freopen("buline.out","w",stdout);  
	citire();  
	calcul();  
	return 0;  
}