Cod sursa(job #973367)

Utilizator cont_de_testeCont Teste cont_de_teste Data 14 iulie 2013 13:28:54
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
//---------------------------------------------------------

#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>

using namespace std;

//---------------------------------------------------------

const int NMax = 100100;
long long N, S, T, solution;
long long C[NMax], P[NMax];

void read(), solve(), write();

//---------------------------------------------------------

int main() {
	#ifdef INFOARENA
		freopen("branza.in", "r", stdin);
		freopen("branza.out", "w", stdout);
	#endif
	read(); solve(); write();
}

//---------------------------------------------------------

void read() {
	cin >> N >> S >> T;
	for (int i = 1; i <= N; i++)
		cin >> C[i] >> P[i];
}

//---------------------------------------------------------

struct minDeque {
	deque<int> D;
	inline void add(int position) {
		for (; D.size() && C[D.back()] > C[position]; D.pop_back());
		D.push_back(position);
	}
	inline void erase(int position) {
		if (D.front() == position)
			D.pop_front();
	}
	inline long long takeMin() {
		return C[D.front()];
	}
	inline int takeMinPosition() {
		return D.front();
	}
} DQ;

void solve() {
	C[0] = 1LL << 60;
	for (int i = N; i >= 1; i--)
		C[i] = C[i] + (N - i) * S;
	for (int i = N; i >= N - T + 1; i--)
		DQ.add(i);
	
	for (int i = N; i >= 1; i--) {
		int position = DQ.takeMinPosition();
		solution += P[i] * (C[position] - S * (N - position) + S * (i - position));
		DQ.add(max(i - T, 0LL));
		DQ.erase(i);
	}
}

//---------------------------------------------------------

void write() {
	cout << solution << '\n';
}

//---------------------------------------------------------