Cod sursa(job #3307444)

Utilizator BusinessBirdRuse Andrei Cristian BusinessBird Data 20 august 2025 19:16:14
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

struct saptamana {
    int pret;
    int cantitate;
};

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ifstream fin("branza.in");
    ofstream fout("branza.out");

    long long N, S, T;
    fin >> N >> S >> T;

vector<saptamana> v(N+1);

    for (int i = 1; i <= N; ++i) {
        fin >> v[i].pret >> v[i].cantitate;
    }

    long long total = 0;

    deque<int> dq;

for (int i = 1; i <= N; ++i) {
    while (!dq.empty() && dq.front() <= i - T)
    dq.pop_front();

long long currentCost = v[i].pret;

while (!dq.empty()) {
    int j = dq.back();

    if (v[j].pret +1LL * (i-j) * S > currentCost)
        dq.pop_back();
    else
        break;
}
    dq.push_back(i);

    int j = dq.front();
    long long bestCost = v[j].pret + 1LL * (i-j) * S;
    total += 1LL * v[i].cantitate * bestCost;

}

    fout << total << endl;
    return 0;
}