結果
問題 | No.2856 Junk Market Game |
ユーザー |
![]() |
提出日時 | 2024-08-25 15:19:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,631 bytes |
コンパイル時間 | 5,903 ms |
コンパイル使用メモリ | 337,440 KB |
実行使用メモリ | 58,368 KB |
最終ジャッジ日時 | 2024-08-25 15:19:33 |
合計ジャッジ時間 | 11,837 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 WA * 50 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define chmin(x,y) (x) = min((x),(y))#define chmax(x,y) (x) = max((x),(y))using namespace std;using namespace atcoder;using ll = long long;const ll mod = 998244353;using mint = modint998244353;using Graph = vector<vector<int>>;const vector<int> dx ={1,0,-1,0}, dy = {0,1,0,-1};long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}int main() {// inputint N; cin >> N;vector<ll> A(2*N),B(2*N);for(int i = 0; i < 2*N; i++) cin >> A[i];for(int i = 0; i < 2*N; i++) cin >> B[i];// solve: Kukan DP O(N^2)vector<vector<vector<ll>>> dp(N+1,vector<vector<ll>>(N+1,vector<ll>(3)));for(int i = 0; i < N; i++){if(A[2*i] - B[2*i+1] <= A[2*i+1] - B[2*i])dp[i][i+1] = {A[2*i] - B[2*i+1], 2*i, 2*i+1};elsedp[i][i+1] = {A[2*i+1] - B[2*i], 2*i+1, 2*i};}for(int d = 2; d <= N; d++){for(int l = 0; l + d <= N; l++){int r = l+d;dp[l][r] = dp[l][r-1];dp[l][r][0] += dp[r-1][r][0];int swp1 = dp[l][r-1][2], swp2 = dp[r-1][r][1];ll X = dp[l][r][0] + B[swp1] - B[swp2] - A[swp2] + A[swp1];int swp3 = dp[r-1][r][2], swp4 = dp[l][r-1][1];ll Y = dp[l][r][0] + B[swp3] - B[swp4] - A[swp4] + A[swp3];if(min(X,Y) > dp[l][r][0]){if(min(X,Y) == X)dp[l][r] = {X,dp[l][r-1][1],swp2};elsedp[l][r] = {Y,dp[r-1][r][1],swp4};}}}// outputcout << dp[0][N][0] << endl;}