結果
問題 | No.2741 Balanced Choice |
ユーザー |
|
提出日時 | 2024-04-15 19:05:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 411 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 2,257 ms |
コンパイル使用メモリ | 199,784 KB |
最終ジャッジ日時 | 2025-02-21 02:12:10 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define REP(i, n) for(ll i = 0;i < n;i++) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) #define FORR(i, m, n) for(ll i = m;i >= n;i--) #define REPO(i, n) for(ll i = 1;i <= n;i++) #define ll long long #define INF (ll)1ll << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(),n.end() #define MOD (ll)1000000007 ll xN, yN, ans; vector<ll> xw, xv, yw, yv; vector<vector<ll>> dpx(5100, vector<ll>(5100, MINF)), dpy(5100, vector<ll>(5100, MINF)); int main(){ ll N, w, d; cin >> N >> w >> d; dpx[0][0] = 0; dpy[0][0] = 0; REP(i, N){ ll t, a, b; cin >> t >> a >> b; if(t){ xN++; xw.push_back(a); xv.push_back(b); } else { yN++; yw.push_back(a); yv.push_back(b); } } REP(i, xN){ REP(j, w){ if (j + xw[i] <= w) dpx[i + 1][j + xw[i]] = max(dpx[i + 1][j + xw[i]], dpx[i][j] + xv[i]); dpx[i + 1][j] = max(dpx[i + 1][j], dpx[i][j]); } } REP(i, yN){ REP(j, w){ if (j + yw[i] <= w) dpy[i + 1][j + yw[i]] = max(dpy[i + 1][j + yw[i]], dpy[i][j] + yv[i]); dpy[i + 1][j] = max(dpy[i + 1][j], dpy[i][j]); } } REP(i, w + 1){ REP(j, w + 1){ if (i + j > w) break; if (abs(i - j) <= d) { ans = max(ans, dpx[xN][i] + dpy[yN][j]); } } } cout << ans << endl; }