結果

問題 No.3289 Make More Happy Connection
ユーザー Facade
提出日時 2025-10-03 22:51:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,029 bytes
コンパイル時間 2,926 ms
コンパイル使用メモリ 281,456 KB
実行使用メモリ 24,356 KB
最終ジャッジ日時 2025-10-03 22:52:06
合計ジャッジ時間 8,983 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
signed  main(){
    int n;cin>>n;
    vector<int>x(n),y(n);
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    vector<vector<int>>dp(n+1,vector<int>(2,-inf));
    dp[0][0]=0;
    dp[0][1]=0;
    //0->nothing 1->fliped
    // int mx=0;
    // vector<pair<int,string>>ans;
    // for(int bit=0;bit<(1<<n);bit++){
    //     set<int>ch;
    //     string now="";
    //     for(int i=0;i<n;i++){
    //         if(bit&(1<<i)){
    //             now+='1';
    //             ch.insert(i);
    //         }else{
    //             now+='0';
    //         }
    //     }
    //     vector<int>que;
    //     for(int i=0;i<n;i++){
    //         if(ch.find(i)==ch.end()){
    //             que.push_back(x[i]);
    //             que.push_back(y[i]);
    //         }else{
    //             que.push_back(y[i]);
    //             que.push_back(x[i]);
    //         }
    //     }
    //     int cnt=0;
    //     for(int i=0;i<2*n-1;i++){
    //         if(que[i]==que[i+1]){
    //             cnt+=que[i];
    //         }
    //     }
    //     ans.push_back({cnt,now});
    // }
    // sort(ans.begin(),ans.end());
    // while(!ans.empty()){
    //     auto[sc,vc]=ans.back();
    //     ans.pop_back();
    //     cout<<"score -> "<<sc<<" "<<vc<<endl;
    // }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]);
            }
        }
        {//j=0
            if(y[i]==y[i+1]){
                dp[i+1][1]=max(dp[i+1][1],dp[i][0]+y[i]);
            }
            if(y[i]==x[i+1]){
                dp[i+1][0]=max(dp[i+1][0],dp[i][0]+y[i]);
            }

        }
        {//j=1
            if(x[i]==x[i+1]){
                dp[i+1][0]=max(dp[i+1][0],dp[i][1]+x[i]);
            }
            if(x[i]==y[i+1]){
                dp[i+1][1]=max(dp[i+1][1],dp[i][1]+x[i]);
            }
        }
    }
    cout<<max(dp[n-1][0],dp[n-1][1])<<endl;
}
0