Cod sursa(job #623055)

Utilizator andra23Laura Draghici andra23 Data 18 octombrie 2011 22:59:34
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<iostream>
#include<fstream>
#include<deque>

using namespace std;

const int MAXN = 100005;
int c[MAXN], p[MAXN];
deque <int> d;

int main() {
	ifstream f("branza.in");
	ofstream g("branza.out");

	int n, s, t;
	f >> n >> s >> t;

	long long cost = 0;
	for (int i = 1; i <= n; i++) {
		f >> c[i] >> p[i];
		
		while (!d.empty() && c[i] < (i - d.back())*s + c[d.back()]) {
			d.pop_back();
		}
		d.push_back(i);
		if (i - d.front() > t) {
			d.pop_front();
		}

		cost += (long long) p[i]*(c[d.front()] + s*(i-d.front())); 
	}

	g << cost << '\n';

	return 0;
}