Cod sursa(job #2610312)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 4 mai 2020 18:46:42
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <deque>

using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
deque <long long>d;
int v[100001];
int main()
{
    int n,s,t,c;
    long long sol=0;
    int i;
    in>>n>>s>>t;
    t++;
    for(i=1; i<=n; i++)
    {
        in>>v[i]>>c;
        if(d.size() and d.front()==i-t)
        {
            d.pop_front();
        }
        while(d.size() and v[d.back()]+s*(i-d.back())>=v[i])
        {
            d.pop_back();
        }
        d.push_back(i);
        sol+=c*(v[d.front()]+(i-d.front())*s);
    }
    out<<sol;
    return 0;
}