Cod sursa(job #3200913)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 6 februarie 2024 09:19:23
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stack>
#define ll long long

using namespace std;

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

const int NMAX = 1e5;

int n, S, T;
int C[NMAX + 1];
int P[NMAX + 1];
deque<pair<int, int>> dq;
int dp[NMAX + 1];
ll answer;

int main()
{
    cin >> n >> S >> T;
    for(int i = 1; i <= n; i++)
        cin >> C[i] >> P[i];

    for(int i = 1; i <= n; i++)
    {
        if(!dq.empty() && i - dq.front().second > T)
            dq.pop_front();
        while(!dq.empty() && C[i] - i * S < dq.back().first)
            dq.pop_back();
        dq.push_back({C[i] - i * S, i});
        dp[i] = dq.front().first;
    }

    for(int i = 1; i <= n; i++)
    {
        dp[i] += i * S;
        answer += dp[i] * P[i];
    }

    cout << answer;

    return 0;
}