Cod sursa(job #3126676)

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

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

    fin >> n >> taxa >> k;
    k++;
    vector<int> v(n+1);
    vector<int> c(n+1);
    vector<int> deq(n+1);
    for (int i = 1; i <= n; i++)
        fin >> v[i] >> c[i];
    for (int 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;
}