Submission #1178072

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include <array>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define EVEL 1

#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {X;}
#define TF(f) {f;}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1000000;
#define NMAX 5000
#define MAX 10

ll sum[NMAX + 1], temp, buff = 0;
int N, K, ans = 0;
int A[100010];
int count = 0;
std::array<std::array<bool, NMAX + 10>, NMAX + 10> dp, dp1;
std::array<std::array<bool, NMAX + 10>, NMAX + 10> vis, vis1;
int low = 0, high, mid;

bool dfs(ll x, ll y) {
	if (y == 0) {
		return true;
	}
	if (y<0)return false;
	if (vis[x][y]) {
		return dp[x][y];
	}
	else vis[x][y] = true;
	if (y == 0) { dp[x][y] = true; /*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y]; }
	if (x == N) { dp[x][y] = false;/*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y]; }

	if (dfs(x + 1, y) || dfs(x + 1, y - A[x])) {
		dp[x][y] = true;
	}
	else dp[x][y] = false;
	//DEB(dp[x][y])DEB(x)DEB(y)END
	return dp[x][y];
}
bool front(ll x, ll y) {
	if (y == 0) {
		return true;
		//dp1[x][y] = true; //DEB(dp1[x][y])DEB(x)DEB(y)END
		//return dp1[x][y];
	}
	if (y<0)return false;
	if (x<0) {
		//DEB(dp1[x][y])DEB(x)DEB(y)END
		return false;
	}
	if (vis1[x][y]) {
		return dp1[x][y];
	}
	else vis1[x][y] = true;


	if (front(x - 1, y) || front(x - 1, y - A[x])) {
		dp1[x][y] = true;
	}
	else dp1[x][y] = false;
	//DEB(dp1[x][y])DEB(x)DEB(y)END
	return dp1[x][y];
}
#if 1
int main() {
	ios_base::sync_with_stdio(false);
	cin >> N >> K;
	ans = N;
	REP(i, N) { cin >> A[i]; }
	sort(A, A + N);
	high = N - 1;
	REP(i, N) {
		bool m = false;
		FOR(j, K - A[i], K) {
			if (j<0)j = 0;
			//if(front(i,j)) m=true;
			REP(k, K) {
				//if(j+k>K)break;
				DEB(i)DEB(j)DEB(k)
					TF(front(i, j))
					TF(dfs(i, k))
					TF(dfs(i, k) && front(i, j))
					END
					if (dfs(i, k) && front(i, j)) {
						ans = i;
						if (i == N - 1)ans = 0;
						m = true;
						break;
					}

			}
			if (m)break;
		}
		if (m)break;
	}

	cout << ans << endl;
}
#else
int main() {
	ios_base::sync_with_stdio(false);
	cin >> N >> K;
	ans = N;
	REP(i, N) { cin >> A[i]; }
	sort(A, A + N);
	REP(i, N) {
		bool m = false;
		REP(k, K) {
			FOR(j, K - A[i] - k, K-k+1) {
				if (j<0)j = 0;
				if (dfs(i+1, k) && front(i-1, j)) {
					//必要
					ans = i;
					//if (i == N - 1)ans = 0;
					m = true;
					break;
				}
			}
			if (m)break;
		}
		if (m)break;
	}
	cout << ans << endl;
}
#endif
//ABC056 AtCoDeer

Submission Info

Judge Result