結果

問題 No.3289 Make More Happy Connection
コンテスト
ユーザー Facade
提出日時 2025-10-05 18:01:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,559 bytes
コンパイル時間 3,416 ms
コンパイル使用メモリ 291,984 KB
実行使用メモリ 28,968 KB
最終ジャッジ日時 2025-10-05 18:01:57
合計ジャッジ時間 9,665 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
int solve(int n,vector<int>x,vector<int>y){
    vector<vector<int>>dp(n+1,vector<int>(2,-inf));
    int fi=0;
    if(x[0]==y[0])fi=x[0];
    dp[0][0]=fi;
    dp[0][1]=fi;
    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
            int fi=0;
            if(x[i+1]==y[i+1])fi=x[i+1];
            if(y[i]==y[i+1]){
                dp[i+1][1]=max(dp[i+1][1],dp[i][0]+y[i]+fi);
            }
            if(y[i]==x[i+1]){
                dp[i+1][0]=max(dp[i+1][0],dp[i][0]+y[i]+fi);
            }
        }
        {//j=1
            int fi=0;
            if(x[i+1]==y[i+1])fi=x[i+1];
            if(x[i]==x[i+1]){
                dp[i+1][0]=max(dp[i+1][0],dp[i][1]+x[i]+fi);
            }
            if(x[i]==y[i+1]){
                dp[i+1][1]=max(dp[i+1][1],dp[i][1]+x[i]+fi);
            }
        }
    }
    if(x[n-1]==y[n-1]){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                dp[n-1][j]=max(dp[n-1][j],dp[n-2][k]+x[n-1]);
            }
        }
    }
    return max(dp[n-1][0],dp[n-1][1]);
}
int naive(int n,vector<int>x,vector<int>y){//O(N^2)
    int ret=0;
    string ans="";
    int mx=0;
    for(int bit=0;bit<(1<<n);bit++){
        string now="";
        unordered_set<int>ch;
        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];
            }
        }
        if(cnt>mx){
            mx=cnt;
            ans=now;
        }
    }
    // cout<<ans<<endl;
    return mx;
}


signed  main(){
    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){
    //     cout<<"sol,nai"<<sol<<" "<<nai<<endl;
    //     cout<<"testcase "<<endl;
    //     cout<<n<<endl;
    //     for(int i=0;i<n;i++)cout<<x[i]<<" "<<y[i]<<endl;
    // }
    cout<<sol<<endl;
}
0