結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー iastm
提出日時 2025-11-01 16:55:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,341 bytes
コンパイル時間 953 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 214,656 KB
最終ジャッジ日時 2025-11-01 16:55:45
合計ジャッジ時間 9,036 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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, {-1LL << 60, -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] + 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);
    }

    std::vector<int> result;
    for (int64_t w = X; w >= 0; w--) {
        if (dp.back()[w][0] < 0) 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