結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー bolero
提出日時 2025-08-16 14:57:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 1,571 ms
コード長 1,748 bytes
コンパイル時間 2,895 ms
コンパイル使用メモリ 288,284 KB
実行使用メモリ 144,128 KB
最終ジャッジ日時 2025-11-02 16:31:07
合計ジャッジ時間 9,039 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
    long long N, W;
    cin >> N >> W;

    vector<array<long long, 2>> vw(N);
    rep(i, N)
    {
        cin >> vw[i][0];
    }
    rep(i, N)
    {
        cin >> vw[i][1];
    }

    reverse(vw.begin(), vw.end());

    vector dp(N + 1, vector<pair<long long, int>>(W + 1, {-1, -1}));

    dp[0][0] = {0, -1};

    rep(i, N) rep(now_w, W + 1)
    {
        if (dp[i][now_w].first == -1)
        {
            continue;
        }

        // i番目のアクスタを使わない
        if (dp[i + 1][now_w].first <= dp[i][now_w].first)
        {
            dp[i + 1][now_w] = dp[i][now_w];
        }

        // i番目のアクスタを使う
        auto [v, w] = vw[i];
        long long next_v = dp[i][now_w].first + v;
        long long next_w = now_w + w;
        if (next_w <= W && dp[i + 1][next_w].first < next_v)
        {
            dp[i + 1][next_w] = {next_v, i};
        }
    }

    vector<int> ans = {-1};
    long long max_v = 0;
    long long now_w = 0;
    rep(w, W + 1)
    {
        if (max_v < dp[N][w].first)
        {
            max_v = dp[N][w].first;
            now_w = w;
            ans = {dp[N][w].second};
        }
        else if (max_v == dp[N][w].first && dp[N][w].second <= ans.back())
        {
            max_v = dp[N][w].first;
            now_w = w;
            ans = {dp[N][w].second};
        }
    }

    while (ans.back() != -1)
    {
        now_w -= vw[ans.back()][1];
        ans.push_back(dp[ans.back()][now_w].second);
    }

    ans.pop_back();

    cout << ans.size() << endl;
    for (auto n : ans)
    {
        cout << N - n << " ";
    }
    cout << endl;

    return 0;
}
0