Submission #45712045

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

const int inf = 1e9;

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, H;
  cin >> n >> H;
  vector<int> X(n + 1), F(n), P(n);
  for (int i = 1; i <= n; i++) cin >> X[i];
  for (int i = 1; i < n; i++) cin >> P[i] >> F[i];

  vector dp(n + 1, vector(H + 1, vector<int>(H + 1, inf)));
  for (int i = 0; i <= H; i++) dp[n][i][i] = 0;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= H; j++) {
      for (int k = H; k >= 0; k--) {
        if (k < H) {
          ckmin(dp[i][j][k], dp[i][j][k + 1]);
        }
        int dx = X[i + 1] - X[i];
        if (j - dx >= 0 && k + dx <= H) {
          ckmin(dp[i][j][k], dp[i + 1][j - dx][k + dx]);
        }
        if (min(H, j + F[i]) - dx >= 0 && k + dx <= H) {
          ckmin(dp[i][j][k], dp[i + 1][min(H, j + F[i]) - dx][k + dx] + P[i]);
        }
        if (j - dx >= 0 && k - F[i] + dx >= 0 && k - F[i] + dx <= H &&
            k - F[i] >= 0 && k - F[i] <= H) {
          ckmin(dp[i][j][k], dp[i + 1][j - dx][k - F[i] + dx] + P[i]);
        }
      }
    }
  }
  int ans = dp[0][H][0];
  if (ans > inf / 2) ans = -1;
  cout << ans << '\n';
  return 0;
}

Submission Info

Judge Result