Submission #11200462
Source Code Expand
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int n,k,a[5010],b[5010];
vector<int> G[5010];
vector<int> get_dp(vector<int> &v){
int s=v.size();
vector<vector<vector<vector<int>>>> dp(s+1,vector<vector<vector<int>>>(s+3,vector<vector<int>>(2,vector<int>(2,-mod))));
dp[0][0][0][0]=0;
rep(i,s-1){
rep(j,s+1){
rep(flagX,2){
//cout << flagX << " " << (!flagX) << endl;
rep(flagY,2){
dp[i+1][j+1][1][flagY]=max(dp[i+1][j+1][1][flagY],dp[i][j][flagX][flagY]+v[i+1]);
dp[i+1][j+(!flagX)][0][flagY || (i==0)]=max(dp[i+1][j+(!flagX)][0][flagY || (i==0)],dp[i][j][flagX][flagY]+v[i]);
}
}
}
}
rep(j,s+1){
rep(flagX,2){
rep(flagY,2){
dp[s][j+(!flagY)][1][flagY]=max(dp[s][j+(!flagY)][1][flagY],dp[s-1][j][flagX][flagY]+v[0]);
dp[s][j+(!flagX)][0][flagY]=max(dp[s][j+(!flagX)][0][flagY],dp[s-1][j][flagX][flagY]+v[s-1]);
}
}
}
vector<int> res(s+1);
rep(j,s+1){
res[j]=max(max(dp[s][j][0][0],dp[s][j][0][1]),max(dp[s][j][1][0],dp[s][j][1][1]));
//cout << j << " " << res[j] << endl;
}
return res;
}
bool visited[5010];
void solve(){
cin >> n >> k;
rep(i,n){
cin >> a[i];
}
rep(i,n){
cin >> b[i];
}
rep(i,n){
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
}
vector<vector<int>> dps;
Rep(i,1,n+1){
if(visited[i]) continue;
visited[i]=true;
int par=i,nex=G[i][0];
vector<int> v={i};
while(!visited[nex]){
//cout << par << " " << nex << endl;
v.push_back(nex);
visited[nex]=true;
for(int t:G[nex]){
if(t==par) continue;
par=nex;
nex=t;
break;
}
}
// for(int v_:v){
// cout << v_ << " ";
// }
//cout << "" << endl;
dps.push_back(get_dp(v));
}
// int m=dps.size();
// vector<vector<int>> DP(m+1,vector<int>(n+1,-mod));
// DP[0][0]=0;
// rep(i,m){
// int l=dps[i].size();
// rep(j,n+1){
// rep(p,l){
// if(j+p>n) continue;
// DP[i+1][j+p]=max(DP[i+1][j+p],DP[i][j]+dps[i][p]);
// }
// }
// }
// // rep(i,m+1){
// // rep(j,n+1){
// // cout << i << " " << j << " " << DP[i][j] << endl;
// // }
// // }
// int ans=0;
// Rep(j,k,n+1){
// ans=max(ans,DP[m][j]);
// }
// cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(50);
solve();
}
Submission Info
Submission Time |
|
Task |
G - Sum of Cards |
User |
Chanyuh |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3814 Byte |
Status |
WA |
Exec Time |
2254 ms |
Memory |
1769984 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
WA |
1 ms |
384 KB |
02.txt |
WA |
1 ms |
384 KB |
03.txt |
WA |
1 ms |
384 KB |
04.txt |
WA |
1 ms |
384 KB |
05.txt |
WA |
1 ms |
384 KB |
06.txt |
WA |
4 ms |
1280 KB |
07.txt |
WA |
12 ms |
7168 KB |
08.txt |
WA |
9 ms |
4736 KB |
09.txt |
WA |
11 ms |
7424 KB |
10.txt |
WA |
5 ms |
3584 KB |
11.txt |
WA |
6 ms |
2560 KB |
12.txt |
WA |
5 ms |
2176 KB |
13.txt |
WA |
11 ms |
7168 KB |
14.txt |
WA |
7 ms |
4224 KB |
15.txt |
WA |
6 ms |
3200 KB |
16.txt |
TLE |
2254 ms |
-1934080 KB |
17.txt |
WA |
1393 ms |
480264 KB |
18.txt |
TLE |
2186 ms |
1288516 KB |
19.txt |
TLE |
2200 ms |
1526912 KB |
20.txt |
WA |
1725 ms |
576384 KB |
21.txt |
TLE |
2216 ms |
1769984 KB |
22.txt |
TLE |
2251 ms |
-1862784 KB |
23.txt |
TLE |
2252 ms |
-1848236 KB |
24.txt |
WA |
1739 ms |
881792 KB |
25.txt |
TLE |
2250 ms |
-1856896 KB |
26.txt |
TLE |
2248 ms |
-1894928 KB |
27.txt |
WA |
1518 ms |
533376 KB |
28.txt |
WA |
1052 ms |
482908 KB |
29.txt |
TLE |
2251 ms |
-1860224 KB |
30.txt |
TLE |
2252 ms |
-1837824 KB |
31.txt |
WA |
10 ms |
640 KB |
32.txt |
WA |
11 ms |
640 KB |
33.txt |
WA |
12 ms |
640 KB |
34.txt |
WA |
10 ms |
640 KB |
35.txt |
WA |
11 ms |
640 KB |
36.txt |
TLE |
2135 ms |
1012224 KB |
37.txt |
TLE |
2205 ms |
1609856 KB |
38.txt |
WA |
1326 ms |
425856 KB |
39.txt |
MLE |
1893 ms |
1043404 KB |
40.txt |
TLE |
2185 ms |
1278868 KB |
s1.txt |
WA |
1 ms |
384 KB |
s2.txt |
WA |
1 ms |
384 KB |
s3.txt |
WA |
1 ms |
384 KB |