Cod sursa(job #113242)

Utilizator swift90Ionut Bogdanescu swift90 Data 9 decembrie 2007 12:46:19
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
struct coada{
	int pret,poz;
};
coada nr[100010];
long long suma;
int main(){
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	long long n,s,t,i,inc,sf,cost,cant;
	long long pr,ul,mij;
	
	scanf("%lld%lld%lld",&n,&s,&t);
	scanf("%lld%lld",&cost,&cant);
	suma=cant*cost;
	inc=sf=0;
	nr[0].pret=cost;
	nr[0].poz=0;
	for(i=1;i<n;++i){
		scanf("%lld%lld",&cost,&cant);
		if(nr[inc].poz+t<i)
			++inc;
		pr=inc;
		ul=sf;
		while(pr!=ul){
			mij=(pr+ul)>>1;
			if(nr[mij].pret+(i-nr[mij].poz)*s>cost)
				ul=mij;
			else
				pr=mij+1;
		}
		if(nr[pr].pret+(i-nr[pr].poz)*s<cost)
			++pr;
		nr[pr].pret=cost;
		nr[pr].poz=i;
		sf=pr;
		suma+=cant*(nr[inc].pret+s*(i-nr[inc].poz));
	}
	
	printf("%lld\n",suma);
	fclose(stdin);
	fclose(stdout);
	return 0;
}