結果

問題 No.2741 Balanced Choice
コンテスト
ユーザー おぼ
提出日時 2024-04-21 10:24:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,152 bytes
コンパイル時間 1,803 ms
コンパイル使用メモリ 178,692 KB
実行使用メモリ 136,704 KB
最終ジャッジ日時 2024-10-13 09:12:38
合計ジャッジ時間 8,118 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,a,b) for(int i=(a);i<(int)(b);i++)

int main() {
    int n, W, D;
    cin >> n >> W >> D;

    vector<int> t(n), w(n), v(n);
    rep(i,0,n) {
        cin >> t[i] >> w[i] >> v[i];
    }

    vector<map<int,int>> dp(W+1);
    dp[0][0] = 0;

    rep(i,0,n) {
        for(int j=W;j>=w[i];j--) {
            auto it = dp[j - w[i]].begin();
            while (it != dp[j - w[i]].end()) {
                int diff = it->first;
                int new_diff = (t[i] == 0) ? (diff + w[i]) : (diff - w[i]);
                int value = it->second + v[i];
                
                auto& current_map = dp[j];
                auto found = current_map.find(new_diff);
                if (found == current_map.end() || found->second < value) {
                    current_map[new_diff] = value;
                }
                ++it;
            }
        }
    }

    int max_value = 0;
    rep(j,0,W+1) {
        for(auto &p:dp[j]) {
            if(abs(p.first)<=D) {
                max_value=max(max_value,p.second);
            }
        }
    }

    cout << max_value << endl;
    return 0;
}
0