Submission #11200289


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;
            }
            par=nex;
        }
        // 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 3671 Byte
Status WA
Exec Time 93 ms
Memory 46592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 4
WA × 39
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 63 ms 28416 KB
17.txt WA 63 ms 28288 KB
18.txt WA 71 ms 32512 KB
19.txt WA 72 ms 33280 KB
20.txt WA 86 ms 40064 KB
21.txt WA 69 ms 31488 KB
22.txt WA 67 ms 30976 KB
23.txt WA 86 ms 40064 KB
24.txt WA 64 ms 28800 KB
25.txt WA 70 ms 32512 KB
26.txt WA 80 ms 36736 KB
27.txt WA 81 ms 37120 KB
28.txt WA 64 ms 28672 KB
29.txt WA 80 ms 36608 KB
30.txt WA 83 ms 38656 KB
31.txt WA 67 ms 30720 KB
32.txt WA 78 ms 36736 KB
33.txt WA 88 ms 41600 KB
34.txt WA 60 ms 27648 KB
35.txt WA 85 ms 40064 KB
36.txt WA 93 ms 46592 KB
37.txt WA 68 ms 33024 KB
38.txt WA 86 ms 43008 KB
39.txt WA 67 ms 33024 KB
40.txt WA 89 ms 44416 KB
s1.txt AC 1 ms 384 KB
s2.txt AC 1 ms 384 KB
s3.txt AC 1 ms 384 KB