Submission #11200024
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]){
v.push_back(nex);
visited[nex]=true;
for(int t:G[nex]){
if(t==par) continue;
nex=t;
}
}
// 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 |
3649 Byte |
Status |
WA |
Exec Time |
94 ms |
Memory |
46592 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 |
AC |
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 |
2 ms |
512 KB |
07.txt |
WA |
2 ms |
512 KB |
08.txt |
WA |
2 ms |
640 KB |
09.txt |
WA |
2 ms |
512 KB |
10.txt |
WA |
2 ms |
512 KB |
11.txt |
WA |
2 ms |
512 KB |
12.txt |
WA |
2 ms |
512 KB |
13.txt |
WA |
2 ms |
512 KB |
14.txt |
WA |
2 ms |
512 KB |
15.txt |
WA |
2 ms |
512 KB |
16.txt |
WA |
64 ms |
28416 KB |
17.txt |
WA |
64 ms |
28288 KB |
18.txt |
WA |
72 ms |
32512 KB |
19.txt |
WA |
73 ms |
33280 KB |
20.txt |
WA |
87 ms |
40064 KB |
21.txt |
WA |
69 ms |
31488 KB |
22.txt |
WA |
68 ms |
30976 KB |
23.txt |
WA |
87 ms |
40064 KB |
24.txt |
WA |
64 ms |
28800 KB |
25.txt |
WA |
71 ms |
32512 KB |
26.txt |
WA |
81 ms |
36736 KB |
27.txt |
WA |
81 ms |
37120 KB |
28.txt |
WA |
65 ms |
28672 KB |
29.txt |
WA |
81 ms |
36608 KB |
30.txt |
WA |
84 ms |
38656 KB |
31.txt |
WA |
68 ms |
30720 KB |
32.txt |
WA |
79 ms |
36736 KB |
33.txt |
WA |
89 ms |
41600 KB |
34.txt |
WA |
61 ms |
27648 KB |
35.txt |
WA |
86 ms |
40064 KB |
36.txt |
WA |
94 ms |
46592 KB |
37.txt |
WA |
69 ms |
33024 KB |
38.txt |
WA |
87 ms |
43008 KB |
39.txt |
WA |
68 ms |
33024 KB |
40.txt |
WA |
90 ms |
44416 KB |
s1.txt |
AC |
1 ms |
384 KB |
s2.txt |
AC |
1 ms |
384 KB |
s3.txt |
AC |
1 ms |
384 KB |