Cod sursa(job #68824)

Utilizator gigi_becaliGigi Becali gigi_becali Data 29 iunie 2007 16:07:58
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define NMAX 100000
#define ull  long long
typedef struct deque
{
    ull poz;
	ull e;
};
deque d[NMAX+5];

template <class T> T min(T a, T b){ if(a<b) return a; return b;}

//inline long long min(long long a, long long b) { return (a < b) ? a : b; }

ull st, dr;
ull c[NMAX+5], p[NMAX+5];
ull n, t, s;
ull res;

int main()
{
	ull i;
	ull aux;
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);

	st = 1;
	dr = 1;
	scanf("%lld %lld %lld", &n, &s, &t);
	scanf("%lld %lld", c+1, p+1);
	res += (ull)c[1]*p[1];
	d[1].poz = 1;
	d[1].e = (ull)c[1] + s*(n-1);

	for(i = 2; i <= n; ++i)
	{
		scanf("%lld %lld", c+i, p+i);
		aux = c[i];

	//	if(d[st].poz <= i-t)
			while(d[st].poz<i-t)++st;

		aux = min(aux, (ull)d[st].e - (ull)s*(n-i));
	//aux=c[i];
		res += (ull)aux*p[i];
		aux += (ull)s*(n-i);

		while(dr >= st && d[dr].e > aux) --dr;
		d[++dr].poz = (ull)i;
		d[dr].e = (ull)aux;
	}
	printf("%lld\n", res);
	return 0;
}