Submission #1168369

---

Source Code Expand

#include <iostream>
#include <cstring>

using ll = long long;
int n, k;
int a[5010];
bool stat[5010];

ll dp[5010][5100];

ll dfs(int idx, ll sum) {
    if(sum >= k) {
        return sum;
    }
    if(idx >= n) {
        return 0;
    }
    if(dp[idx][sum] != -1) {
        return dp[idx][sum];
    }

    ll min = 1e18;
    for(int i = idx; i < n; ++i) {
        auto r = dfs(i + 1, sum + a[i]);

        if(r != 0) {
            if(r - a[i] < k) {
//                std::cout << idx << " " << i << " " << sum << " " << r << std::endl;
                stat[i] = true;
            }
            min = std::min(min, r);
        }
    }

    if(min == 1e18) {
        return dp[idx][sum] = 0;
    }
    return dp[idx][sum] = min;
}

int main() {
    memset(dp, -1, sizeof(dp));
    std::cin >> n >> k;

    for(int i = 0; i < n; ++i)
        std::cin >> a[i];

    dfs(0, 0);

    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        if(stat[i])
            ++cnt;
    }

    std::cout << n - cnt << std::endl;
}

Submission Info

Judge Result