Submission #1972282

---

Source Code Expand

#include <iostream>

using namespace std;

int N, K;
int a[5005];
bool dp[5005][5005];

bool check(int m)
{
	if(m > N) return true;
	if(m <= 0) return false;
	
	for(int i = 0; i <= N; i++){
		for(int j = 0; j < K; j++){
			dp[i][j] = false;
		}
	}
	dp[0][0] = true;
	
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < K; j++){
			dp[i][j] = dp[i-1][j];
			if(i == m) continue;
			if(j - a[i] >= 0 && dp[i-1][j-a[i]]) dp[i][j] = true;
		}
	}
	
	for(int i = max(0, K - a[m]); i < K; i++){
		if(dp[N][i]) return true;
	}
	return false;
}

int main(void)
{
	cin >> N >> K;
	for(int i = 1; i <= N; i++) cin >> a[i];
	
	int ub = N+1, lb = 0, mid;
	while(ub - lb > 1){
		mid = (ub + lb) / 2;
		if(check(mid)) ub = mid;
		else lb = mid;
	}
	
	cout << lb << endl;
	return 0;
}

Submission Info

Judge Result