Cod sursa(job #68815)

Utilizator peanutzAndrei Homorodean peanutz Data 29 iunie 2007 16:03:23
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define NMAX 100000

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

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

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

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

	st = 1;
	dr = 0;
	scanf("%lld %lld %lld", &n, &s, &t);
	for(i = 1; i <= n; ++i)
	{
		scanf("%ld%ld", c+i, p+i);

	while(st <= dr && (long long)d[dr].e > (long long)c[i] + (long long)s*(n-i))
		 --dr;
	d[++dr].poz = i;
	d[dr].e = (long long)c[i] + (long long)s*(n-i);

	res += (long long)((long long)d[st].e - (long long)s*(n-i)) * p[i];

	if(i-t == d[st].poz)
	       ++st;
	}
	printf("%lld\n", res);
	return 0;
}