Cod sursa(job #111772)

Utilizator megabyteBarsan Paul megabyte Data 1 decembrie 2007 20:32:48
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#define INF "branza.in"
#define OUF "branza.out"
#define NMAX 100002
using namespace std;

struct sapt
{
	long long k,cost;
}a[NMAX];

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	long long i,n,s,t,p,q,id[NMAX];
	long long total,kg;
	fscanf(in,"%lld%lld%lld",&n,&s,&t);
	fscanf(in,"%lld%lld",&a[1].cost,&a[1].k);
	p=1;q=1;id[p]=1;
	total=a[1].k*a[1].cost;
	//printf("%lld %lld\n",a[1].k,a[p].cost);

	for(i=2;i<=n;++i)
	{
		fscanf(in,"%lld%lld",&a[i].cost,&a[i].k);
		if(i-id[p]>t) ++p;
		++q;
		while(q>p&&a[i].cost<(i-id[q-1])*s+a[id[q-1]].cost) --q;

		id[q]=i;

		kg=(i-id[p])*s+a[id[p]].cost;
		total+=a[i].k*kg;
		//printf("%lld %lld %lld\n",a[i].k,a[id[p]].cost,(i-id[p])*s);
	}

	fprintf(out,"%lld\n",total);
	fclose(in);fclose(out);
	return 0;
}