Cod sursa(job #68785)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 29 iunie 2007 14:26:57
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <cstdio>
#define fin  "branza.in"
#define fout "branza.out"
#define Nmax 100001

struct nod { long long poz,val; };

int N,T,pr,vf;
nod v[Nmax];
long long ret,S;

int main() {
int i;
long long ct,qu;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%lld%d",&N,&S,&T);
	
	pr=1; vf=0; v[1].poz=1;

	for (i=1;i<=N;++i) {

		scanf("%lld%lld",&ct,&qu);
		
		if ( v[pr].poz < i-T ) 
			++pr;

		while ( qu* ( v[vf].val + (i - v[vf].poz )*S ) > ct * qu && vf >= pr)
			--vf;

		++vf;

		v[vf].poz=i; v[vf].val=ct;

		ret=ret+qu*(v[pr].val+(i-v[pr].poz)*S);
	
	}

	printf("%lld\n",ret);

	return 0;
}