はまやんはまやんはまやん

hamayanhamayan's blog

引き算をして門松列(その2) [yukicoder 967]

https://yukicoder.me/problems/no/967

解説

https://yukicoder.me/submissions/417569

1つ前の下位互換の問題での方針ガチャによっては、ちょっと拡張するだけでこの問題が解ける。
(というか、この問題が解ければ、下位互換も同様に解ける)

min,mid,maxを全探索して、かかるコストを計算していこう。
前の解法がわかっていれば、この問題を解くのは難しくないだろう。
数が結構でかいので、long longじゃないとダメ。

int A[3], C[3];
//---------------------------------------------------------------------------------------------------
void solve() {
    rep(i, 0, 3) cin >> A[i];
    rep(i, 0, 3) cin >> C[i];

    ll ans = infl;

    vector<int> ord;
    rep(i, 0, 3) ord.push_back(i);
    do {
        if (ord[1] == 1) continue;
        int pre = A[ord[0]];
        ll tot = 0;
        rep(i, 1, 3) {
            int nxt = min(A[ord[i]], pre - 1);
            tot += 1LL * (A[ord[i]] - nxt) * C[ord[i]];
            pre = nxt;
        }
        if (0 < pre) chmin(ans, tot);
    } while (next_permutation(all(ord)));

    if (ans == infl) ans = -1;
    printf("%lld\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}