Submission #3014048

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>
#include<utility>
#include<numeric>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define all(v) begin(v), end(v)
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int inf = (int)1e9;
const ll INF = (ll)1e18;
const ll MOD{ (ll)1e9 + 7 };
const long double EPS = 1e-10;

int dp[2001][2001];

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> a(N + 1);
	rep(i, N) cin >> a[i + 1];

	if (accumulate(ALL(a), 0) == K) {
		cout << 1 << endl;
		return 0;
	}

	vector<int> S = a;
	rep(i, N) {
		S[i + 1] += S[i];
	}
	S[0] = 1;

	vector<vector<int>> dp(N + 1, vector<int>(N + 1, inf));
	dp[0][0] = 0;
	rep(i, N) {
		rep(j, N) {
			if (dp[i][j] == inf) continue;
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);

			int k = dp[i][j] * a[i + 1] / S[i] + 1;
			if (k > a[i + 1]) continue;
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + k);
		}
	}

	int ans = 0;
	rep(j, N + 1) {
		if (dp[N][j] <= K) ans = j;
	}

	cout << ans << endl;
}

Submission Info

Judge Result