Cod sursa(job #2914075)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 18 iulie 2022 16:42:16
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[100001];

int main()
{
    int n, s, t;
    in >> n >> s >> t;

    int ans = 0;
    deque<int>deq;

    for (int i=1; i<=n; i++)
    {
        int p;
        in >> a[i] >> p;
        while (!deq.empty() && deq.front() < i-t)
            deq.pop_front();

        while (!deq.empty() && a[i] <= a[deq.back()] + (i - deq.back()) * s)
            deq.pop_back();
        deq.push_back(i);
        ans += (a[deq.front()] + s * (i - deq.front())) * p;
    }

    out << ans;

    return 0;
}