Cod sursa(job #2887283)

Utilizator AdelaCorbeanuAdela Corbeanu AdelaCorbeanu Data 9 aprilie 2022 11:28:35
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>

int c[5000010], p[5000010];
int deq[5000010];

int main()
{
    std::ifstream fin("branza.in");
    std::ofstream fout("branza.out");
    int n, s, k;
    fin >> n >> s >> k;

    for (int i = 0; i < n; ++i) fin >> c[i] >> p[i];

    int front = 0, back = 0;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        while (deq[front] < i - k + 1) front++;

        while (c[i] <= c[deq[back]] + s * (i - deq[back]) && back >= front) back--;
        deq[++back] = i;

        sum += 1ll * (c[deq[front]] * p[i]) + 1ll * s * (i - deq[front]) * p[i];
    }

    fout << sum;
    return 0;
}