Cod sursa(job #2801750)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 16 noiembrie 2021 20:26:25
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
const int NMAX=1e5+2;
long long v[NMAX];
deque<long long>dq;
int main()
{
    long long n,s,k,nr,sol=0;
    cin>>n>>s>>k;
    k++;
    for(long long i=1;i<=n;i++)
    {
        cin>>v[i]>>nr;
        if(dq.size()!=0 and dq.front()==i-k)
        {
            dq.pop_front();
        }
        while(dq.size()!=0 and v[dq.back()]+s*(i-dq.back())>=v[i])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        sol+=(v[dq.front()]+s*(i-dq.front()))*nr;
    }
    cout<<sol;
    return 0;
}