結果
問題 | 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)1000000007ll 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;}