Pagini recente » Cod sursa (job #1371402) | Cod sursa (job #3333179) | Cod sursa (job #244929) | Cod sursa (job #82775) | Cod sursa (job #3303692)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
vector<int> getSlidingMins(vector<int> &arr, int k) {
deque<int> minime;
vector<int> raspunsuri(arr);
int ans(0), n(arr.size());
for (int i = 0; i < n; ++i) {
while (minime.size() && arr[minime.back()] >= arr[i])
minime.pop_back();
if (minime.size() && minime.front() <= i - k) // pasul magic care face diferenta intre stiva si acest deque
minime.pop_front();
minime.push_back(i);
raspunsuri[i] = minime.front();
}
return raspunsuri;
}
int main() {
ifstream fin("branza.in");
ofstream fout("branza.out");
int n, costDepozitare, durataMaxima;
fin >> n >> costDepozitare >> durataMaxima;
vector<int> costuri(n), cantitati(n);
for (int i = 0; i < n; ++i)
fin >> costuri[i] >> cantitati[i];
// adaptam costurile la o forma consistenta
for (int i = 0; i < n; ++i)
costuri[i] -= i * costDepozitare;
vector<int> minimeSecvente = getSlidingMins(costuri, durataMaxima);
vector<int> costMinimSecventa(n);
for (int i = 0; i < n; ++i)
costMinimSecventa[i] = costuri[minimeSecvente[i]] + i * costDepozitare; // adaugam inapoi pentru a avea forma ceruta
long long ans(0);
for (int i = 0; i < n; ++i)
ans += costMinimSecventa[i] * cantitati[i];
fout << ans;
return 0;
}