Submission #46985162

---

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 int64 inf = 1e14;

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

  int n;
  cin >> n;
  vector<int64> D(n);
  for (int i = 0; i < n; i++) cin >> D[i];
  int64 L1, C1, K1, L2, C2, K2;
  cin >> L1 >> C1 >> K1 >> L2 >> C2 >> K2;

  vector dp(n + 1, vector<int64>(K1 + 1, inf));
  dp[n][0] = 0;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= K1; j++) {
      for (int k = 0; k <= j; k++) {
        int64 len = max(0ll, D[i] - (j - k) * L1);
        int64 need = len / L2 + (len % L2 == 0 ? 0 : 1);
        ckmin(dp[i][j], dp[i + 1][k] + need);
      }
    }
  }
  int64 ans = inf;
  for (int j = 0; j <= K1; j++) {
    if (dp[0][j] <= K2) {
      ckmin(ans, j * C1 + dp[0][j] * C2);
    }
  }
  if (ans > 1e13) ans = -1;
  cout << ans << '\n';

  return 0;
}

Submission Info

Judge Result