Submission #1168375

---

Source Code Expand

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr = ds.begin(); itr != ds.end(); ++itr)
#define mp make_pair
#define INF 2000000000
#define INFL 2000000000000000000LL
#define EPS 1e-9
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
typedef pair<int, pair<int, int> > Edge;

int N, K;
vi a;

// a[n]が必要
bool need(int n) {
	vb can(K, false);
	can[0] = true;
	rep(i, N) {
		if (i == n)continue;
		reprev(j, K - a[i]) {
			can[j + a[i]] = can[j + a[i]] || can[j];
		}
	}

	repl(i, max(0, K - a[n]), K) {
		if (can[i])return true;
	}
	return false;
}

int main() {
	cin >> N >> K;
	a = vi(N);
	rep(i, N)cin >> a[i];

	sort(a.begin(), a.end());

	int ans = 0;
	int no = -1, yes = N;
	while (yes - no > 1) {
		int med = (no + yes) / 2;
		if (need(med)) {
			yes = med;
		}
		else {
			no = med;
		}
	}

	cout << yes << endl;

	return 0;
}

Submission Info

Judge Result