Submission #1587844

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	int a[n];
	for(int &i:a) cin >> i;
	if(n == 1){
		cout << (k <= a[0]) << endl;
		return 0;
	}
	vector<set<int>> l(n);
	l[0].insert(0);
	if(a[0] < k) l[0].insert(a[0]);
	for(int i = 1; i < n; i++){
		for(int x:l[i - 1]){
			l[i].insert(x);
			if(x + a[i] < k) l[i].insert(x + a[i]);
		}
	}
	vector<set<int>> r(n);
	r[0].insert(0);
	if(a[n - 1] < k) r[0].insert(a[n - 1]);
	for(int i = n - 2; 0 <= i; i--){
		for(int x:r[n - i - 2]){
			r[n - i - 1].insert(x);
			if(x + a[i] < k) r[n - i - 1].insert(x + a[i]);
		}
	}
	int ans = 0;
	{
		auto itr = r[n - 2].lower_bound(k - a[0]);
		if(itr == r[n - 2].end()) ans++;
		auto itr2 = l[n - 2].lower_bound(k - a[n - 1]);
		if(itr2 == l[n - 2].end()) ans++;
	}
	for(int i = 1; i < n - 1; i++){
		for(int x:l[i - 1]){
			auto itr = r[i - 1].lower_bound(k - a[i] - x);
			if(itr != r[i - 1].end()) goto next;
		}
		ans++;
		next:;
	}
	cout << ans << endl;
}

Submission Info

Judge Result