#include #define int long long using namespace std; const int inf = (int)4e18; int solve(int n, vector x, vector y){ vector> dp(n, vector(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 x, vector y){//O(N * 2^N) but fine for small tests int mx = 0; for(int bit=0; bit < (1< A; A.reserve(2*n); for(int i=0;i> n; vector x(n), y(n); for(int i=0;i> 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; }