Cod sursa(job #113284)

Utilizator hadesgamesTache Alexandru hadesgames Data 9 decembrie 2007 15:49:15
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
struct ceva
{
	long long p,v;
};
ceva a[100001];
long long s;
long long cauta(long long x,long long p,long long u,long long y)
{
	long long m,aux;
	while (p<u)
	{
		m=(p+u)/2;
		aux=a[m].v + s*(y-a[m].p);
		if (x<=aux)
			u=m;
		else
			p=m+1;
	}
	if (a[p].v+s*(y-a[p].p)<x)
		return p+1;
	return p;
	
}
int main ()
{
	FILE *in,*out;
	long long cost=0,p,u,n,i,t,x,c;
	in=fopen("branza.in","r");
	out=fopen("branza.out","w");
	fscanf(in,"%lld%lld%lld",&n,&s,&t);
	fscanf(in,"%lld%lld",&x,&c);
	p=1;
	u=1;
	a[1].v=x;
	a[1].p=1;
	for (i=2;i<=n;i++)
	{
		fscanf(in,"%lld%lld",&x,&c);
		if (i-a[p].p>t)
			p++;
		t=cauta(x,p,u,i);
		a[t].v=x;
		a[t].p=i;
		cost+=a[p].v*c;
		u=t;
	}
	fprintf(out,"%lld\n",cost);
	fclose(in);
	fclose(out);
	return 0;
	
}