Cod sursa(job #222414)

Utilizator swift90Ionut Bogdanescu swift90 Data 22 noiembrie 2008 13:16:05
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
long long nr[400100],sum[400100];
struct xx{
	long long v,p;
}t[400100];
int main(){
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	long long n,i,a,b,maxim,pmin,lung,s;
	scanf("%lld",&n);
	t[0].v=-1000000;
	for(i=1;i<=n;++i){
		scanf("%lld%lld",&a,&b);
		if(b)
			nr[i]=nr[n+i]=a;
		else
			nr[i]=nr[n+i]=-a;
	}
	t[0].p=1;
	for(i=1;i<=n<<1;++i){
		sum[i]=sum[i-1]+nr[i];
		if(t[i-1].v>sum[i]){
			t[i].v=t[i-1].v;
			t[i].p=t[i-1].p;
		}
		else{
			t[i].v=sum[i];
			t[i].p=i;
		}
	}
	t[0].v=0;
	maxim=-10000000;
	pmin=lung=0;
	for(i=1;i<2*n;++i){
		s=t[i-1].v-sum[i-1]+sum[n];
		if(maxim<s){
			maxim=s;
			pmin=i;
			lung=n+t[i-1].p-i+1;
		}
	}
	if(pmin>n)
		pmin-=n;
	printf("%lld %lld %lld\n",maxim,pmin,lung);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}