Cod sursa(job #341248)

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