Cod sursa(job #2801737)

Utilizator TraianQTraianQ TraianQ Data 16 noiembrie 2021 20:13:17
Problema Branza Scor 100
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");
const long long DIM=1e5+5;
long long sol;
long long n,add,k;
long long cst[DIM],sale;
deque <long long> cheese;
int 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;
}