Cod sursa(job #68632)

Utilizator peanutzAndrei Homorodean peanutz Data 28 iunie 2007 18:57:55
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define NMAX 100000

typedef struct deque
{
	long long e;
	int poz;
};
deque d[NMAX+5];

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

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

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

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

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

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

		aux = min(aux, d[st].e - s*(n-i));

		res += aux*p[i];
		aux += s*(n-i);

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