Cod sursa(job #132216)

Utilizator swift90Ionut Bogdanescu swift90 Data 5 februarie 2008 13:23:32
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
#include<stdlib.h>
#define maxn 400100
int nr[maxn];
int main(){
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	int n,i,aux,pmin,pmax,p,u,max,s,suma=0;
	scanf("%d",&n);
	
	for(i=0;i<n;++i){
		scanf("%d%d",&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(max<s){
			max=s;
			pmin=p;
			pmax=u;
		}
		if(s<0 || (u-p>=n)){
			s=0;
			p=i+1;
			u=i+1;
		}
	}
	int l;
	l=n-pmax+pmin;
	pmin=pmax%n;
	printf("%d %d %d\n",abs(suma-max),pmin+1,l);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}