Submission #1197684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197684		abczz	Ski 2 (JOI24_ski2)	C++20	100 / 100	481 ms	852932 KiB

Main

#include <iostream>
#include <map>
#define ll long long

using namespace std;

ll n, k, H[300], C[300], tot[601], A[601], B[601];
ll dp[601][301][301], dp2[601][301][301];
map <ll, ll> mp;
int main() {
  cin >> n >> k;
  for (int i=0; i<n; ++i) {
    cin >> H[i] >> C[i];
    ++mp[H[i]];
    ++mp[H[i]+1];
  }
  ll z = 0;
  for (auto [x, y] : mp) {
    B[z] = x;
    mp[x] = z++;
  }
  for (int i=0; i<mp.size(); ++i) A[i] = 1e18;
  for (int i=0; i<n; ++i) {
    ++tot[mp[H[i]]];
    A[mp[H[i]]] = min(A[mp[H[i]]], C[i]);
  }
  for (int i=0; i<=mp.size(); ++i) {
    for (int j=0; j<=n; ++j) {
      for (int x=0; x<=n; ++x) {
        dp[i][j][x] = dp2[i][j][x] = 1e18;
      }
    }
  }
  B[mp.size()] = 1e10;
  dp[0][tot[0]][1] = 0;
  for (int i=0; i<mp.size(); ++i) {
    if (i) A[i] = min(A[i], A[i-1]);
    for (ll j=0; j<=n; ++j) {
      for (ll x=1; x<=n; ++x) {
        dp2[i][j][x] = min(dp2[i][j][x], dp2[i][j][x-1]);
        if (i) dp[i][j][x] = min(dp[i][j][x], dp2[i][j][x] + x * A[i-1]);
        if (dp[i][j][x] >= 1e18) continue;
        ll d = min(B[i+1]-B[i], (j+x-1)/x), s;
        if (j-d*x >= 0) s = (j-x+j-d*x)*d/2 * k;
        else s = (j-x+j-(d-1)*x)*(d-1)/2 * k;
        dp2[i+1][max(0LL, j-d*x)+tot[i+1]][x] = min(dp2[i+1][max(0LL, j-d*x)+tot[i+1]][x], dp[i][j][x] + s - A[i] * x);
      }
    }
  }
  ll f = 1e18;
  for (int x=1; x<=n; ++x) {
    dp2[mp.size()][0][x] = min(dp2[mp.size()][0][x], dp2[mp.size()][0][x-1]);
    dp[mp.size()][0][x] = min(dp[mp.size()][0][x], dp2[mp.size()][0][x] + x * A[mp.size()-1]);
    f = min(f, dp[mp.size()][0][x]);
  }
  cout << f << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 14 / 14