結果

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

ソースコード

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_element(dp[0]) - dp[0].begin();
  vector<int> ans;
  for (int i = 0; i < N; i++)
  {
    cout << i << ' ' << e << '\n';
    if (b[i][e] != e)
      ans.push_back(i);
    e = b[i][e];
  }
  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