Cod sursa(job #3271369)

Utilizator unomMirel Costel unom Data 25 ianuarie 2025 20:49:00
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <deque>

using namespace std;

#define int long long

ifstream in("branza.in");
ofstream out("branza.out");
int n, s, t, ans;
pair<int, int> v[100005];
int dp[100005];
deque<int> dq;

signed main()
{
    in>>n>>s>>t;
    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    for(int i = 1; i<=n; i++)
    {
        while(!dq.empty() && v[i].first - i * s <= v[dq.back()].first - dq.back() * s)
        {
            dq.pop_back();
        }

        dq.push_back(i);

        if(dq.front() == i - t - 1)
        {
            dq.pop_front();
        }

        dp[i] = i * s + v[dq.front()].first - dq.front() * s;

        ans += dp[i] * v[i].second;
    }

    out<<ans;

    return 0;
}