結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー Andrew8128
提出日時 2025-08-09 16:32:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,849 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 109,848 KB
実行使用メモリ 74,112 KB
最終ジャッジ日時 2025-09-09 17:11:34
合計ジャッジ時間 5,115 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 72 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using std::cerr, std::cin, std::cout, std::endl, std::fixed, std::flush;
#include <vector>
using std::vector;
#include <algorithm>
using std::clamp, std::ranges::count, std::ranges::count_if, std::ranges::fill, std::ranges::find, std::ranges::find_if;
using std::ranges::is_permutation, std::ranges::lower_bound, std::ranges::max, std::ranges::max_element, std::ranges::min;
using std::ranges::min_element, std::ranges::next_permutation, std::ranges::prev_permutation, std::swap_ranges;
using std::ranges::reverse, std::ranges::rotate, std::ranges::sort, std::ranges::unique, std::ranges::upper_bound;
static_assert(sizeof(long) == 8);
int main()
{
  int N, W;
  cin >> N >> W;
  vector<int> v(N);
  vector<int> w(N);
  for (int i = 0; i < N; i++)
  {
    cin >> v[i];
  }
  for (int i = 0; i < N; i++)
  {
    cin >> w[i];
  }
  vector<vector<int>> dp(N + 1, vector<int>(W + 1));
  vector<vector<int>> b(N + 1, vector<int>(W + 1));
  for (int i = N - 1; i >= 0; i--)
  {
    for (int j = 0; j <= W; j++)
    {
      dp[i][j] = dp[i + 1][j];
      b[i][j] = j;
    }
    for (int j = 0; j + w[i] <= W; j++)
    {
      if (dp[i][j + w[i]] < dp[i + 1][j] + v[i])
      {
        dp[i][j + w[i]] = dp[i + 1][j] + v[i];
        b[i][j + w[i]] = j;
      }
    }
  }
  int e = max(dp[0]);
  vector<int> ans;
  for (int i = 0; i <= W; i++)
  {
    if (dp[0][i] == e)
    {
      int i0 = i;
      vector<int> tmp;
      for (int j = 0; j < N; j++)
      {
        if (b[j][i0] != i0)
          tmp.push_back(j);
        i0 = b[j][i0];
      }
      if (ans.empty() || tmp < ans)
        ans = move(tmp);
    }
  }

  cout << size(ans) << '\n';
  for (int i = 0; i < size(ans); i++)
  {
    cout << ans[i] + 1 << ' ';
  }
  cout << '\n';
  return 0;
}
/*
  File : ~/kyopro/yukicoder/iwai2/H.cpp
  Date : 2025/08/09
  Time : 14:42:23
*/
0