Cod sursa(job #222412)

Utilizator swift90Ionut Bogdanescu swift90 Data 22 noiembrie 2008 12:45:25
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<stdlib.h>
#define maxn 400100
long long nr[maxn];
int main(){
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	long long n,i,aux,pmin=0,pmax=0,p,u,max,s,suma=0;
	scanf("%lld",&n);
	
	for(i=0;i<n;++i){
		scanf("%lld%lld",&nr[i],&aux);
		if(aux==1)
			nr[i]=nr[i]*(-1);
		suma+=nr[i];
	}
	for(i=n;i<2*n-1;++i)
		nr[i]=nr[i-n];
	s=0;
	p=u=0;
	max=-1000000;
	for(i=0;i<2*n-2;++i){
		s+=nr[i];
		++u;
		if(u-p==n+1){
			if(nr[i]>nr[i-n]){
				++p;
				s-=nr[i-n];
			}
		}
		if(max<s){
			max=s;
			pmin=p;
			pmax=u;
		}
		if(s<0 || (u-p>n)){
			s=0;
			p=i+1;
			u=i+1;
		}
	}
	long long l;
	l=n-pmax+pmin;
	pmin=pmax%n;
	printf("%lld %lld %lld\n",abs(suma-max),pmin+1,l);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}