Cod sursa(job #3369709)

Utilizator radu_alexRadu Hopartean radu_alex Data 21 octombrie 2026 20:11:34
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb

/*

N - queryuri {
    C - cost pentru productie
    P - cantiate cumparata 
}

S - plata depozit 
T - duratie maxima depozit

idee: gaseste cel mai eficient mod de a da
"cover" la depozit pentru a minimiza costul

costul cel mai mic pe unitate 
va da provide pentru urmatoarele 
t elemente
*/

#include <fstream>
#include <vector>
#include <deque>

#define ll long long int 

std::ifstream in("branza.in");
std::ofstream out("branza.out");

struct obj {
    int cost;
    int amount;
};

int n,s,t,ans = 0;

std::vector<obj>v;

inline ll value(int j) { // get individual value of each deque element
    return v[j].cost - 1LL * s * j;
}

int main(void) {

    in >> n >> s >> t;
    v.resize(n);

    for(int i = 0 ; i < n ; i ++ ) {
        in >> v[i].cost >> v[i].amount;
    }

    std::deque<int>dq;

    for(int i = 0 ; i < n ; i ++ ) {
        
        while(!dq.empty() && dq.front() < i-t) {
            dq.pop_front();
        }

        while(!dq.empty() && value(dq.back()) >= value(i)) {
            dq.pop_back();
        }

        dq.push_back(i);

        ans += (value(dq.front()) + 1LL * s * i) * v[i].amount;
    }

    out << ans;

    return 0;
}