Cod sursa(job #257186)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 12 februarie 2009 21:33:12
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#define N 200001
int n,i,s,ok,s1,s2,l1,l2,S,P,L,a[N],b[N],c[N],d[N],e[N],f[N],g[N];
void readd(),prelucrari(),solve();
int main()
{
	readd();
	prelucrari();
	
	solve();
	return 0;
}
void readd()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	for(i=1;i<=n;i++)   
    {   
        scanf("%d%d",&a[i],&s);   
        if(!s)a[i]=-a[i];   
        else if(a[i])ok=1;   
    }   

}
void prelucrari()
{
	for(i=1;i<=n;i++)b[i]=b[i-1]+a[i];
	for(i=n;i>=1;i--)c[i]=c[i+1]+a[i];
	d[1]=b[1];e[1]=1;
	for(i=2;i<=n;i++)
	{
		d[i]=d[i-1];e[i]=e[i-1];
		if(b[i]>d[i]){d[i]=b[i];e[i]=i;}
	}
	f[n]=c[n];g[n]=n;
	for(i=n-1;i>=1;i--)
	{
		f[i]=f[i+1];g[i]=g[i+1];
		if(c[i]<=f[i]){f[i]=c[i];g[i]=i;}
	}
}
void solve()
{
	if(!ok)
	{
		P=1;L=1;S=a[1];   
        for(i=2;i<=n;i++)
			if(a[i]>S){P=i;S=a[i];}
		printf("%d %d %d\n",S,P,L);
		return;
    } 
	for(i=1;i<=n;i++)
	{
		s1=c[i]+d[i-1];
		l1=n-i+1+e[i-1];
		s2=c[i];
		l2=n-i+1;
		if(s2>=s1){s1=s2;l1=l2;}
		s2=c[i]-f[i];
		l2=g[i+1]-i+1;
		if(s2>=s1){s1=s2;l1=l2;}
		if(s1>S){S=s1;P=i;L=l1;}
	}
	printf("%d %d %d",S,P,L);
}