結果

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

ソースコード

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);
    }

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

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