Cod sursa(job #2801723)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 16 noiembrie 2021 19:55:52
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

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

const long long DIM = 1e5 + 5;
long long sol;
long long n, add, k;
long long cst[DIM], sale;
deque <long long> cheese;

signed main (){
    fin>>n>>add>>k; k++;
    for(long long i=1; i<=n; i++){
        fin>>cst[i]>>sale;

        while(!cheese.empty() && cst[i] < cst[cheese.back()] + add * (i - cheese.back()))
            cheese.pop_back();
        cheese.push_back(i);

        sol += (long long)sale * (cst[cheese.front()] + (long long)add * (i - cheese.front()));
        if(i >= k && cheese.front() == i-k+1)
            cheese.pop_front();
    }
    fout<<sol;
    return 0;
}