Cod sursa(job #3170781)

Utilizator cosmin983Pascale Cosmin cosmin983 Data 18 noiembrie 2023 09:52:23
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <deque>


using namespace std;


ifstream cin("branza.in");
ofstream cout("branza.out");


const int NMAX = 1e5;
#define int long long

pair <int, int> a[NMAX];
long long answer;
int n, s, t;


void read() {
	cin >> n >> s >> t;
	for (int index = 0; index < n; ++index) {
		cin >> a[index].first >> a[index].second;
	}
}


void solve() {
	deque <int> dq;


	for (int index = 0; index < n; ++index) {
		while (dq.empty() == false && a[index].first < a[dq.back()].first + s * (index - dq.back())) {
			dq.pop_back();
		}
		dq.push_back(index);
		if (index - t > dq.front()) {
			dq.pop_front();
		}
		answer += (a[dq.front()].first + s * (index - dq.front())) * a[index].second;
	}
}


void display() {
	cout << answer;
}


signed main() {
	read();
	solve();
	display();
	return 0;
}