Cod sursa(job #214937)

Utilizator zlatebogdanZlate Bogdan zlatebogdan Data 16 octombrie 2008 22:39:37
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
   #include<stdio.h>  
   #define N 50070  
   #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;  
	}