提出 #67889585

---

ソースコード 拡げる

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

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n;
  cin >> n;

  // w+sの値でソートしたいので、4つ組にする
  vector<tuple<int,int,int,int>> a(n);
  for (int i=0; i<n; i++) {
    int w, s, v;
    cin >> w >> s >> v;
    a.at(i) = {w+s,w,s,v};
  }

  //////////////// 出力変数定義 ////////////////

  long long result = 0;

  //////////////////// 処理 ////////////////////

  // w+sが小さい順にソートしておく
  sort(a.begin(),a.end());

  // DPテーブル
  // dp.at(i).at(j)は、i番目まで使う場合の総重量jでの最大価値
  vector<vector<long long>> dp(n+1,vector<long long>(get<0>(a.back())+1,-1e18));
  dp.at(0).at(0) = 0;

  // w+sが小さい順にDP
  for (int i=0; i<n; i++) {

    auto [ws,w,s,v] = a.at(i);

    // とりあえず、それを使わない場合のを全部コピー
    dp.at(i+1) = dp.at(i);

    // 注目の荷物の上に載せられるやつパターン全部処理
    for (int j=0; j<=s; j++) {
      dp.at(i+1).at(j+w) = max(dp.at(i+1).at(j+w),dp.at(i).at(j)+v);
    }

  }

  // 全部使う場合の任意の重さでの最大価値が答え
  result = *max_element(dp.at(n).begin(),dp.at(n).end());

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

提出情報

ジャッジ結果