Submission #1320254

---

Source Code Expand

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

int dp[5010][2];

int n, k;
int a[5001];
bool isnec(int x) {
    for (int i = 0; i <= k; i++)
        dp[i][0] = dp[i][1] = 0;

    int z = 0;

    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        if (i == x) continue;
        for (int j = 0; j <= k; j++) {
            dp[j][1-z] = dp[j][z] || (j >= a[i] && dp[j-a[i]][z]);
        }

        z = 1-z;
    }

    for (int j = max(k - a[x], 0); j < k; j++) {
        if (dp[j][z]) return true;
    }

    return false;
}


int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a+n);

    int p = 0;
    int q = n;

    while (q-p > 0) {
        int s = (p+q)/2;
        if (!isnec(s)) {
            p = s+1;
        } else {
            q = s;
        }
    }

    cout << q << "\n";
    return 0;
}

Submission Info

Judge Result