Cod sursa(job #2716409)

Utilizator Titus_Teodor_PirsanTitus-Teodor Pirsan Titus_Teodor_Pirsan Data 5 martie 2021 10:03:00
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb

#include <fstream>
#include <deque>

using namespace std;

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

typedef long long ll;

deque<int> dq;
int n, s, t, p;
ll ans;

int main()
{
	cin >> n >> s >> t;
	int* c = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> c[i] >> p;
		if (!dq.empty() && dq.front() == i - t)
		{
			dq.pop_front();
		}
		while (!dq.empty() && c[dq.back()] + (i - dq.back()) * s > c[i])
		{
			dq.pop_back();
		}
		dq.push_back(i);
		ans += (ll)((c[dq.front()] + (i - dq.front()) * s) * p);
	}
	cout << ans;
	cin.close();
	cout.close();
	return 0;
}