Cod sursa(job #165908)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 martie 2008 09:03:58
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#define N 444111
int sum,n,max,sb,lb,s,e,l;
struct buline{
	int a,b;
};
buline v[N];
void dublam()
{
	for(int i=1;i<=n;++i)
		v[i+n]=v[i];
}	
void scan()
{
	freopen("buline.in", "r",stdin);
	freopen("buline.out", "w",stdout);
	scanf("%d", &n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d", &v[i].a,&v[i].b);
		if(!v[i].b)
			v[i].b=-1;
	}
}
void solve()
{
	dublam();
	sum=0; s=1;
	for(int i=1;i<n*2;++i)
	{
		e=i;  
        if(sum<0)  
        {  
            sum=0;  
            s=i;  
            if(s>n)  
                s=1;  
        }  
        sum+=v[i].a*v[i].b;  
        l=e-s+1;  
        if(l>n)  
        {sum-=v[s].a*v[s].b; ++s;}    
        if(sum>max)  
        {  
            max=sum;  
            sb=s;  
            lb=l;  
        }  
	}	
	printf("%d %d %d\n",max,sb,lb);
}
int main()
{
	scan();
	solve();
	return 0;
}