Cod sursa(job #2638649)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 29 iulie 2020 11:38:34
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <deque>

using namespace std;

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

typedef pair < int, int > PII;

const int NMAX = 1e5 + 5;

int N, S, T;
PII A[NMAX];

deque < int > D;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> S >> T;

    for(int i = 1; i <= N; ++i)
        f >> A[i].first >> A[i].second;

    return;
}

static inline int Get_Cost (int Old_Day, int New_Day)
{
    return A[Old_Day].first + S * (New_Day - Old_Day);
}

static inline void Solve ()
{
    long long ans = 0;

    for(int Week = 1; Week <= N; ++Week)
    {
        int Old_Limit = Week - T + 1;
        while(!D.empty() && D.front() < Old_Limit)
            D.pop_front();

        while(!D.empty() && Get_Cost(D.front(), Week) > A[Week].first)
            D.pop_back();
        D.push_back(Week);

        ans += 1LL * Get_Cost(D.front(), Week) * A[Week].second;
    }

    g << ans << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}