Cod sursa(job #3226173)

Utilizator lensuLensu Alexandru lensu Data 20 aprilie 2024 13:26:25
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <deque>
#define int long long

using namespace std;

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

const int NMAX = 1e5 + 5, inf = 1e9;
int ans, N, S, T, C[NMAX], P[NMAX], dp[NMAX];
deque<int> dq;

signed main()
{
    cin >> N >> S >> T;

    for(int i = 1; i <= N; i++)
        cin >> C[i] >> P[i], dp[i] = inf;

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

    for(int i = 1; i <= N; i++)
        ans = ans + dp[i] * P[i];

    cout << ans;
}