Cod sursa(job #203983)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 21 august 2008 11:42:54
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#define N 100005
int c[N],p=1,n,t;
long long s;
struct ab{
	long long a,b;
};
ab v[N];
int caut(long long x,int k){
	int st=p,dr=c[0],m;
	while(st<dr){
		m=(st+dr)>>1;
		if(v[c[m]].a+(k-c[m])*s>=x) dr=m;
		else st=m+1;
	}
	if(v[c[st]].a+(k-c[st])*s<x) st++;
	return st;
}
int main(){
	int i,z;
	long long total=0;
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%lld%d",&n,&s,&t);
	for(i=1;i<=n;i++)
		scanf("%lld%lld",&v[i].a,&v[i].b);
	c[1]=c[0]=1;
	total=v[1].a*v[1].b;
	/*for(i=2;i<=min;i++){
		z=caut(v[i].a,i);
		c[0]=z;c[z]=i;
		total+=v[i].b*(v[c[p]].a+(i-c[p])*s);
		
	}*/
	for(i=2;i<=n;i++){
		if(i-t>c[p]) p++;
		z=caut(v[i].a,i);
		c[z]=i;c[0]=z;
		total+=v[i].b*(v[c[p]].a+(i-c[p])*s);
	}
	printf("%lld\n",total);
}