結果

問題 No.3049 Contest Coordinator
コンテスト
ユーザー suisen
提出日時 2025-01-18 15:57:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,458 bytes
コンパイル時間 3,848 ms
コンパイル使用メモリ 81,156 KB
実行使用メモリ 208,052 KB
最終ジャッジ日時 2025-01-18 15:57:54
合計ジャッジ時間 19,177 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 RE * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

// naive

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

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

    int n, t, x, y;
    std::cin >> n >> t >> x >> y;

    std::vector<int> d(n);
    for (auto& e : d) std::cin >> e;

    assert(n <= 20);

    std::vector cost(n, std::vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i] + t < d[j]) {
                cost[i][j] = x;
            } else if (d[i] > d[j]) {
                cost[i][j] = y;
            } else {
                cost[i][j] = 0;
            }
        }
    }

    std::vector dp(1 << n, std::vector<long long>(n, 1e18));
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = 0;
    }

    for (int s = 1; s < 1 << n; ++s) {
        for (int i = 0; i < n; ++i) if ((s >> i) & 1) {
            for (int j = 0; j < n; ++j) if (not ((s >> j) & 1)) {
                int ns = s | 1 << j;
                dp[ns][j] = std::min(dp[ns][j], dp[s][i] + cost[i][j]);
            }
        }
    }

    std::vector<long long> ans(n + 1, 1e18);
    for (int s = 1; s < 1 << n; ++s) {
        int cnt = __builtin_popcount(s);
        for (int i = 0; i < n; ++i) {
            ans[cnt] = std::min(ans[cnt], dp[s][i]);
        }
    }
    for (int k = 1; k <= n; ++k) {
        if (k != 1) std::cout << ' ';
        std::cout << ans[k];
    }
    std::cout << std::endl;
}
0