Submission #1966279

---

Source Code Expand

/*  ***  In The Name of God ... ***  */ 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;


//#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define endl '\n' 
template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

const int N = 5000 + 10 ;

int n , a [ N ] , k ; 
bool dp [ N ] ;

bool chk ( int mid ) {
	memset ( dp , 0 , sizeof dp ) ;
	dp [ 0 ] = 1 ;
	for ( int i = 1 ; i <= mid ; i++ ) {
		for ( int j = N - 1 ; j >= a [ i ] ; j-- ) {
			dp [ j ] |= dp [ j - a [ i ] ] ; 
		}
	}
	bool isFound = 0 ;
	for ( int i = k - a [ mid ] ; i < k ; i++ )
		isFound |= dp [ i ] ;
	return !isFound ; 
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k ; 
	for ( int i = 1 ; i <= n ; i++ )
		cin >> a [ i ] ;
	sort ( a + 1 , a + n + 1 ) ; 
	int lo = -1 , hi = n + 1 ;
	while ( hi - lo > 1 ) {
		int mid = ( hi + lo ) >> 1 ; 
		( chk ( mid ) ? lo : hi ) = mid ; 
	}
	cout << lo << '\n' ; 
}

Submission Info

Judge Result