結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー iastm
提出日時 2025-11-01 17:13:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,493 bytes
コンパイル時間 1,241 ms
コンパイル使用メモリ 95,916 KB
実行使用メモリ 214,784 KB
最終ジャッジ日時 2025-11-01 17:13:17
合計ジャッジ時間 9,547 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <array>

int main() {
    int64_t N, X;
    std::cin >> N >> X;
    std::vector<int64_t> V(N);
    std::vector<int64_t> W(N);
    for (int64_t &v : V) std::cin >> v;
    for (int64_t &w : W) std::cin >> w;

    std::vector<std::vector<std::array<int64_t, 3>>> dp(1, std::vector<std::array<int64_t, 3>>(X + 1, {-1, -1, -1}));
    dp[0][0] = {0, -1, -1};
    for (int i = N - 1; i >= 0; i--) {
        std::vector<std::array<int64_t, 3>> ndp = dp.back();
        for (int64_t w = X - W[i]; w >= 0; w--) {
            if (dp.back()[w][0] == -1) continue;
            if (dp.back()[w][0] + V[i] > ndp[w + W[i]][0] || dp.back()[w][0] + V[i] == ndp[w + W[i]][0] && ndp[w + W[i]][1] == i && dp.back()[w][1] > ndp[w + W[i]][2]) {
                ndp[w + W[i]] = {dp.back()[w][0] + V[i], i, dp.back()[w][1]};
            }
        }
        dp.push_back(ndp);
    }

    std::vector<int> result;
    for (int64_t w = X; w >= 0; w--) {
        if (dp.back()[w][0] == -1) continue;
        int target = dp.back()[w][1];
        while (target != -1) {
            if (dp.back()[w][1] == target) {
                result.push_back(target + 1);
                target = dp.back()[w][2];
                int64_t nw = w - W[dp.back()[w][1]];
                w = nw;
            }
            dp.pop_back();
        }
        break;
    }

    std::cout << result.size() << std::endl;
    for (int r : result) std::cout << r << ' ';
    std::cout << std::endl;
}
0