Submission #1443783

---

Source Code Expand

#include <iostream>
#include <set>
#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];
char dp[5001][5001];
set<ll> st[5000];
ll cnt[5000];

ll dfs(ll n, ll k, set<ll> &st) {
  if(n == 0 || k == 0) return 1;
  ll ret = 0;
  if(!st.count(n - 1)) {
    if(dp[n][k] & 2) st.insert(n - 1);
    if(dp[n][k] & 1) ret += dfs(n - 1, k, st);
    if(dp[n][k] & 2) ret += dfs(n - 1, k - A[n - 1], st);
  }
  return ret;
}

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

  REP(i, 0, N + 1) REP(j, 0, K + 1) 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(j + A[i] < K) dp[i + 1][j + A[i]] |= 2;
  }

  REP(i, 0, K) cnt[i] = 0;
  REP(i, 0, K) if(dp[N][i]) cnt[i] = dfs(N, i, st[i]);

  ll ans = N;
  REP(i, 0, N) {
    bool f = 0;
    REP(j, 0, K) if(dp[N][j] && (!st[j].count(i) || cnt[j] > 1) && j + A[i] >= K) f = 1;
    if(f) ans--;
  }
  cout << ans << endl;
}

Submission Info

Judge Result