AtCoder Weekday Contest 0011 Beta

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N + 1), B(N + 1);
    rep(i, N) cin >> A[i + 1] >> B[i + 1];

    vvll dp(N + 1, vll(M + 1, -INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(j, M + 1) {
            // i 番目の宝を使わない
            chmax(dp[i][j], dp[i - 1][j]);

            // i 番目の宝を使う
            if (j - A[i] < 0) continue;
            if (dp[i - 1][j - A[i]] < 0) continue;
            chmax(dp[i][j], dp[i - 1][j - A[i]] + B[i]);
        }
    }

    vint ans(N + 1);
    ll mxval = *max_element(all(dp[N]));
    set<tuple<int, int, ll>> memo;

    auto dfs = [&](auto dfs, int now, int weight, ll val) -> void {
        if (now == 0) return;
        if (memo.count({now, weight, val})) return;
        memo.insert({now, weight, val});
        // now を使わない
        dfs(dfs, now - 1, weight, val);

        // now を使う
        weight -= A[now];
        val -= B[now];
        if (weight < 0) return;
        if (dp[now - 1][weight] != val) return;
        ans[now] = 1;
        dfs(dfs, now - 1, weight, val);
    };

    rep(w, M + 1) {
        if (dp[N][w] == mxval) dfs(dfs, N, w, mxval);
    }

    rep2(i, 1, N + 1) yesno(ans[i]);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N), B(N);
    rep(i, N) cin >> A[i] >> B[i];

    // dp[i][j]: 1~i 番目の宝を使って重さが j kg 以下のときの価値の最大値
    vvll dp(N + 2, vll(M + 1));

    // dp2[i][j]: i 番目以降の宝を使って重さが j kg 以下のときの価値の最大値
    vvll dp2(N + 2, vll(M + 1));

    rep(_, 2) {
        rep2(i, 1, N + 1) {
            rep(j, M + 1) {
                // i 番目の宝を使わない
                chmax(dp[i][j], dp[i - 1][j]);
                if (j > 0)
                    chmax(dp[i][j], dp[i][j - 1]);

                // i 番目の宝を使う
                if (j - A[i - 1] < 0) continue;
                chmax(dp[i][j], dp[i - 1][j - A[i - 1]] + B[i - 1]);
            }
        }
        swap(dp, dp2);
        reverse(all(A));
        reverse(all(B));
    }
    reverse(all(dp2));

    ll mx = dp[N][M];

    vint ans(N + 1);
    rep2(i, 1, N + 1) {
        rep(w, M + 1) {
            if (M - w - A[i - 1] < 0) continue;
            if (dp[i - 1][w] + B[i - 1] + dp2[i + 1][M - w - A[i - 1]] == mx) {
                ans[i] = 1;
            }
        }
    }

    rep2(i, 1, N + 1) yesno(ans[i]);
}