結果

問題 No.2741 Balanced Choice
コンテスト
ユーザー ringo
提出日時 2024-04-20 12:12:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,801 bytes
コンパイル時間 2,177 ms
コンパイル使用メモリ 194,092 KB
実行使用メモリ 512,172 KB
最終ジャッジ日時 2024-10-12 07:29:29
合計ジャッジ時間 8,445 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
typedef long long ll;
#define rep1(i, m, n) for(int i = m; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i <= (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if(a < b) {a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if(a > b) {a = b; return true; } return false; }
const ll INF = 1LL << 60;
//#define _GLIBCXX_DEBUG
// 範囲外エラーを教えてくれる。使うときはincludeより上に置く。
 
// const char newl='\n';

int main() {
  int n,sw,d;
  cin >> n >> sw >> d;
  vector<int> t(n),w(n),v(n);
  for (int i=0; i<n; i++) cin >> t[i] >> w[i] >> v[i];
  map<int,map<int,map<int,int>>> dp;
  dp[0][0][0]=0;
  for (int i=0; i<n; i++) {
    for (auto x:dp[i]) {
      int j=x.first;
      for (auto y:x.second) {
        int k=y.first;
        if (!dp[i+1][j].count(k)) dp[i+1][j][k]=0;
        chmax(dp[i+1][j][k],dp[i][j][k]);
        if (t[i]==0) {
          if (j+k+w[i]>sw) continue;
          if (!dp[i+1][j+w[i]].count(k)) dp[i+1][j+w[i]][k]=0;
          chmax(dp[i+1][j+w[i]][k],dp[i][j][k]+v[i]);
        }
        if (t[i]==1) {
          if (j+k+w[i]>sw) continue;
          if (!dp[i+1][j].count(k+w[i])) dp[i+1][j][k+w[i]]=0;
          chmax(dp[i+1][j][k+w[i]],dp[i][j][k]+v[i]);
        }
      }
    }
  }
  /*
  for (int i=0; i<=n; i++) {
    cout << i << endl;
    for (auto x:dp[i]) {
      for (auto y:x.second) {
        cout << x.first << " " << y.first << " " << y.second << endl;
      }
    }
  }
  */
  int ans=0;
  for (auto x:dp[n]) {
    for (auto y:x.second) {
      if (abs(x.first-y.first)<=d) chmax(ans,y.second);
    }
  }
  cout << ans << endl;
}
0