Cod sursa(job #300845)

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

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

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

void dreapta(long long 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()
{
	long long a;
	scanf("%lld%lld%lld",&n,&s,&t);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld%lld",&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);
}