Submission #1018281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018281		erray	Ski 2 (JOI24_ski2)	C++17	100 / 100	495 ms	433748 KiB

Main

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  vector<int> H(N), C(N);
  vector<int> poses;
  for (int i = 0; i < N; ++i) {
    cin >> H[i] >> C[i];
    poses.push_back(H[i]);
    poses.push_back(H[i] + 1);
  }
  auto sh = H;
  sort(sh.begin(), sh.end());
  sort(poses.begin(), poses.end());
  poses.erase(unique(poses.begin(), poses.end()), poses.end());
  int s = int(poses.size());
  vector<int> pref_mn(s, int(1E9));
  for (int i = 0; i < N; ++i) {
    int lb = int(lower_bound(poses.begin(), poses.end(), H[i]) - poses.begin());
    pref_mn[lb] = min(pref_mn[lb], C[i]);
  }

  constexpr int64_t inf = int64_t(1e16);
  vector<int64_t> mn(s);
  mn[0] = inf; 
  for (int i = 0; i < s - 1; ++i) {
    mn[i + 1] = min<int64_t>(mn[i], pref_mn[i]);
  }
  vector<int64_t> pref(N + 1);
  for (int i = 0; i < N; ++i) {
    pref[i + 1] = pref[i] + sh[i];
  }
  auto Ckmin = [&](int64_t& x, int64_t y) {
    x = min(x, y);
  };
  vector<int> pt(s);
  for (int i = 0; i < s; ++i) {
    pt[i] = pt[i - !!i];
    while (pt[i] < N && sh[pt[i]] <= poses[i]) {
      ++pt[i];
    }
  }
  vector<vector<vector<int64_t>>> best(N + 1, vector<vector<int64_t>>(s + 1, vector<int64_t>(N + 1, inf)));
  best[0][0][1] = 0;
  for (int i = 0; i < N; ++i) {
    for (int pos = 0; pos < s; ++pos) {
      for (int leaf = 1; leaf <= N; ++leaf) {
        int64_t me = best[i][pos][leaf];
        Ckmin(best[i][pos + 1][leaf], me);
        if (sh[i] > poses[pos]) {
          continue;
        }
        if (i + leaf < N && sh[i + leaf] <= poses[pos]) {
          Ckmin(best[i][pos][leaf + 1], me + mn[pos]);
        }
        int go = min<int64_t>(i + (pos == s - 1 ? int64_t(N) : 1LL * leaf * (poses[pos + 1] - poses[pos])), pt[pos]);
        int start = poses[pos];
        int need = go - i;
        int last = start + (need / leaf);
        auto G = [&](int x) { return 1LL * x * (x - 1) / 2; };
        int64_t this_formula_will_be_fucked_up = 1LL * (need % leaf) * last + 1LL * leaf * (G(last) - G(start));
        this_formula_will_be_fucked_up -= pref[go] - pref[i];
        if (this_formula_will_be_fucked_up != 0 && inf / this_formula_will_be_fucked_up + 10 < K) {
          continue;          
        }
        Ckmin(best[go][pos + 1][leaf], me + K * this_formula_will_be_fucked_up);
      } 
    }
  }
  int64_t ans = inf;
  for (int i = 0; i <= s; ++i) {
    for (int j = 0; j <= N; ++j) {
      Ckmin(ans, best[N][i][j]);
    }
  }
  cout << ans << '\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