結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー のらら
提出日時 2025-08-08 21:57:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,391 bytes
コンパイル時間 3,268 ms
コンパイル使用メモリ 179,180 KB
実行使用メモリ 814,460 KB
最終ジャッジ日時 2025-09-09 17:09:46
合計ジャッジ時間 5,243 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 73
権限があれば一括ダウンロードができます

ソースコード

diff # 

//解を持ってdpする
//MLEするかな
#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
const long long INF = 1000000000000000000;
ll N, W, v[3009], w[3009];
ll dp[3009][3009];
vector<ll> dpv[3009][3009];

int main(){
  cin >> N >> W;
  for(int i = 1; i <= N; i++) cin >> v[i];
  for(int i = 1; i <= N; i++) cin >> w[i];
  for(int i = 0; i <= N; i++){
    for(int j = 0; j <= W; j++){
      dp[i][j] = -INF;
    }
  }
  dp[N][0] = 0;
  for(int i = N; i >= 1; i--){
    for(int j = 0; j <= W; j++){
      if(dp[i][j] == -INF) continue;
      if(j + w[i] <= W){
        if(dp[i - 1][j + w[i]] == dp[i][j] + v[i]){
          //前の方が右に寄っている
        }
        if(dp[i - 1][j + w[i]] < dp[i][j] + v[i]){
          dp[i - 1][j + w[i]] = dp[i][j] + v[i];
          dpv[i - 1][j + w[i]] = dpv[i][j];
          dpv[i - 1][j + w[i]].push_back(i);
        }
      }
      if(dp[i - 1][j] <= dp[i][j]){
        dp[i - 1][j] = dp[i][j];
        dpv[i - 1][j] = dpv[i][j];
      }
    }
  }
  
  ll maxval = 0;
  vector<ll> ans;
  for(int j = 0; j <= W; j++){
    if(maxval < dp[0][j]){
      maxval = dp[0][j];
      ans = dpv[0][j];
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans.size() << endl;
  for(auto p: ans) cout << p << " ";
  cout << endl;
  return 0;
}
0