Submission #68598445

---

Source Code Expand

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

void remax(int& x, int y) {
	x = (x > y) ? x : y;
}

int f(const vector<int>& values) {
	const int n = values.size();
	vector<vector<int>> dp(n, vector<int>(n, 0));
	vector<vector<int>> others(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i != j && values[i] == values[j]) {
				others[i].push_back(j);
			}
		}
	}
	auto is_in = [&](int j, int i, int len) {
		if (j > i) {
			return j <= i + len;
		} else {
			return j + n <= i + len;
		}
	};
	auto dist = [&](int i, int j) {
		return j >= i ? (j - i) : (j - i + n);
	};
	for (int len = 1; len < n; ++len) {
		for (int i = 0; i < n; ++i) {
			const int j = (i + len) % n;
			dp[i][len] = dp[i][len - 1];
			for (int k : others[j]) {
				if (is_in(k, i, len - 1)) {
					int d = dist(i, k);
					remax(dp[i][len], dp[i][d - 1] + dp[k][len - d]);
				}
			}
			if (values[i] == values[j]) {
				++dp[i][len];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		remax(ans, dp[i][n - 1]);
	}
	// cerr << ans << "\n";
	return ans;
}

void solve() {
	int n = nxt(), k = nxt();
	const int sz = n * k;
	vector<int> a(sz);
	for (auto& x : a) {
		x = nxt() - 1;
	}
	vector<char> used(sz);
	int ans = 0;
	for (int i = 0; i < sz; ++i) {
		if (used[i]) {
			continue;
		}
		int v = i;
		vector<int> values;
		while (!used[v]) {
			// cerr << v << " -> ";
			values.push_back(v % n);
			used[v] = true;
			v = a[v];
		}
		// cerr << i << "\n";
		ans += f(values);
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1; // nxt();
	while (t--) {
		solve();
	}

	return 0;
}

Submission Info

Judge Result