Yukicoder No.617 Nafmo、買い出しに行く

実行速度がどうこうと言っていたので解いたが面倒そうだったので自明bitset解を書いて終了。

solution

部分和問題のようにしてDP。$O(NK)$

implementation

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

constexpr int max_k = 2e6;
int main() {
    int n, k; scanf("%d%d", &n, &k);
    assert (k <= max_k);
    bitset<max_k + 1> dp;
    dp[0] = true;
    while (n --) {
        int a_i; scanf("%d", &a_i);
        dp |= dp << a_i;
    }
    while (not dp[k]) k --;
    printf("%d\n", k);
    return 0;
}