Submission #3229933

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 5010

bool dp[MAX_N][MAX_N] = {};
bool maked[MAX_N][MAX_N] = {};     // グループ内の数の組み合わせで i 抜きで j が作れるなら true
int N, K;
int A[MAX_N];
map<int, bool> isChecked;
map<int, int> valToInd;

// 今 i を見ていて、現在の数が j のとき
// ただし A[skip] は加算せずにとばす
void dfs(int i, int j, int skip) {
    if(i >= N) { return; }
    if(dp[i][j]) { return; }
    dfs(i+1, j, skip);
    if(i != skip && j + A[i] < K) {
        maked[skip][j + A[i]] = true;
        dfs(i+1, j + A[i], skip);
        valToInd[A[i]] = i;
    }
    dp[i][j] = true;
}

signed main()
{
    cin >> N >> K;
    REP(i, N) { cin >> A[i]; }
    REP(i, N) {
        if(isChecked.count(A[i]) != 0) { continue; }
        ZERO(dp);
        dfs(0, 0, i);
        isChecked[A[i]] = true;
    }
    ll ans = N;
    REP(i, N) {
        for(int j = K - A[i]; j < K; ++j) {
            int ind = valToInd[A[i]];
            if( j <= 0 || maked[ind][j]) {
                ans--;
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Submission Info

Judge Result