Submission #68597674

---

Source Code Expand

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def solve(N,K,P):

    val_to_idx = [[] for i in range(N)]

    def calc(A):
        n = len(A)

        for i,a in enumerate(A):
            val_to_idx[a].append(i)


        dp = [[0]*(n+1) for l in range(n+1)]
        for l in range(n)[::-1]:
            for r in range(l+1,n+1):
                dp[l][r] = dp[l+1][r]
                a = A[l]

                for mid in val_to_idx[a]:
                    if l < mid < r:
                        dp[l][r] = max(dp[l][r],dp[l][mid]+dp[mid][r]+1)
        
        for i,a in enumerate(A):
            val_to_idx[a] = []
        
        return dp[0][n]
    
    res = 0
    done = [0] * (N*K)
    for i in range(N*K):
        if done[i]:
            continue

        A = [i]
        done[i] = 1
        while True:
            nxt = P[A[-1]]
            if done[nxt]:
                break
            A.append(nxt)
            done[nxt] = 1

        A = [a % N for a in A]
        res += calc(A)
    
    return res

N,K = mi()
P = li()
P = [p-1 for p in P]
print(solve(N,K,P))

Submission Info

Judge Result