Submission #68602708

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

const int N = 1e4 + 5;
int f[N][N], ok[N][N], n, k;

inline bool chk(int x, int y) { return (x - y) % n == 0; }

int sol(vector<int> v)
{
    if(v.size() == 1) return 0;
    // for(int i : v) cerr << i << " "; cerr << endl;
    int n = v.size();
    int ans = 0;
    rep(i, 0, n - 1) v.push_back(v[i]);
    rep(i, 0, n * 2) rep(j, 0, n * 2) f[i][j] = -1e9, ok[i][j] = 0;
    rep(i, 0, n * 2 - 2) f[i][i + 1] = chk(v[i], v[i + 1]), ok[i][i + n - 1] = 1;
    per(i, n - 1, 0)
    {
        vector<int> pos;
        rep(j, i + 1, n * 2 - 2)
        {
            for(int k : pos)
                chmax(f[i][j], f[i][k] + f[k][j]);
            ok[i][j] |= pos.size();
            chmax(f[i][j], f[i][j - 1] + chk(v[i], v[j]));
            chmax(f[i][j], f[i + 1][j] + chk(v[i], v[j]));
            // if(!ok[i][j])
            //     rep(k, i + 1, j - 1)
            //         chmax(f[i][j], f[i][k] + f[k][j]);
            if(chk(v[j], v[i])) pos.push_back(j);
        }
        pos = {};
        per(j, i - 1, 1)
        {
            for(int k : pos)
                chmax(f[j][i], f[j][k] + f[k][i]);
            ok[j][i] |= pos.size();
            if(chk(v[j], v[i])) pos.push_back(j);
        }
    }
    rep(i, 0, n - 1) chmax(ans, f[i][i + n - 1]);
    // cerr << ans << endl;
    return ans;
}

int a[N];
bool vis[N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> k; rep(i, 1, n * k) cin >> a[i];
    int ans = 0;
    rep(i, 1, n * k) if(!vis[i])
    {
        vector<int> v;
        for(int j = i; !vis[j]; j = a[j]) v.push_back(j), vis[j] = 1;
        ans += sol(v);
    }
    cout << ans;

    return 0;
}

Submission Info

Judge Result