Cod sursa(job #3270487)

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

using namespace std;

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

struct branza
{
    int index;
    long long cost;
};

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()
{
    long long sol = 0;
    deque<branza> dq; /// OBS: dq este ordonat descrecator, iar dq.front() reprez cea mai mica suma curenta de platit per branza

    cin >> N >> S >> T;
    long long P, C;
    branza temp;

    for(int i = 0; i < N; i++)
    {
        cin >> C >> P;

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

        while(not dq.empty())
        {
            temp = dq.back();
            if(S * (i - temp.index) + temp.cost > C)
                dq.pop_back();
            else
                break;
        }
        dq.push_back(branza{i, C});

        temp = dq.front();
        sol += P * (S * (i - temp.index) + temp.cost);
    }

    cout << sol;
}

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

    Solve();

    return 0;
}