Cod sursa(job #3291544)

Utilizator alexdraguAlexandru Dragu alexdragu Data 5 aprilie 2025 01:59:21
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <deque>
#define int long long
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

const int MAX=1e5;
int n,t,s,c[MAX+5],p[MAX+5],i,dp[MAX+5];
int sol;
deque <int> dq;
signed main()
{
    fin>>n>>s>>t;

    for (i=1; i<=n; i++)
        fin>>c[i]>>p[i];


    for (i=1; i<=n; i++)
    {

        while (!dq.empty() && dq.front()<i-t)
            dq.pop_front();

        while (!dq.empty() && c[dq.back()]-dq.back()*s>c[i]-i*s)
            dq.pop_back();

        dq.push_back(i);
        dp[i]=i*s+c[dq.front()]-dq.front()*s;
    }
    for (i=1; i<=n; i++)
    sol=sol+dp[i]*p[i];

    fout<<sol;
    return 0;
}