Cod sursa(job #67555)

Utilizator gcosminGheorghe Cosmin gcosmin Data 25 iunie 2007 11:31:04
Problema Branza Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.63 kb
#include <stdio.h>

#define NMAX 100010
#define LL long long

int N, S, T;

int c[NMAX];

int deck[NMAX];
int poz[NMAX];


int main()
{
	int i, nr, cur;

	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);

	scanf("%d %d %d", &N, &S, &T);

	LL cost = 0;

	LL off = 0;

	int p, q;
	p = 0, q = -1;
	
	for (i = 1; i <= N; i++, off += S) {
		scanf("%d %d", &c[i], &nr);
		
		while (p <= q && poz[p] < i - T) p++;

		cur = c[i] - off;
		
		while (p <= q && deck[q] > cur) q--;
		q++;
		deck[q] = cur;
		poz[q] = i;

		cost += (LL) nr * (deck[p] + off);
	}

	printf("%lld\n", cost);

fclose(stdin);
fclose(stdout);
return 0;
}