Cod sursa(job #2733987)

Utilizator Ion.AAlexandru Ion Ion.A Data 31 martie 2021 11:00:48
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int N = 100000;
int n, k, t, a[N], cnt[N];
deque <int> dq;

int main()
{
    long long s = 0;
    in >> n >> k >> t;
    t++;
    for (int i = 0; i < n; i++)
    {
        long long b;
        in >> a[i] >> b;
        cnt[i] = 0;
        if (!dq.empty() && dq.front() == i - t)
        {
            dq.pop_front();
        }
        while (!dq.empty() && a[i] <= a[dq.back()] + k * (i - dq.back()))
        {
            dq.pop_back();
        }
        dq.push_back(i);
        s += (a[dq.front()] + k * (i - dq.front())) * b;
    }
    out << s;
    return 0;
}