Submission #1443274

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
int a,b,c,i,j,k[5009],sum[5009],ans=0;
bool solve(int x){
	memset(sum,0,sizeof(sum));
	sum[0]=1;
	for(i=1;i<=a;i++) if(i!=x){
		for(j=b;j>=0;j--){
			if(sum[j] && j+k[i]<=b){
				sum[j+k[i]]=1;
			}
		}
	}
//	for(j=0;j<b;j++){
//		cout<<sum[j]<<' ';
//	}cout<<endl;
	for(j=max(0,b-k[x]);j<b;j++){
		
		if(sum[j]==1){
			return 0;
		}
	}
	return 1;
}
int main(){
	cin>>a>>b;
	int c=0;
	for(i=1;i<=a;i++){
		cin>>k[i];
		c+=k[i];
	}
	if(c<b){
		cout<<a;
		return 0;
	}
	sort(k+1,k+a+1);
//	i=a;
	while(k[i]>b){
		a--;
	}
	int l,r;
	l=1;r=a;
	int m;
//	for(i=1;i<=a;i++){
//		cout<<k[i]<<' ';
//	}cout<<endl;
	while(l<=r){
		m=(l+r)/2;//cout<<m<<endl;
		if(solve(m)){
			ans=max(ans,m);
			l=m+1;
		}else{
			r=m-1;
		}
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result