Cod sursa(job #3308848)

Utilizator iccjocIoan CHELARU iccjoc Data 28 august 2025 18:05:39
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> v(n + 1), c(n + 1), q(n + 1);
    for(int i = 1; i <= n; i++)
    {
        cin >> c[i] >> q[i];
        v[i] = c[i] - d * i;
    }
    deque<pair<int, int>> dq;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        while(dq.size() && dq.back().first > v[i])
        {
            dq.pop_back();
        }
        if(dq.size() && dq.front().second < i - m)
        {
            dq.pop_front();
        }
        dq.push_back({v[i], i});
        ans += (dq.front().first + d * i) * q[i];
    }
    cout << ans;
}