Cod sursa(job #3130477)

Utilizator JellyTheOctopusKyle Liang JellyTheOctopus Data 17 mai 2023 20:52:29
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N, T;
long long S;

int main() {
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	cin >> N >> S >> T;
	vector<long long> C(N+1), P(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> C[i] >> P[i];
	}
	deque<int> d;
	long long ans = 0;
	for (int i = 1; i <= N; i++) {
		d.push_back(i);
		while (i-d.front() > T) {
			d.pop_front();
		}
		while(C[d.front()]+S*(long long)(i-d.front()) > C[i]) {
			d.pop_front();
		}
		ans += P[i]*(C[d.front()]+S*(long long)(i-d.front()));
	}
	cout << ans << "\n";
}