Cod sursa(job #826302)

Utilizator Robert29FMI Tilica Robert Robert29 Data 30 noiembrie 2012 16:31:56
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<stdio.h>
FILE*f=fopen("branza.in","r");
FILE*g=fopen("branza.out","w");
long long N,S,T,d[100002],sol,p,u;
struct branza
{
	long long c,p;
}v[100002];
int main()
{
	fscanf(f,"%lld%lld%lld",&N,&S,&T);
	for(int i=1;i<=N;++i)
		fscanf(f,"%lld%lld",&v[i].c,&v[i].p);
	p=1;
	for(int i=1;i<=N;++i)
	{
		while(d[p]+T<i)
			++p;
		
		while(p<=u&&v[i].c<=(v[d[u]].c+(i-d[u])*S))
			--u;
		d[++u]=i;
		
		sol+=v[i].p*(v[d[p]].c+(i-d[p])*S);
	}
	
	fprintf(g,"%lld",sol);
	
	fclose(f);
	fclose(g);
	return 0;
}