結果
問題 |
No.2856 Junk Market Game
|
ユーザー |
|
提出日時 | 2024-08-25 14:43:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,670 ms / 2,000 ms |
コード長 | 1,000 bytes |
コンパイル時間 | 4,125 ms |
コンパイル使用メモリ | 294,480 KB |
実行使用メモリ | 504,320 KB |
最終ジャッジ日時 | 2024-08-25 14:44:23 |
合計ジャッジ時間 | 55,253 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ int N; cin >> N; int n2 = N*2; vector<ll> A(n2); for(int i=0; i<n2; i++){ cin >> A[i]; } vector<ll> B(n2); for(int i=0; i<n2; i++){ cin >> B[i]; } vector<int> idx(n2); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j) -> bool{ return A[i]+B[i] < A[j]+B[j]; }); vector seen(n2+1, vector(n2+1, vector<bool>(2))); vector memo(n2+1, vector(n2+1, vector<ll>(2))); auto dp = [&](auto& dp, int l, int r, bool f) -> ll{ if(!seen[l][r][f]){ seen[l][r][f] = true; if(r-l==1){ if(f){ memo[l][r][f] = A[idx[l]]; }else{ memo[l][r][f] = -B[idx[l]]; } }else{ if(f){ memo[l][r][f] = min(dp(dp,l+1,r,!f)+A[idx[l]], dp(dp,l,r-1,!f)+A[idx[r-1]]); }else{ memo[l][r][f] = max(dp(dp,l+1,r,!f)-B[idx[l]], dp(dp,l,r-1,!f)-B[idx[r-1]]); } } } return memo[l][r][f]; }; cout << dp(dp, 0, n2, true) << endl; return 0; }