Cod sursa(job #215749)

Utilizator hadesgamesTache Alexandru hadesgames Data 20 octombrie 2008 20:21:33
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>  
#define N 400070
#define inf -1500000000  
int v[N],lung,n,p,t[N],sum[N],nr[N],smax=inf;  
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 init()  
{  

	t[1]=0;  
	nr[1]=0;  
	for (int i=1;i<=n;i++){  
		sum[i]=v[i]+sum[i-1];  
		if (t[i-1]>sum[i-1]){  
			nr[i]=nr[i-1];  
			t[i]=t[i-1];
		}  
		else{  
			nr[i]=i-1;  
			t[i]=sum[i-1];  
		}  
	}
}
void suma1()
{
	int sc=0;  
	for (int i=1;i<=n;++i){  
		sc=t[i]+sum[n]-sum[i-1];  
		if (t[i]+sum[n]-sum[i-1]>smax){  
			smax=sc;  
			p=i;  
			lung=n-i+1+nr[i];  
		}
	}
}
void suma2()
{
	int sc=0,pp=1;
	for (int i=1;i<=n;++i)
	{
		sc=sc+v[i];
		if (sc>smax){
			smax=sc;
			p=pp;
			lung=i-p+1;
		}
		if (sc<=0){
			sc=0;
			pp=i+1;
		}
	}
}
void calcul()  
{
	init();
	suma1();
	suma2();
	printf("%d %d %d\n",smax , p, lung);  
}  
int main()  
{  
	freopen("buline.in","r",stdin);  
	freopen("buline.out","w",stdout);  
	citire();  
	calcul();  
	return 0;  
}