Cod sursa(job #341256)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 17 august 2009 21:51:25
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<cstdio>
#define N 100001
long long v[N],x,n,t,s,d[N],u,p,total;
void citire()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	scanf("%lld%lld%lld",&n,&s,&t);
	++t;
	for (int i=1; i<=t; ++i)
	{
		scanf("%lld%lld",&v[i],&x);
		while(u!=p&v[i]<=v[d[u-1]]+s*(i-d[u-1]))
			--u;
		d[u++]=i;
		total+=x*(v[d[p]]+s*(i-d[p]));
		//printf("%d\n",x*(v[d[p]]+s*(i-d[p])));
	}
	for (int i=t+1; i<=n; ++i)
	{
		scanf("%lld%lld",&v[i],&x);
		int g=i-d[p];
		if (g==t)
			++p;
		while(u!=p&v[i]<=v[d[u-1]]+s*(i-d[u-1]))
			--u;
		d[u++]=i;
		total+=x*(v[d[p]]+s*(i-d[p]));
		//printf("%d\n",x*(v[d[p]]+s*(i-d[p])));
	}
	printf("%lld",total);
}
int main()
{
	citire();
	return 0;
}