Submission #9699761

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int dp[2001][2001] = {};

int main() {
  int n, k;
  cin >> n >> k;
  vi a(n + 1);
  vi cum(n + 1, 0);
  REP(i, n) {
    cin >> a[i + 1];
    cum[i + 1] = cum[i] + a[i + 1];
  }

  REP(i, n + 1) {
    FOR(j, 1, n + 1) { dp[i][j] = k + 1; }
  }

  if (k == cum[n]) {
    cout << 1 << endl;
    return 0;
  }

  FOR(i, 1, n + 1) {
    FOR(j, 1, n + 1) {
      if (i < j)
        dp[i][j] = k + 1;
      dp[i][j] = dp[i - 1][j];
      double po = (double)a[i] / cum[i - 1] * dp[i - 1][j - 1];
      if (po < a[i]) {
        int mi = ceil(po);
        if (mi == floor(po))
          mi++;
        if (mi < a[i])
          dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + mi);
      }
    }
  }

  int ans = 0;
  REP(i, n + 1) {
    if (dp[n][i] <= k) {
      ans = max(ans, i);
    }
  }
  cout << ans << endl;
}

Submission Info

Judge Result