Submission #1169466

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define DIM 5005

int N, K, x;
int V[DIM];
int appears[DIM][DIM];
int is[DIM];

int main() {
//    #ifndef ONLINE_JUDGE
//    freopen("input.txt","r",stdin);
//    #endif // ONLINE_JUDGE

    cin >> N >> K;

    for(int i = 1; i <= N; ++i) {
        cin >> x;

        if(x < K) {
            V[++V[0]] = x;
        }
    }

    N = V[0];
    V[0] = 0;

    sort(V + 1, V + 1 + N);

    is[0] = 1;

    for(int obj = 1; obj <= N; ++obj) {
        for(int actual = K - V[obj]; actual >= 0; --actual) {
            if(is[actual]) {
                is[actual + V[obj]] = 1;

                for(int cop = 1; cop <= N; ++cop) {
                    appears[actual + V[obj]][cop] |= appears[actual][cop];
                }

                appears[actual + V[obj]][obj] = 1;
            }
        }
    }

    int ans = 0;
    for(int obj = 1; obj <= N; ++obj) {
        int flag = 1;

        if(is[K] && appears[K][obj]) {
            flag = 0;
        }

        if(flag) {
            for(int actual = K - 1; flag && actual >= K - V[obj]; actual--) {
                if(is[actual] && appears[actual][obj] == 0) {
                    flag = 0;
                }
            }

            ans += flag;
        }
    }

    cout << ans << '\n';

    return 0;
}

Submission Info

Judge Result