Cod sursa(job #113248)

Utilizator znakeuJurba Andrei znakeu Data 9 decembrie 2007 13:02:23
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
struct gaina
{
	long long n,p;
};

gaina v[100001];
gaina w[100001];
long long n,s,t;
long long gf,gs;

FILE *in=fopen("branza.in","r");
FILE *out=fopen("branza.out","w");

int main()
{
	long long i,x,y,tf,ts;
	long long sfff=0;
	fscanf(in,"%lld%lld%lld",&n,&s,&t);
	
	fscanf(in,"%lld%lld",&x,&y);
	v[0].n=x;
	v[0].p=1;
	w[0].n=x;
	w[0].p=y;
	gf=0;
	gs=0;
	
	for (i=1; i<n; i++)
	{
		fscanf(in,"%lld%lld",&x,&y);
		if (i+1-v[gs].p>t)
			gs++;
		if (gs<=gf)
		{
			ts=gs;
			tf=gf;
			while (ts!=tf)
			{
				if (x>= v[(ts+tf+1)/2].n+s*(i+1-v[(ts+tf+1)/2].p))
					ts=(ts+tf+1)/2;
				else
					tf=(ts+tf+1)/2;
			}
			if (x>v[ts].n+s*(i+1-v[ts].p))
			{
				gf=tf+1;
				v[gf].n=x;
				v[gf].p=i+1;				
			}
			else
			{
				gs=ts;
				v[gs].n=x;
				v[gs].p=i+1;
				gf=gs;
			}
		}
		else
		{
			gs=0;
			gf=0;
			v[0].n=x;
			v[0].p=i+1;
		}
		w[i].n=v[gs].n+s*(i+1-v[gs].p);
		w[i].p=y;
	}
	for (i=0; i<n; i++)
		sfff+=w[i].n*w[i].p;
	
	fprintf(out,"%lld\n",&sfff);
	
	fclose(in);
	fclose(out);
	
	return 0;
}