Cod sursa(job #3330727)

Utilizator RuxandraPro12_Metehau Ruxandra Maria RuxandraPro12_ Data 21 decembrie 2025 15:46:56
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 100005;

int n, s, t;
int c[N_MAX], p[N_MAX];
deque <int> dq;

int main() {
    fin >> n >> s >> t;
    long long suma = 0;
    for (int i = 1; i <= n; i++) {
        fin >> c[i] >> p[i];
        while (!dq.empty() && c[i] <= c[dq.back()] + 1ll * s * (i - dq.back()))
            dq.pop_back();
        dq.push_back(i);
        if (dq.front() == i - t - 1)
            dq.pop_front();
        suma += 1ll * p[i] * (c[dq.front()] + 1ll * s * (i - dq.front()));
    }
    fout << suma << "\n";
    return 0;
}