Submission #1167879

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int i, j, it, now, k, n, dp[5005], a[5005], rs;
long long sum;

int main() {
  ios_base::sync_with_stdio(0);

  cin >> n >> k;
  for(i = 1; i <= n; ++i) cin >> a[i], sum += a[i];

  if(sum < k) return cout << n << '\n', 0;

  sort(a + 1, a + n + 1);

  for(it = 1; it <= n; ++it) {
    memset(dp, 0, sizeof(dp));

    for(dp[0] = i = 1; i <= n; ++i) {
      if(i == it) continue;

      for(j = k; j >= 0; --j)
        if(dp[j] && j + a[i] <= k) dp[j + a[i]] = 1;
    }

    for(i = 0; i < k; ++i)
      if(dp[i] && i + a[it] >= k) i = 1e9;

    if(i == k) ++rs;
  }

  cout << rs << '\n';

  return 0;
}

Submission Info

Judge Result