提出 #27059260

---

ソースコード 拡げる

#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

int A[5000];
bool S1[5001][5000];
bool S2[5001][5000];

int main()
{
	int N,K;
	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}

	S1[0][0] = true;
	for (int i = 0; i < N; ++i) {
		int a = A[i];
		copy(S1[i], S1[i]+K, S1[i+1]);
		for (int j = K-1; a <= j; --j) {
			S1[i+1][j] |= S1[i+1][j-a];
		}
	}

	S2[N][0] = true;
	for (int i = N-1; 0 <= i; --i) {
		int a = A[i];
		copy(S2[i+1], S2[i+1]+K, S2[i]);
		for (int j = K-1; a <= j; --j) {
			S2[i][j] |= S2[i][j-a];
		}
	}

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int a = A[i];
		bool *s1 = S1[i], *s2 = S2[i+1], any = false;
		for (int i = 0; i < K && ! any; ++i) {
			any |= s1[i] && (K <= i+a || any_of(s2+K-i-a, s2+K-i, [](bool b){ return b; }));
		}
		if (! any) {
			ans += 1;
		}
	}

	cout << ans << endl;
	return 0;
}

提出情報

ジャッジ結果