Cod sursa(job #3123983)

Utilizator Mircea08Tomita Mircea Stefan Mircea08 Data 26 aprilie 2023 16:04:00
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
std :: vector <int> cost;
std :: deque <int> dq;
unsigned long long int ans;
int n, s, t, p, c, i, j;
int main() {
    std :: ios_base :: sync_with_stdio(0);
    dq.push_back(0);
    cost.emplace_back(-1e9);
    std :: ifstream fin("branza.in");
    fin >> n >> s >> t >> c >> p;
    cost.emplace_back(c);
    ans += p * c;
    dq.push_back(1);
    for (i = 2; i <= t and i <= n; ++ i) {
        fin >> c >> p;
        cost.emplace_back(c);
        while (cost[dq.back()] + (i - dq.back()) * s >= cost[i])
            dq.pop_back();
        dq.push_back(i);
        ans += p * (cost[dq[1]] + (i - dq[1]) * s);
    }
    for (; i <= n; ++ i) {
        fin >> c >> p;
        if (i - dq[1] == t) {
            dq.pop_front();
            dq.front() = 0;
        }
        cost.emplace_back(c);
        while (cost[dq.back()] + (i - dq.back()) * s >= cost[i])
            dq.pop_back();
        dq.push_back(i);
        ans += p * (cost[dq[1]] + (i - dq[1]) * s);
    }
    fin.close();
    std :: ofstream fout("branza.out");
    fout << ans;
    fout.close();
    return 0;
}