Cod sursa(job #2673156)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 15 noiembrie 2020 22:57:06
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>
#include <deque>
#define ll long long
#define pi std::pair<ll, ll>

std::deque<pi>dq;
ll n, s, t, k, c, ans;

int main() {
	std::ifstream fin("branza.in");
	std::ofstream fout("branza.out");
	fin >> n >> s >> t;
	for (int i = 1; i <= n; i++) {
		fin >> c >> k;
		if (!dq.empty() and dq.front().second < i - t) dq.pop_front();
		while (!dq.empty() and dq.back().first + (i - dq.back().second) * s >= c) dq.pop_back();
		dq.push_back({ c, i });
		ans += k * (dq.front().first + (i - dq.front().second) * s);
	}
	fout << ans;
}