Cod sursa(job #3231152)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 24 mai 2024 23:41:45
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("branza.in", "r", stdin);
	freopen("branza.out", "w", stdout);
	int n, s, t;
	cin >> n >> s >> t;
	vector<vector<int>> v(n, vector<int>(2));
	for(int i = 0;i < n;++i)
		cin >> v[i][0] >> v[i][1];
	uint64_t ans = 0;
	
	deque<int> q;
	for(int i = 0;i < n;++i)
	{
		if(!q.empty() && i - q.front() > t)
			q.pop_front();
		while(!q.empty() && v[i][0] < (i - q.back()) * s + v[q.back()][0])
			q.pop_back();
		q.push_back(i);
		ans += (v[q.front()][0] + (i - q.front()) * s) * (uint64_t) v[i][1];
	}
	cout << ans << "\n";
}