Submission #1451637

---

Source Code Expand

#include <iostream>
#include <algorithm>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, K, A[5000];
bool dp[5001][5000];

bool ok(ll n) {
  REP(i, 0, N + 1) REP(j, 0, K) dp[i][j] = 0;
  dp[0][0] = 1;

  REP(i, 0, N) REP(j, 0, K) if(dp[i][j]) {
    dp[i + 1][j] = 1;
    if(i != n && j + A[i] < K) dp[i + 1][j + A[i]] = 1;
  }

  bool f = false;
  REP(i, 0, K) if(dp[N][i] && i + A[n] >= K) f = true;
  return f;
}

int main(void) {
  cin >> N >> K;
  REP(i, 0, N) cin >> A[i];

  sort(A, A + N);

  ll l = 0, h = N;
  while(h - l > 1) {
    ll m = (l + h) / 2;
    if(ok(m)) h = m;
    else l = m;
  }
  cout << h << endl;
}

Submission Info

Judge Result