Cod sursa(job #3170814)

Utilizator DeriusSaila Darius Derius Data 18 noiembrie 2023 10:17:30
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int main()
{
    int n,s,t;
    fin >>n>>s>>t;
    vector<int> cost(n);
    long long cost_total=0;
    t++;
    deque<int>dq;
    for(int i=0;i<n;i++)
    {
        int cantitate;
        fin >>cost[i]>>cantitate;
        if(!dq.empty()&&dq.front()==i-t)
        {
            dq.pop_front();
        }
        while(!dq.empty()&&cost[i]<=cost[dq.back()]+(i-dq.back())*s)
        {
            dq.pop_back();
        }
        dq.push_back(i);
        cost_total+=(long long)cantitate*(cost[dq.front()]+(i-dq.front())*s);
    }
    fout <<cost_total;
    return 0;
}