Submission #1748455

---

Source Code Expand

#include <bits/stdc++.h>
#define N 6010
using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n,k,tmp,F[N],a[N];
inline bool check(int x)
{
	if(a[x]>=k) return 1;
	memset(F,0,sizeof F); F[0]=1;
	for(int i=1;i<=n;i++) if(i!=x)
		for(int j=k;j>=a[i];j--)
			F[j]|=F[j-a[i]];
	for(int i=k-a[x];i<k;i++)
		if(F[i]) return 1;
	return 0;
}
int main()
{
	F[0]=1; n=read(); k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	int ans=0;
	int l=1,r=n; while(l<=r)
	{
		int mid=(l+r)>>1;
		if(!check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result