Cod sursa(job #210022)

Utilizator tvladTataranu Vlad tvlad Data 26 septembrie 2008 08:21:52
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <cstdio>
#include <deque>
using namespace std;

int n,s,t,c,r;

int main() {
	freopen("branza.in","rt",stdin);
	freopen("branza.out","wt",stdout);
	scanf("%d %d %d",&n,&s,&t);
	deque< pair<int,int> > d;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d %d",&c,&r);
		if (!d.empty() && d.front().second == i-t) d.pop_front();
		for (; !d.empty() && d.back().first + (i-d.back().second)*s > c; d.pop_back());
		d.push_back(make_pair(c,i));
		sum += r * (d.front().first + (i-d.front().second) * s);
	}
	printf("%d\n",sum);
	return 0;
}