Cod sursa(job #2884779)

Utilizator UpgradeStrikeMurgilas Mihai-Rares UpgradeStrike Data 4 aprilie 2022 20:57:05
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream>
#include <deque>

using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int v[5000001];
int main()
{
    int n,s,t;
    long long p=0;
    in>>n>>s>>t;
    t++;
    deque <int> dq;
    for(int i=0;i<n;i++)
    {
        int c;
        in>>v[i]>>c;
        if(!dq.empty()&&dq.front()==i-t)
            dq.pop_front();
        while(!dq.empty()&&v[dq.back()]+(i-dq.back())*s>=v[i])
            dq.pop_back();
        dq.push_back(i);
        p+=c*(v[dq.front()]+(i-dq.front())*s);
    }
    out<<p;
    return 0;
}