結果
問題 |
No.3289 Make More Happy Connection
|
ユーザー |
|
提出日時 | 2025-10-03 23:06:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,507 bytes |
コンパイル時間 | 3,471 ms |
コンパイル使用メモリ | 291,800 KB |
実行使用メモリ | 29,008 KB |
最終ジャッジ日時 | 2025-10-03 23:06:26 |
合計ジャッジ時間 | 9,713 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 WA * 5 |
ソースコード
#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 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]); } } {//x[i]=y[i] if(x[i+1]==y[i+1]){ 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]+x[i+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; }