Cod sursa(job #2716416)

Utilizator Titus_Teodor_PirsanTitus-Teodor Pirsan Titus_Teodor_Pirsan Data 5 martie 2021 10:12:23
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb

#include <fstream>
#include <deque>

using namespace std;

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

typedef long long ll;

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

int main()
{
	cin >> n >> s >> t;
	ll *c = new ll[n];
	for (ll 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 += p * (c[dq.front()] + (i - dq.front()) * s);
	}
	cout << ans;
	cin.close();
	cout.close();
	return 0;
}