Cod sursa(job #67508)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 25 iunie 2007 10:45:08
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 0.67 kb
#include <cstdio>

#define FIN "branza.in"
#define FOUT "branza.out"
#define MAX 100004
#define tip long long

long C[MAX], P[MAX];
long n, S, T;
long i,j, dep,qty, nou;

tip A[MAX];

int main() {
	freopen(FIN, "r", stdin);
	scanf("%ld %ld %ld", &n, &S, &T);
	for (i=0; i<n; ++i)
		scanf("%ld %ld", C+i, P+i);
	fclose(stdin);

	for (i=n-1; i>=0; --i) {
		A[i] = P[i] * C[i] + A[i+1];
		dep = 0; qty = P[i];
		for (j=i+1; j<n && j-i<=T; ++j) {
			dep += (j-i)*P[j];
			qty += P[j];
			nou = S*dep + C[i]*qty + A[j+1];
			if ( nou<A[i] ) 
				A[i] = nou;
		}
	}
	
	freopen(FOUT, "w", stdout);
	printf("%lld\n", A[0]);
	fclose(stdout);
	return 0;
}