Cod sursa(job #3240980)

Utilizator divadddDavid Curca divaddd Data 24 august 2024 18:22:44
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX = 1e5+2;
int n,s,t,c[NMAX],p[NMAX],dp[NMAX];

ifstream fin("branza.in");
ofstream fout("branza.out");

void minSelf(int &a, int b){
  a = min(a, b);
}

signed main()
{
  fin >> n >> s >> t;
  for(int i = 1; i <= n; i++){
    fin >> c[i] >> p[i];
    dp[i] = c[i];
  }
  auto cost = [&](int pos) -> int {
    return c[pos] - pos * s;
  };
  int ans = 0;
  deque<int> dq;
  for(int i = 1; i <= n; i++){
    while(!dq.empty() && dq.back() < i-t){
      dq.pop_back();
    }
    if(!dq.empty()){
      int cand = cost(dq.back()) + i * s;
      minSelf(dp[i], cand);
    }
    ans += p[i] * dp[i];
    while(!dq.empty() && cost(i) < cost(dq.front())){
      dq.pop_front();
    }
    dq.push_front(i);
  }
  fout << ans;
  return 0;
}