Submission #3665338

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
  V<> b(n); for (int i = 0; i < n; ++i) cin >> b[i], --b[i];
  V<> p(n);
  for (int i = 0; i < n; ++i) p[a[i]] = b[i];
  VV<> c;
  bitset<5000> vis;
  for (int i = 0; i < n; ++i) if (!vis[i]) {
    int t = i;
    vis[t] = true;
    c.push_back({t});
    while ((t = p[t]) != i) {
      vis[t] = true;
      c.back().push_back(t);
    }
  }
  int cn = c.size();
  VV<> mx(cn);
  for (int i = 0; i < cn; ++i) {
    int m = c[i].size();
    mx[i].resize(m + 1, -1e9);
    if (m == 1) {
      mx[i][1] = c[i][0];
      continue;
    }
    if (m == 2) {
      mx[i][1] = 2 * max(c[i][0], c[i][1]);
      mx[i][2] = c[i][0] + c[i][1];
      continue;
    }
    VV<> dpl, dpr;
    assign(dpl, m, m + 1, -1e9), assign(dpr, m, m + 1, -1e9);
    dpl[0][1] = c[i][0];
    for (int j = 1; j < m - 1; ++j) {
      for (int x = 1; x <= j + 1; ++x) {
        dpl[j][x] = max(dpl[j][x], dpl[j - 1][x - 1] + c[i][j]);
        dpl[j][x] = max(dpl[j][x], dpr[j - 1][x] + c[i][j]);
        dpr[j][x] = max(dpr[j][x], dpl[j - 1][x - 1] + c[i][j + 1]);
        dpr[j][x] = max(dpr[j][x], dpr[j - 1][x - 1] + c[i][j + 1]);
      }
    }
    for (int x = 1; x <= m; ++x) {
      mx[i][x] = max(mx[i][x], dpl[m - 2][x - 1] + c[i][m - 1]);
      mx[i][x] = max(mx[i][x], dpr[m - 2][x] + c[i][m - 1]);
      mx[i][x] = max(mx[i][x], dpl[m - 2][x] + c[i][0]);
      mx[i][x] = max(mx[i][x], dpr[m - 2][x] + c[i][0]);
    }
    assign(dpl, m, m + 1, -1e9), assign(dpr, m, m + 1, -1e9);
    dpr[0][1] = c[i][1];
    for (int j = 1; j < m - 1; ++j) {
      for (int x = 1; x <= j + 1; ++x) {
        dpl[j][x] = max(dpl[j][x], dpl[j - 1][x - 1] + c[i][j]);
        dpl[j][x] = max(dpl[j][x], dpr[j - 1][x] + c[i][j]);
        dpr[j][x] = max(dpr[j][x], dpl[j - 1][x - 1] + c[i][j + 1]);
        dpr[j][x] = max(dpr[j][x], dpr[j - 1][x - 1] + c[i][j + 1]);
      }
    }
    for (int x = 1; x <= m; ++x) {
      mx[i][x] = max(mx[i][x], dpl[m - 2][x - 1] + c[i][m - 1]);
      mx[i][x] = max(mx[i][x], dpr[m - 2][x] + c[i][m - 1]);
      mx[i][x] = max(mx[i][x], dpl[m - 2][x - 1] + c[i][0]);
      mx[i][x] = max(mx[i][x], dpr[m - 2][x - 1] + c[i][0]);
    }
  }
  VV<> dp; assign(dp, cn + 1, n + 1, -1e9);
  dp[0][0] = n;
  for (int i = 0; i < cn; ++i) {
    for (int x = 1; x <= n; ++x) {
      for (int j = min<int>(c[i].size(), x); j > 0; --j) {
        dp[i + 1][x] = max(dp[i + 1][x], dp[i][x - j] + mx[i][j]);
      }
    }
  }
  int res = 0;
  for (int x = k; x <= n; ++x) res = max(res, dp[cn][x]);
  cout << res << '\n';
}

Submission Info

Judge Result