Cod sursa(job #68375)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 iunie 2007 18:25:06
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

#define FIN "branza.in"
#define FOUT "branza.out"
#define MAX 100020
#define tip_cifra char
#define CIFRE 20

long C[MAX], P[MAX];
long n, S, T;

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


long A[MAX];
numar Sum;

class deque {
	public:
		pair<long,long> V[MAX];
		long p, u;
		
		long next(long &x) {
			x++;
			if ( x==MAX ) 
				x = 0;
			return x;
		}
		long prev(long &x) {
			x--;
			if ( x<0 )
				x = MAX-1;
			return x;
		}
		
		deque() {
			p = u = 0;
		}
		void push(long x, long y) {
			pair<long,long> tmp = make_pair(x,y);
			if ( p==u && !p && !V[0].first ) {
				V[0] = tmp;
				return ;
			}
			if ( x<V[p].first ) 
				V[prev(p)] = tmp;
			else {
				while ( x < V[u].first ) 
					prev(u);
				V[next(u)] = tmp;
			}
			
		}
		void update(long i) {
			if ( !i ) 
				return ;
			while ( i-V[p].second>T )
				next(p);
		}
		pair <long,long> pop() {
			return V[p];
		}
		void debug() {
			long i;
			fprintf(stderr, "---------------------------\n");
			for (i=p; i!=u; next(i))
				fprintf(stderr, "%ld %ld\n", V[i].first, V[i].second);
			fprintf(stderr, "%ld %ld\n", V[i].first, V[i].second);
		}
} D;


int main() {
	long i;
	
	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=0; i<n; ++i) {
		D.update(i);
		D.push(C[i]+(n-i)*S, i);
//		D.debug();
		
		A[i] = D.pop().first - (n-i)*S;
	}
	

	for (i=0; i<n; ++i) {
		Sum += A[i]*P[i];
	}
	
	freopen(FOUT, "w", stdout);
	for (i=Sum.nr; i; --i)
		printf("%d", Sum.a[i]);
	printf("\n");
/*	for (i=0; i<n; ++i)
		printf("%ld\n", A[i]);*/
	fclose(stdout);
	return 0;
}