Cod sursa(job #300833)

Utilizator ooctavTuchila Octavian ooctav Data 7 aprilie 2009 18:34:05
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>

int n,s,t;
int cost[100001];
int dq[100001];
long long cos=0,nr;
int st=1;

void stanga(int i)
{
	if(dq[st]+t<=dq[i])
		st++;
	
}

void dreapta(int i)
{
	while(nr && cost[dq[nr]] + (i-dq[nr]) * s >= cost[i] )//cat timp dq nu e vid si ultimul e mai scump decat i
		--nr;
}

void citire()
{
	int a;
	scanf("%d%d%d",&n,&s,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&cost[i],&a);
		stanga(i);//scoate elem din stanga daca e prea indepartat (branza mai veche de t sapt)
		dreapta(i);//scoate din dreapta branza mai scumpa
		dq[++nr]=i;
		cos=cos+(long long)(cost[dq[st]]+(i-dq[st])*s)*a;
	}
}
int main()
{
	freopen("branza.in","r",stdin);
	freopen("branza.out","w",stdout);
	citire();

	printf("%lld\n",cos);
}