Submission #983310

#	Time	Username	Problem	Language	Result	Execution time	Memory
983310		NeroZein	Ski 2 (JOI24_ski2)	C++17	0 / 100	70 ms	100192 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 42;
const long long INF = 1e15;

int n, k;
int h[N], c[N];
int cnt[N * 2];
int prefsum[N * 2];
int prefcnt[N * 2];
int pref[N * 2 + 1];//mnC
long long dp[N * 2 + 1][N][N][N];

void init() {
  prefcnt[0] = cnt[0];
  for (int i = 1; i < N * 2; ++i) {
    prefcnt[i] = cnt[i] + prefcnt[i - 1]; 
    prefsum[i] += prefsum[i - 1];
  }
  for (int i = 1; i < N * 2; ++i) {
    if (pref[i - 1] == 0) continue; 
    if (pref[i] == 0 || (c[pref[i]] > c[pref[i - 1]])) {
      pref[i] = pref[i - 1]; 
    }
  }
  for (int height = 0; height < N * 2; ++height) {
    for (int available = 0; available < n; ++available) {
      for (int carry = 0; carry < n; ++carry) {
        for (int mn = 0; mn <= n; ++mn) {
          dp[height][available][carry][mn] = INF;
        }
      }
    }
  }    
  for (int i = 1; i <= n; ++i) {
    dp[h[i] + 1][1][prefcnt[h[i]] - 1][i] = ((prefcnt[h[i]] - 1) * (h[i] + 1) - (prefsum[h[i]] - h[i])) * k;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i] >> c[i]; 
    cnt[h[i]]++;
    prefsum[h[i]] += h[i];
    if (pref[h[i]] == 0 || c[pref[h[i]]] > c[i]) {
      pref[h[i]] = i; 
    }
  }
  init();
  for (int height = 0; height < N * 2; ++height) {
    for (int available = 0; available < n; ++available) {
      for (int carry = 0; carry < n; ++carry) {
        for (int mn = 1; mn <= n; ++mn) {
          int t = carry + cnt[height];
          for (int i = 0; i <= max(0, t - available); ++i) {
            int ncarry = carry - i + cnt[height];
            int navailable = available + i;
            int nmn = (i == 0 ? mn : pref[height]);
            if (available && ncarry) {
              int tmp = min(ncarry, available);
              ncarry -= tmp; 
              nmn = pref[height];
            }
            long long cost = ncarry * k + i * c[mn];
            dp[height + 1][navailable][ncarry][nmn] = min(dp[height + 1][navailable][ncarry][nmn], dp[height][available][carry][mn] + cost);
          }
        }
      }
    }
  }
  long long ans = LLONG_MAX;
  for (int available = 1; available < n; ++available) {
    ans = min(ans, dp[N * 2 - 1][available][0][pref[N * 2 - 1]]);
  }
  cout << ans << '\n';
  return 0;
}

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