Cod sursa(job #2638555)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 28 iulie 2020 18:37:45
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f ("branza.in");
ofstream g ("branza.out");

constexpr int NMAX = 1e5 + 5;

deque <int> D;

int N, T, S;

int C[NMAX], P[NMAX];

int Value (int pos, int finish) {
    return C[ pos ] + S * (finish - pos);
}

int main()
{
    f >> N >> S >> T;

    long long ans = 0;
    for (int i = 1; i <= N; ++ i ) {
        f >> C[ i ] >> P[ i ];
        if (!D.empty() && D.front() < i - T)
            D.pop_front();

        while (!D.empty() && Value(D.back(), i) > C[ i ]) {
            D.pop_back();
        }

        D.push_back(i);

        ans = ans + 1LL * Value(D.front(), i) * P[ i ];
    }

    g << ans << '\n';
    return 0;
}