結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー iastm
提出日時 2025-11-01 17:36:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 205 ms / 1,571 ms
コード長 1,427 bytes
コンパイル時間 979 ms
コンパイル使用メモリ 98,120 KB
実行使用メモリ 214,528 KB
最終ジャッジ日時 2025-11-02 16:32:39
合計ジャッジ時間 8,882 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main() {
    int N, X;
    std::cin >> N >> X;
    std::vector<int64_t> V(N);
    std::vector<int> W(N);
    for (int64_t &v : V) std::cin >> v;
    for (int &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 (int w = X - W[i]; w >= 0; w--) {
            if (dp.back()[w][0] == -1) continue;
            if (ndp[w + W[i]][0] == -1 || dp.back()[w][0] + V[i] > ndp[w + W[i]][0]) {
                ndp[w + W[i]] = {dp.back()[w][0] + V[i], i, dp.back()[w][1]};
            }
        }
        dp.push_back(ndp);
    }

    int w = X;
    for (int x = X; x >= 0; x--) {
        if (dp.back()[x][0] > dp.back()[w][0] || dp.back()[x][0] == dp.back()[w][0] && dp.back()[x][1] > dp.back()[w][1]) {
            w = x;
        }
    }

    std::vector<int> result;
    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];
            w -= W[dp.back()[w][1]];
        }
        dp.pop_back();
    }

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