Submission #3248280

---

Source Code Expand

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
//#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007ll
#define pb push_back
#define fi first
#define se second
#define mk(a, b) make_pair(a, b)
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int N, K, a[5020], sum, ans;
bool dp[5020];

signed main()
{
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + N);
    dp[0] = true;
    for(int i = N - 1; i >= 0; i--){
        bool flag = false;
        for(int j = 0; j < K; j++){
            if(dp[j] && j + sum >= K){
                flag = true;
            }
        }
        if(!flag){
            ans++;
        }
        sum -= a[i];
        for(int j = K - 1; j >= a[i]; j--){
            dp[j] |= dp[j - a[i]];
        }
    }
    cout << ans << endl;

    return 0;
}
/*


*/

Submission Info

Judge Result