Pagini recente » Cod sursa (job #1964485) | Cod sursa (job #1402601) | Cod sursa (job #1867634) | Cod sursa (job #2375411) | Cod sursa (job #2888516)
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int main()
{
int n, s, t;
long long cost_minim = 0;
vector <int> cost_branza;
cost_branza.push_back(0);
deque <int> saptamani;
fin >> n >> s >> t;
for(int saptamana = 1; saptamana <= n; saptamana ++)
{
long long cost, kg;
fin >> cost >> kg;
cost_branza.push_back(cost);
while(!saptamani.empty() && saptamani.front() < saptamana - t)
saptamani.pop_front();
while(!saptamani.empty() && cost_branza[saptamana] < cost_branza[saptamani.back()] + s * (saptamana-saptamani.back()))
saptamani.pop_back();
saptamani.push_back(saptamana);
cost_minim += kg * (cost_branza[saptamani.front()] + s * (saptamana - saptamani.front()));
}
fout << cost_minim;
return 0;
}