結果

問題 No.3289 Make More Happy Connection
コンテスト
ユーザー Facade
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0