結果
問題 |
No.3289 Make More Happy Connection
|
ユーザー |
|
提出日時 | 2025-10-05 18:15:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 2,280 bytes |
コンパイル時間 | 3,075 ms |
コンパイル使用メモリ | 283,244 KB |
実行使用メモリ | 28,992 KB |
最終ジャッジ日時 | 2025-10-05 18:15:32 |
合計ジャッジ時間 | 6,437 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #define int long long using namespace std; const int inf = (int)4e18; int solve(int n, vector<int> x, vector<int> y){ vector<vector<int>> dp(n, vector<int>(2, -inf)); // 初期化: 最初のペアの内部スコアは共通 int base0 = (x[0] == y[0] ? x[0] : 0); dp[0][0] = base0; // order 0: (x,y) dp[0][1] = base0; // order 1: (y,x) for(int i = 0; i < n-1; i++){ // 次を初期化(既に -inf にしてあるので不用だが明示的にしてもよい) // dp[i+1][*] は既に -inf int inner = (x[i+1] == y[i+1] ? x[i+1] : 0); // pair i+1 の内部得点(必ず加える) // k = 0 or 1 : order chosen for pair i for(int k = 0; k < 2; k++){ if(dp[i][k] <= -inf/2) continue; int last_of_i = (k == 0 ? y[i] : x[i]); // pair i の最後の要素 // j = 0 or 1 : order chosen for pair i+1 for(int j = 0; j < 2; j++){ int first_of_next = (j == 0 ? x[i+1] : y[i+1]); // pair i+1 の最初の要素 int add = 0; if(last_of_i == first_of_next) add += last_of_i; // 境界 int val = dp[i][k] + inner + add; dp[i+1][j] = max(dp[i+1][j], val); } } } return max(dp[n-1][0], dp[n-1][1]); } int naive(int n, vector<int> x, vector<int> y){//O(N * 2^N) but fine for small tests int mx = 0; for(int bit=0; bit < (1<<n); ++bit){ vector<int> A; A.reserve(2*n); for(int i=0;i<n;i++){ if(bit & (1<<i)){ A.push_back(y[i]); A.push_back(x[i]); } else { A.push_back(x[i]); A.push_back(y[i]); } } int cnt = 0; for(int i=0;i<2*n-1;i++){ if(A[i] == A[i+1]) cnt += A[i]; } mx = max(mx, cnt); } return mx; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> x(n), y(n); for(int i=0;i<n;i++) cin >> x[i] >> y[i]; int sol = solve(n,x,y); //int nai = naive(n,x,y); //if(sol != nai) cerr << "Mismatch sol=" << sol << " naive=" << nai << "\n"; cout << sol << "\n"; return 0; }