Cod sursa(job #79194)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 21 august 2007 10:11:33
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
# include <stdio.h>

const long int MAXN=400000;
long int n,v[MAXN+1],sm,pim,pfm,count;
struct {long int pos,sum;} deq[MAXN+1];

void citire()
{
FILE *f=fopen("buline.in","r");
fscanf(f,"%ld",&n);
long int i,aa;
for (i=1;i<=n;i++)
	{
	fscanf(f,"%ld%ld",&v[i],&aa);
	if (!aa) v[i]*=-1;
	v[n+i]=v[i];
	}
fclose(f);
}

void scrie()
{
FILE *g=fopen("buline.out","w");
fprintf(g,"%ld %ld %ld\n",sm,pim,pfm);
fcloseall();
}

void calculeaza()
{
sm=v[1];pim=1;pfm=1;count=1;
long int i;
long int prim=0,ultim=0;
deq[0].sum=0;deq[0].pos=0;
for (i=2;i<=2*n-1;i++)
	{
	v[i]+=v[i-1];
	//bagam in deq cel mai nou elem
	++ultim;
	deq[ultim].pos=i-1;
	deq[ultim].sum=v[i-1];
	//scufundam in deq, dar nu si pentur egal
	while (ultim>prim&&deq[ultim].sum<deq[ultim-1].sum)
		{
		ultim--;
		deq[ultim].pos=deq[ultim+1].pos;
		deq[ultim].sum=deq[ultim+1].sum;
		}
	//verificam solutia
	if (sm<v[i]-deq[prim].sum)
		{
		sm=v[i]-deq[prim].sum;
		pim=deq[prim].pos+1;
		pfm=i-deq[prim].pos;
		}
	//scoatem din deq tot ce se poate
	while (i+1-deq[prim].pos>n&&prim<=ultim) prim++;
	}
}

int main()
{
citire();
calculeaza();
scrie();
return 0;
}