Cod sursa(job #2861878)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 4 martie 2022 17:05:20
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int NMAX=1e6+5;
long long c[NMAX],p[NMAX];

deque<long long>dq;

int main()
{
    int n,i,j,s,t;
    long long cost=0;
    fin>>n>>s>>t;
    for(i=1;i<=n;i++)
    {
        cin>>c[i]>>p[i];
        while(!dq.empty() && c[dq.back()]+(i-dq.back())*s>=c[i])
        {
            dq.pop_back();
        }
        while(!dq.empty() && (i-dq.front())>t)
            dq.pop_front();
        dq.push_back(i);
        cost=cost+p[i]*(c[dq.front()]+s*(i-dq.front()));
    }
    fout <<cost;
    return 0;
}