Cod sursa(job #3303695)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 17 iulie 2025 12:45:53
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

vector<int> getSlidingMins(vector<int> &arr, int k) {
    int n(arr.size());
    deque<int> minime;
    vector<int> raspunsuri(n);
    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 += 1ll * costMinimSecventa[i] * cantitati[i];
    fout << ans;
    return 0;
}