Submission #3664591

---

Source Code Expand

#include <bits/stdc++.h>

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver2 {
 public:
  int n, k;
  vector<int> a, b, visit;
  vector<vector<int>> to;
  vector<vector<int>> memo;
  vector<vector<int>> seq;
  Solver2(LL n, LL k) : n(n), k(k), a(n), b(n), visit(n + 1), to(n + 1), memo(n + 1){};
  void dfs(int a, int prev, int s, vector<int> &v) {
    DBG(a, prev, s)
    visit[a] = 1;
    v.push_back(a);
    int nxt = to[a][0];
    if (nxt == prev) {
      nxt = to[a][1];
    }
    if (nxt != s) {
      dfs(nxt, a, s, v);
    }
  }
  vector<int> dp(vector<int> &v) {
    int m = v.size();
    if (m == 2) {
      return {0, abs(v[0] - v[1])};
    }
    vector<vector<vector<int>>> res(m + 1, vector<vector<int>>(2, vector<int>(2, INF)));

    res[0][0][0] = 0;
    res[1][1][1] = abs(v[0] - v[1]);
    for (int i = 1; i < m - 1; ++i) {
      for (int j = m - 1; j >= 0; --j) {
        for (int k = 0; k < 2; ++k) {
          res[j + 1][1][k] = min(res[j + 1][1][k], res[j][0][k] + abs(v[i] - v[i + 1]));
          res[j][0][k] = min(res[j][0][k], res[j][1][k]);
        }
      }
    }
    DBG(res)
    vector<int> ret(m + 1, INF);
    ret[0] = 0;
    for (int j = m; j >= 1; --j) {
      ret[j] = min<int>({res[j][0][0], res[j][0][1], res[j][1][0], res[j][1][1], res[j - 1][0][0] + abs(v.back() - v[0])});
    }
    return ret;
  }
  vector<int> calc(vector<int> &a, vector<int> &&b) {
    vector<int> ret(a.size() + b.size() - 1, INF);
    for (int i = 0; i < a.size(); ++i) {
      for (int j = 0; j < b.size(); ++j) {
        ret[i + j] = min(ret[i + j], a[i] + b[j]);
      }
    }
    return ret;
  }
  void solve() {
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
      cin >> b[i];
    }
    int maxsum = 0;
    set<int> S;
    for (int i = 0; i < n; ++i) {
      int ma = max(a[i], b[i]);
      int mi = min(a[i], b[i]);
      if (a[i] != b[i]) {
        to[ma].push_back(mi);
        to[mi].push_back(ma);
      }
      maxsum += ma;
      S.insert(ma);
    }
    int rem = max(0, k - (int)S.size());
    DBG(a, b, n, k)
    DBG(maxsum, S, rem)
    for (int i = n; i > 0; --i) {
      if (visit[i] == 0 && to[i].size() == 2 && i > to[i][0] && i > to[i][1]) {
        visit[i] = 1;
        vector<int> tmp;
        DBG(i)
        tmp.push_back(i);
        dfs(to[i][0], i, i, tmp);
        seq.push_back(tmp);
      }
    }
    DBG(seq)
    vector<int> ans(1);
    for (auto &&x : seq) {
      vector<int> y;
      int X = x.size();
      for (int i = 0; i < X; ++i) {
        if ((x[i] - x[(i - 1 + X) % X]) * (x[i] - x[(i + 1 + X) % X]) > 0) y.push_back(x[i]);
      }
      ans = calc(ans, dp(y));
    }
    DBG(ans)
    cout << maxsum - *min_element(ans.begin() + rem, ans.end()) << endl;
  }
};
}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0, k;
  std::cin >> n >> k;

  Problem::Solver2 sol(n, k);
  sol.solve();
  return 0;
}

Submission Info

Judge Result