Cod sursa(job #2640449)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 6 august 2020 14:51:00
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");


int N, S, T;

long long sol;

vector<int> C, P;
deque<int> DQ;

auto costStoc = [](int curr, int prev) -> long long {
	return 1LL * C[prev] + 1LL * S * (curr - prev);
};

int main()
{
	f >> N >> S >> T;
	for (int i = 0; i < N; i++) {
		int c, p;
		f >> c >> p;
		C.push_back(c);
		P.push_back(p);
		
		while (!DQ.empty() && i - DQ.front() > T) DQ.pop_front();

		while (!DQ.empty() && costStoc(i, DQ.back()) > 1LL * C[i]) DQ.pop_back();
		DQ.push_back(i);


		sol += P[i] * costStoc(i, DQ.front());

	}

	g << sol << "\n";
	return 0;
}