Cod sursa(job #2169311)

Utilizator amaliarebAmalia Rebegea amaliareb Data 14 martie 2018 14:44:34
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
const int MaxN = 100005;
ll n, s, k, cost[MaxN], dem[MaxN], ans;
deque<ll> dq;

int main()
{
    f >> n >> s >> k;
    for (int i = 1; i <= n; ++i) f >> cost[i] >> dem[i];
    for (int i = 1; i <= n; ++i) {
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && cost[dq.back()] - s * dq.back() >= cost[i] - s * i) dq.pop_back();
        dq.push_back(i);
        ans += dem[i] * (cost[dq.front()] + s * (i - dq.front()));
    }
    g << ans << '\n';
    return 0;
}