Cod sursa(job #67644)

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

#define FIN "branza.in"
#define FOUT "branza.out"
#define MAX 100004
#define tip numar
#define tip_cifra short
#define CIFRE 25

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

class numar {
	public:
		tip_cifra a[CIFRE];
		
		void operator=(long long x) {
			long old = a[0]; a[0] = 0;
			while ( x ) { 
				a[++a[0]] = x%10;
				x/=10;
			}
			while ( old>a[0] )
				a[old--]=0;
		}
		void operator+=(numar x) {
			long i,t=0;
			for (i=1; i<=a[0] || i<=x.a[0] || t; ++i, t/=10)
				a[i] = (t = (a[i]+=t+x.a[i])) % 10;
			a[0] = i-1;
		}
		void operator+=(long long x) {
			numar b;
			b = x;
			*this += b;
		}
		bool operator<(numar x) {
			if ( a[0]<x.a[0] )
				return true;
			if ( a[0]>x.a[0] )
				return false;
			// a[0] == x.a[0]
			long i=a[0];
			while (i && a[i] == x.a[i])
				--i;
			return (a[i]<x.a[i]);
		}
};

tip A[MAX], nou;

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]  = (long long)P[i] * C[i];
		A[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  = (long long) S*dep ;
			nou += (long long) C[i]*qty;
			nou +=  A[j+1];
			if ( nou<A[i] ) 
				A[i] = nou;
			else
				break;
		}
	}
	
	freopen(FOUT, "w", stdout);
	for (i=A[0].a[0]; i; --i)
		printf("%d", A[0].a[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}