Pagini recente » Cod sursa (job #19164) | Cod sursa (job #1416561) | Cod sursa (job #1899933) | Cod sursa (job #430754) | Cod sursa (job #2939210)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
#define DIM 100000
#define LL long long
int n;
LL s, t, cost[DIM + 1], kg[DIM + 1];
deque <int> DQ;
//DQ.front() retin cel mai bun pret pentru a putea produce un kg de branza;
//Deci elimin atat timp cat: cost[i] * kg[i] <= cost[DQ.back()] * kg[i] + (i - DQ.back()) * s * kg[i]; | :kg[i]
//cost[i] <= cost[DQ.back()] + (i - DQ.back()) * s;
int main() {
fin >> n >> s >> t;
LL total = 0;
for(int i = 1; i <= n; i++) {
fin >> cost[i] >> kg[i];
while(!DQ.empty() && cost[i] <= cost[DQ.back()] + (i - DQ.back()) * s)
DQ.pop_back();
DQ.push_back(i);
if(i - DQ.front() == t + 1) //daca o tin de mai mult de t zile;
DQ.pop_front();
total += cost[DQ.front()] * kg[i] + (i - DQ.front()) * s * kg[i];
}
fout << total;
return 0;
}