Pagini recente » Cod sursa (job #2253141) | Cod sursa (job #1863689) | Cod sursa (job #2179434) | Cod sursa (job #2745256) | Cod sursa (job #2889177)
#include <string.h>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int main ()
{
long long n, s, t;
long long sapt[1000001];
deque <long long> dq;
long long suma = 0;
fin >> n >> s >> t; // Citesc nr de saptamani, suma pentru stocarea unui kg de braza,
for(int i = 0; i < n; i++)
{
long long q;
fin >> sapt[i] >> q;
while(!dq.empty() && dq.front() < i - t)
dq.pop_front();
/*
* Este mai eficient sa luam branza din saptamana curenta daca este mai bine decat pretul per
* un kg din saptamanile precedente + cate saptamani ar trebui sa depozitez branza aceea * pretul per sapt
*/
while(!dq.empty() && sapt[i] < ((i - dq.back()) * s + sapt[dq.back()]))
dq.pop_back();
// Adaugam ziua curenta
dq.push_back(i);
suma = suma + q * (sapt[dq.front()] + (i - dq.front()) * s);
}
fout << suma;
return 0;
}