結果
問題 | No.2741 Balanced Choice |
ユーザー |
|
提出日時 | 2024-04-20 10:45:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 198,064 KB |
最終ジャッジ日時 | 2025-02-21 06:11:16 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,W,D; cin >> N >> W >> D; vector<pair<int,int>> Q0,Q1; for(int i=0; i<N; i++){ int t,w,v; cin >> t >> w >> v; if(t == 0) Q0.push_back({w,v}); if(t == 1) Q1.push_back({w,v}); } int inf = 1e9; vector<int> dp0(W+1,-inf),dp1(W+1,-inf); dp0.at(0) = 0; dp1.at(0) = 0; for(auto [w,v] : Q0){ for(int i=W; i>=0; i--) if(i+w <= W) dp0.at(i+w) = max(dp0.at(i+w),dp0.at(i)+v); } for(auto [w,v] : Q1){ for(int i=W; i>=0; i--) if(i+w <= W) dp1.at(i+w) = max(dp1.at(i+w),dp1.at(i)+v); } int answer = 0; for(int i=0; i<=W; i++) for(int k=0; k<=W; k++){ if(i+k > W || abs(i-k) > D) continue; answer = max(answer,dp0.at(i)+dp1.at(k)); } cout << answer << endl; }