Cod sursa(job #3270481)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 23 ianuarie 2025 15:49:41
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e5 + 1;
int N, S, T;
long long C[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void Solve()
{
    int sol = 0;
    deque<int> dq; /// OBS: dq este ordonat descrecator, iar dq.front() reprez cea mai mica suma curenta de platit per branza

    cin >> N >> S >> T;
    int P;
    for(int i = 0, j; i < N; i++)
    {
        cin >> C[i] >> P;

        if(dq.front() == i - T - 1)
            dq.pop_front();

        while(not dq.empty())
        {
            j = dq.back();
            if(C[j] + S * (i - j) > C[i])
                dq.pop_back();
            else
                break;
        }
        dq.push_back(i);

        j = dq.front();
        sol += P * (C[j] + S * (i - j));
    }

    cout << sol;
}

int main()
{
    SetInput("branza");

    Solve();

    return 0;
}