Cod sursa(job #3126688)

Utilizator TediCutuTudor Chitu TediCutu Data 6 mai 2023 20:56:40
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

long long n, taxa, k, sol, dr, st = 1;
int main()
{

    fin >> n >> taxa >> k;
    k++;
    vector<long long> v(n+1);
    vector<long long> c(n+1);
    vector<long long> deq(n+1);

    for (long long i = 1; i <= n; i++)
        fin >> v[i] >> c[i];

    for (long long i = 1; i <= n; i++)
    {
        while (dr>=st && v[i] <= v[deq[dr]] + taxa * (i - deq[dr]))
            dr--;

        dr++;
        deq[dr] = i;
        if (deq[st] == i - k)
            st++;

        sol += (v[deq[st]] + taxa * (i - deq[st])) * c[i];
    }

    fout << sol << endl;

    return 0;
}