Cod sursa(job #2712642)

Utilizator Albert_GAlbert G Albert_G Data 26 februarie 2021 10:41:44
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

const int N = 1e5;
int c[N];

int main()
{
    int n,storage_p,max_t;
    cin>>n>>storage_p>>max_t;
    deque <int> minCost;
    long long totalP=0;
    for(int i=0;i<n;++i)
    {
        int pret;
        cin>>c[i]>>pret;
        if(!minCost.empty() && i-max_t-1==minCost.front())
            minCost.pop_front();
        while(!minCost.empty() && c[i]<=(c[minCost.back()]+storage_p*(i-minCost.back())))
            minCost.pop_back();
        minCost.push_back(i);
        totalP += (long long)pret * ( c[minCost.front()] + (long long)(i-minCost.front()) * storage_p);
    }
    cout<<totalP;
    return 0;
}