Submission #1972781

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

ll a[5003];
bool seg[10003];


int main() {
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = n; i >= 1; --i) {
		if (a[i] >= k) {
			--n;
		}
	}
	int lo = 0, hi = n + 1;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		for (int i = 0; i < 1003; ++i) seg[i] = false;
		seg[0] = true;
		for (int i = 1; i <= n; ++i) {
			if (i == mid) continue;
			for (int j = 1002 - a[i]; j >= 0; --j) {
				if (!seg[j]) continue;
				seg[j + a[i]] = true;
			}
		}
		bool flag = false;
		for (int i = k - a[mid]; i < k; ++i) {
			flag |= seg[i];
		}
		if (flag) hi = mid;
		else lo = mid;
	}
	cout << lo << endl;
	return 0;
}

Submission Info

Judge Result