結果

問題 No.3097 Azuki Kurai
ユーザー RiRinbaru
提出日時 2025-03-29 04:50:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,449 bytes
コンパイル時間 3,740 ms
コンパイル使用メモリ 222,460 KB
実行使用メモリ 20,736 KB
最終ジャッジ日時 2025-03-29 04:50:25
合計ジャッジ時間 11,982 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, p, n) for (ll i = p; i < (ll)(n); i++)
#define rep2(i, p, n) for (ll i = p; i >= (ll)(n); i--)
using namespace std;
using ll = long long;
using ld = long double;
const double pi = 3.141592653589793;
const long long inf = 2 * 1e9;
const long long linf = 4 * 1e18;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;

// atcoder
#include <atcoder/all>
using namespace atcoder;
using mint1 = modint1000000007;
using mint2 = modint998244353;

constexpr int MAX_N = 10;
constexpr int MAX_M = 2000;
constexpr int MAX_STATES = (1 << MAX_N);

array<pair<ll, ll>, 4> base = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll N, M, K;
    cin >> N >> M >> K;

    ll A[MAX_N];
    rep(i, 0, N) {
        cin >> A[i];
    }

    ll dp[MAX_M + 1][MAX_STATES];
    rep(i, 0, M + 1) rep(j, 0, MAX_STATES) dp[i][j] = linf;

    rep(i, 0, (1 << N)) {
        dp[0][i] = 0;
        rep(j, 0, N) {
            if (!(i & (1 << j))) {
                dp[0][i] += A[j];
            }
        }
    }

    ll pl[MAX_STATES][MAX_N + 1];
    ll mae[MAX_N][MAX_STATES][MAX_N + 1];

    rep(i, 0, (1 << N)) {
        int F = 0;
        for (ll c = i; c; c = (c - 1) & i) {
            pl[i][F++] = (__builtin_popcount(i) - __builtin_popcount(c)) * K;
        }
        pl[i][F] = (__builtin_popcount(i) - __builtin_popcount(0)) * K;
    }

    rep(p, 0, N) {
        rep(i, 0, (1 << N)) {
            int F = 0;
            for (ll c = i; c; c = (c - 1) & i) {
                ll now = i;
                now |= ((c * 2) - ((c * 2) & (1 << N)));
                now |= (((c * 2) & (1 << N)) >> N);
                now |= (c / 2);
                now |= (c % 2) * (1 << (N - 1));
                now -= (now & (1 << p));
                mae[p][i][F++] = now;
            }
            ll now = i;
            now -= (now & (1 << p));
            mae[p][i][F] = now;
        }
    }

    rep(p, 0, M) {
        ll B;
        cin >> B;
        B--;
        rep(i, 0, (1 << N)) {
            ll F = 0;
            for (ll c = i; c; c = (c - 1) & i) {
                dp[p + 1][mae[B][i][F]] = min(dp[p + 1][mae[B][i][F]], dp[p][i] + pl[i][F]);
                F++;
            }
            dp[p + 1][mae[B][i][F]] = min(dp[p + 1][mae[B][i][F]], dp[p][i] + pl[i][F]);
        }
    }

    rep(i, 0, M) {
        cout << dp[i + 1][0] << endl;
    }
}
0