Cod sursa(job #2914076)

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

using namespace std;

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

long long a[100001];

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

    long long ans = 0;
    deque<long long>deq;

    for (long long i=1; i<=n; i++)
    {
        long long 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;
}