Cod sursa(job #113239)

Utilizator swift90Ionut Bogdanescu swift90 Data 9 decembrie 2007 12:44:09
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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);
	int n,s,t,i,inc,sf,cost,cant;
	int pr,ul,mij;
	
	scanf("%d%d%d",&n,&s,&t);
	scanf("%d%d",&cost,&cant);
	suma=cant*cost;
	inc=sf=0;
	nr[0].pret=cost;
	nr[0].poz=0;
	for(i=1;i<n;++i){
		scanf("%d%d",&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;
}