Cod sursa(job #3127099)

Utilizator johnutddDobrin Ionut johnutdd Data 7 mai 2023 12:08:56
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <iostream>
#include <vector>
#include <deque>

using std::cin;
using std::cout;
using std::deque;
using std::vector;

int main()
{
	int n, s, t;
	cin >> n >> s >> t;
	deque<int> deq;
	vector<int> cost(2 * n + 1);
	vector<int> pret(2 * n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> pret[i] >> cost[i];
		while (!deq.empty() && i - deq.front() > t)
		{
			deq.pop_front();
		}
		while (!deq.empty() && (pret[deq.back()] + s * (i - deq.back())) > pret[i])
		{
			deq.pop_back();
		}
		deq.push_back(i);
		pret[deq.front()] += cost[i];
	}
	cout << pret[deq.front()];
	return 0;
}