Cod sursa(job #3311818)

Utilizator mihai.25Calin Mihai mihai.25 Data 24 septembrie 2025 14:15:52
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

#include <vector>

#include <deque>

#include <climits>

using namespace std;

ifstream fin ("branza.in");

ofstream fout ("branza.out");

struct saptamana {

	long long C, P;
};

int main () {

	long long N, S, T;

	fin >> N >> S >> T;

	vector<saptamana> v (N + 1);

	for (int i = 1; i <= N; ++i)
		fin >> v[i].C >> v[i].P;

	long long cost_total = 0;

	deque<int> dq;

	for (int i = 1; i <= N; ++i) {

		while (!dq.empty() && dq.front() < i - T)
			dq.pop_front();
		
		long long cost_curent = v[i].C * v[i].P, cost_anterior = LLONG_MAX;

		if (!dq.empty()) {

			int j = dq.front();

			cost_anterior = (v[j].C + (i - j) * S) * v[i].P;
		}

		cost_total += min (cost_curent, cost_anterior);

		while (!dq.empty()) {

			int j = dq.back();

			if (cost_anterior>= cost_curent)
				dq.pop_back();
			else
				break;
		}

		dq.push_back(i);
	}

	fout << cost_total;

	return 0;
}