Submission #1241850

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

int N, K;
int a[5001];
int ans;
bool is;

int main() {
  cin >> N >> K;

  for(int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a,a+N);
 
  int l = 0;
  int r = N;
  while(r > l){
    int s = (l+r)/2;
    if(a[s] > K){r = s;continue;}
    
    is = false;
    bool dp[N+2][K+2] = {};
    dp[0][0] = true;
    if(s > 0)dp[0][a[0]] = true;
    for(int j = 1; j < N; j++) {
      for(int k = 0; k < K; k++) {
	if(dp[j-1][k]) dp[j][k] = true;
	if(j != s && k >= a[j] && dp[j-1][k-a[j]]) {
	  dp[j][k] = true;
	}
      }
    }
    for(int m = K - a[s]; m < K; m++) {
      if(dp[N-1][m]) {is = true; break;}
    }
    if(is) r = s;
    else l = s+1;
  
  }
  cout << r <<endl;
}


	      
      
  

Submission Info

Judge Result