Cod sursa(job #2852136)

Utilizator Radu_marioRadu Mario Radu_mario Data 19 februarie 2022 11:39:19
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream file_in("branza.in");
ofstream file_out("branza.out");

int i, c[100005], p[100005];

int main()
{
	int N, S, T;
	long long MIN = 0;
	file_in >> N >> S >> T;
	deque<int> DEQ;

	for (i = 0; i < N; ++i)
	{
		file_in >> c[i] >> p[i];

		while (!DEQ.empty() && c[i] <= c[DEQ.back()] + S * (i - DEQ.back()))
			DEQ.pop_back();

		while (!DEQ.empty() && (i - DEQ.front()) > T)
			DEQ.pop_front();

		DEQ.push_back(i);
		MIN = MIN + c[DEQ.front()] * p[i] + p[i] * (i - DEQ.front()) * S;
	}

	file_out << MIN;
	return 0;
}