Cod sursa(job #203985)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 21 august 2008 12:04:40
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#define N 100007
struct branz{
	long long a,b;
};
branz v[N];
long long s,z=0;
inline long long val(int k,int l){
	return v[k].a+(l-k)*s;
}

int p,u;
int c[N];
int bynary(int k,int p,int u){
	long long y=val(k,k);
	while(p!=u)
		if(y<=val(c[(p+u)/2],k))
			u=(p+u)/2;
		else
			p=(p+u)/2+1;
	if(val(c[p],k)>=y)
		return p;
	return p+1;
}
int main(){
	int i,q,t,n;
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%d%lld%d",&n,&s,&t);
	p=u=0;
	scanf("%lld%lld",&v[1].a,&v[1].b);
	c[u]=1;
	z=val(1,1);
	for(i=2;i<=n;++i){
		scanf("%lld%lld",&v[i].a,&v[i].b);
		if(c[p]-i>=t)
			++p;
		q=bynary(i,p,u);
		u=q;
		c[q]=i;
		z+=val(c[p],i)*v[i].b;
	}
	printf("%lld\n",z);
	return 0;
}