ABC 431

Mon, Dec 29, 2025

https://atcoder.jp/contests/abc431

A. Robot Balance

https://atcoder.jp/contests/abc431/tasks/abc431_a

B. Robot Weight

https://atcoder.jp/contests/abc431/tasks/abc431_b

C. Robot Factory

https://atcoder.jp/contests/abc431/tasks/abc431_c

D. Robot Customize

https://atcoder.jp/contests/abc431/tasks/abc431_d

すべてのパーツを体につけることはできるので嬉しさは $\sum_i B_i$ 以上であることが言える。

すべてのパーツを体につけたあとにいくつかを頭に付け替えることで嬉しさを最大化させたい。例えば $i$ 番目のパーツを頭に付け替えると、嬉しさは $H_i - B_i$ 変化する。

$V_i = H_i - B_i$ とし、重さの和が $w$ のときの $V_i$ の和の最大値を dp を使って求める。

$w \leq \frac{\sum_i W_i}{2}$ を満たす$w$ について、$dp[w] + \sum_i B_i$ の最大値が答えとなる。

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

    ll N;
    cin >> N;
    vll W(N), H(N), B(N);
    rep(i, N) cin >> W[i] >> H[i] >> B[i];

    ll sumb = accumulate(all(B), 0ll);
    ll sumw = accumulate(all(W), 0ll);

    vll dp(500 * 500 + 5, -INF);
    dp[0] = 0;
    rep(k, N) {
        ll w = W[k], h = H[k], b = B[k];
        for (ll i = 500 * 500; i > 0; i--) {
            if (i - w < 0) continue;
            if (dp[i - w] == -INF) continue;
            chmax(dp[i], dp[i - w] + h - b);
        }
    }

    ll ans = sumb;
    rep(w, sumw / 2 + 1) {
        chmax(ans, dp[w] + sumb);
    }
    cout << ans << endl;
}