Cod sursa(job #2719363)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 9 martie 2021 19:45:05
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=100001;
int v[Nmax];
deque <int> d;

int main()
{
    long long n, s, t, r=0, p;
    cin >> n >> s >> t;
    t++;
    for (int i=1; i<=n; i++)
    {
        cin >> v[i] >> p;
        if (!d.empty() && d.front()==i-t)
        {
            d.pop_front();
        }
        while (!d.empty() && v[i]<=v[d.back()]+s*(i-d.back()))
        {
            d.pop_back();
        }
        d.push_back(i);
        r+=(v[d.front()]+s*(i-d.front()))*(long long)p;
    }
    cout << r;
    return 0;
}