Submission #1631478

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<cstring>
#include<vector>
#include <type_traits>
typedef long long int ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef pair<ll, ll>P;
template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

ll par[100000], depth[100000];
static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}
#define yo 100001
typedef pair<double, double> dop;
//------------------変数-----------------------//
ll n, k,a[10000];
ll dp[5001];
//-------------------関数----------------------//
int main() {
	cin >> n >> k;
	ll bwam = 0;
	REP(i, n) { cin >> a[i]; bwam += a[i]; }
	if (bwam < k) { cout << n << endl; return 0; }
	sort(a, a + n);
	fill_all(dp, INF);
	dp[0] = 0;
	ll mini = INF;
	for (ll i = n-1; i >=0; i--)
	{
		for (ll j = 5000; j >=0; j--)
		{
			if (dp[j] < INF) {
				if (j + a[i] >= k) {
					mini = min(mini, a[i]);
				}
				else {
					dp[j + a[i]] = 0;
				}
			}
		}
	}
	//cout << mini << endl;
	ll cnt = 0;
	REP(i, n) {
		if (a[i] < mini) { cnt++; }
	}
	cout << cnt << endl;
	return 0;
}

Submission Info

Judge Result