Submission #3226971

---

Source Code Expand

typedef int ll;
#include <bits/stdc++.h>
using namespace std;

ll n,k;
ll a[5010];
bool sum[5010];
// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}


int main() {
    std::cin >> n>>k;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    sort(a,a+n);

    ll r = n-1;
    ll l = -1;
    ll i = r;
    while(r-l>1){
        // iだけがいない街
        bool sum[5010][5010];
      	Fill(sum,false);
      	sum[0][0]=true;
        for (int l = 0; l < n; l++) {
            for (int j = 0; j <= k; j++) {
                if(sum[l][j]){
                    sum[l+1][j] = true;
                    if(j+a[l]<=k && i!=l){
                        sum[l+1][j+a[l]]=true;
                    }
                }
            }
        }
      	sum[n][0]=false;
        
        bool flag = false;
      
        for (int c = 1; c <= min(a[i],k); c++) {
            if(sum[n][k-c]){
                flag = true;
                break;
            }
        }
        if(i==r && !flag){
          cout<<n<<endl;
            return 0;
        }else if(i==r){
            i = (r+l)/2;
        }else{
            (flag ? r : l ) = i;
            i = (r+l)/2;
        }
    }
    std::cout << l+1 << std::endl;
}

Submission Info

Judge Result