Problem:
 Score : 400 points    Problem Statement Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N . Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N : P_1, P_2, \cdots, P_N .  Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):   In one move, if the piece is now on Square i  (1 \leq i \leq N) , move it to Square P_i . Here, his score increases by C_{P_i} .   Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)      Constraints  2 \leq N \leq 5000  1 \leq K \leq 10^9  1 \leq P_i \leq N  P_i \neq i  P_1, P_2, \cdots, P_N are all different.  -10^9 \leq C_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_1  P_2  \cdots  P_N  C_1  C_2  \cdots  C_N       Output Print the maximum possible score at the end of the game.        Sample Input 1 5 2
2 4 5 1 3
3 4 -10 -8 8      Sample Output 1 8  When we start at some square of our choice and make at most two moves, we have the following options:   If we start at Square 1 , making one move sends the piece to Square 2 , after which the score is 4 . Making another move sends the piece to Square 4 , after which the score is 4 + (-8) = -4 .  If we start at Square 2 , making one move sends the piece to Square 4 , after which the score is -8 . Making another move sends the piece to Square 1 , after which the score is -8 + 3 = -5 .  If we start at Square 3 , making one move sends the piece to Square 5 , after which the score is 8 . Making another move sends the piece to Square 3 , after which the score is 8 + (-10) = -2 .  If we start at Square 4 , making one move sends the piece to Square 1 , after which the score is 3 . Making another move sends the piece to Square 2 , after which the score is 3 + 4 = 7 .  If we start at Square 5 , making one move sends the piece to Square 3 , after which the score is -10 . Making another move sends the piece to Square 5 , after which the score is -10 + 8 = -2 .   The maximum score achieved is 8 .       Sample Input 2 2 3
2 1
10 -7      Sample Output 2 13       Sample Input 3 3 3
3 1 2
-1000 -2000 -3000      Sample Output 3 -1000  We have to make at least one move.       Sample Input 4 10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719      Sample Output 4 29507023469  The absolute value of the answer may be enormous.

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
  
already = [0] * N
A = [-float("inf")] * N

for i in range(N):
  if already[i] == 0:
    already[i] = 1
    q = [i + 1]
    now = i + 1
    score = []
    T = True
    while T:
      now = P[now - 1]
      score.append(C[now - 1])
      if now in q:
        T = False
      else:
        q.append(now)
        already[now - 1] = 1
    
    
    
    
    
    roop = sum(score)
    if len(q) >= K:
      aa = -float("inf")
      for j in range(len(q)):
        time = 0
        bb = 0
        p = j
        while time != K:
          time += 1
          bb += score[p]
          aa = max(aa, bb)
          p += 1
          if p == len(q):
            p = 0
      A[i] = aa      
    else:  
      if roop <= 0:
        aa = -float("inf")
        for j in range(len(q)):
          time = 0
          bb = 0
          p = j
          while time != len(q):
            time += 1
            bb += score[p]
            aa = max(aa, bb)
            p += 1
            if p == len(q):
              p = 0
        A[i] = aa            
      else:
        ll = int(K / len(q)) 
        rr = K % len(q)
        aa = -float("inf")
        for j in range(len(q)):
          time = 0
          bb = ll * roop
          p = j
          while time != len(q):
            time += 1
            bb += score[p]
            if time == rr + 1:
              bb -= roop
            aa = max(aa, bb)
            p += 1
            if p == len(q):
              p = 0
        A[i] = aa           
        


print(max(A))

Solution (Python):
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

res = -10**10

for i in range(N):
    j = i
    total = 0
    loop_values = []

    while True:
        j = P[j] - 1
        loop_values.append(C[j])
        total += C[j]
        if j == i:
            break
    
    loop_length = len(loop_values)
    point_sum = 0

    for j in range(loop_length):
        point_sum += loop_values[j]
        result_cand = point_sum

        if j+1 > K:
            break

        if total > 0:
            loop_num = (K - j - 1) // loop_length
            result_cand += total * loop_num
        
        if res < result_cand:
            res = result_cand

print(res)

Solution (Python):
n, k = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
ans = -10**18
for i in range(n):  
  x = i
  sc = []
  tot = 0
  while True:
    x = P[x]
    sc.append(C[x])
    tot += C[x]
    if x == i: break  
  
  l = len(sc)
  cum = 0
  for j in range(l):  
    cum += sc[j]
    if j+1 > k: break  
    val = cum  
    if tot > 0:
      cyc = (k-(j+1)) // l  
      val += tot * cyc
    ans = max(ans, val)
    
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

seen = []
roots = []
candidates = []

for i in range(N):
    if i+1 in seen:
        continue
    root = [i+1]
    seen.append(i+1)
    to = P[i]
    while(root[0] != to):
        root.append(to)
        seen.append(to)
        to = P[to-1]
    roots.append(root)
for root in roots:
    length = len(root)
    eachMoveBests = [None] * length
    for i in range(length):
        score = 0
        to = P[root[i]-1]
        for j in range(len(root)):
            score += C[to-1]
            to = P[to-1]
            if eachMoveBests[j] == None or score > eachMoveBests[j]:
                eachMoveBests[j] = score
    
    aroundScore = eachMoveBests[len(eachMoveBests)-1]
    if length < K and aroundScore > 0:
        for i in range(len(eachMoveBests)):
            if K-i-1 % length == 0:
                candidates.append(aroundScore * ((K-i-1) // length))
            else:
                candidates.append(aroundScore * ((K-i-1) // length) + eachMoveBests[i])
    else:
        candidates.append(max(eachMoveBests[:K]))

print(max(candidates))

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))


def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

max_score = -float('inf')

for i in range(n):
    score = 0
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            len_mv = j
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)

print(max_score)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))





def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

max_score = -float('inf')

for i in range(n):
    score = 0
    
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            
            len_mv = j
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)
    


print(max_score)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))



score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            
            len_mv = j
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print(max(score_array))

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))



score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            len_mv = len(score_mv_array)
            
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print(max(score_array))

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))


score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        
        if j!=0 and pos == start_pos:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print(max(score_array))

Solution (Python):
n,k = map(int,input().split())
p = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]

ans = -10**100

for i in range(n):
    chk = [0]*n
    chk[p[i]] = 1
    now = p[i]
    cnt = 1
    val = [-10**100]*n
    val[0] = c[p[i]]
    while 1 == 1:
        if cnt >= k:
            break
        
        if chk[p[now]] == 1:
            break
        else:
            chk[p[now]] = 1
            val[cnt] = val[cnt-1]+c[p[now]]
            now = p[now]
            cnt += 1
    
    cnt -= 1
    
    
    
    if val[cnt] <= 0:
        ans = max(ans,max(val))
    else:
        num = k // (cnt+1)
        amari = k % (cnt+1)
        
        for j in range(cnt+1):
            if j < amari:
                tmp = num*val[cnt]
            else:
                tmp = (num-1)*val[cnt]
            ans = max(ans,tmp+val[j])
            
    
    
    
print(ans)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

mv_array = [set() for _ in range(n)]
score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    for j in range(k):
        pos = p[pos]-1
        if pos in mv_array[i]:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        mv_array[i].add(pos)
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print(max(score_array))

Solution (Python):

class UnionFind():
    
    
    
    def __init__(self, n):
        self.n = n
        
        
        
        self.root = [-1]*(n+1)
        
        
        self.rnk = [0]*(n+1)

    
    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return
        
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()


for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            



ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    
    if loop_score[p]>0:
        tmp=0
        pos=i
        tmp += ((t//loop_len[p])-1)*loop_score[p]
        if tmp>0:
            ans=max(tmp,ans)
        t = (t%loop_len[p])+loop_len[p]
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        
        for j in range(min(t,loop_len[p]-1)):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)
    
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration

def main():
    N, K = MI()
    P = LI()
    C = LI()
    
    
    ans = []
    result = -float('inf')
    
    for i in range(N):
        result2= 0
        
        temp = i
        d = [-float('inf')] * N
        for j in range(N):
            temp = P[temp]-1
            result2+=C[temp]
            d[j] = result2
            if temp == i:
                index = j+1
                score = result2
                if index < K:
                    amari = K % index
                    syou = K // index
                    if amari !=0:
                        result = max(result, syou*score, syou*score+max(d[0:amari]), (syou-1)*score+max(d[0:index-1]), max(d), (syou-1)*score+max(d[0:index-1]))
                    else:
                        result = max(result, syou*score, max(d), (syou-1)*score+max(d[0:index-1]))
                    break
                else:
                    result = max(result, max(d[0:K]))
                    break
    print(result)

if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
mv_array = [set() for _ in range(n)]
score_mv_array = [[] for _ in range(n)]
score_array = [0]*n
 
def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)
 
def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score
 
 
for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    for j in range(k):
        pos = p[pos]-1
        if pos in mv_array[i]:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        mv_array[i].add(pos)
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score
 
print(max(score_array))

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

max_score = -float('inf')

for i in range(n):
    loop_score_array = []
    loop_score = 0
    loop_len = 0
    pos = i
    while True:
        pos = p[pos] - 1
        loop_score += c[pos]
        loop_score_array.append(loop_score)
        loop_len+=1
        if pos == i:
            break
    for i, score in enumerate(loop_score_array):
        if k-i-1 < 0:
            continue
        loop_num = (k-i-1)//loop_len
        score_sum = score + max(0, loop_score)*loop_num
        max_score = max(score_sum, max_score)
print(max_score)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

UnionFind=UnionFind(N+1)
for i in range(N):
    UnionFind.Unite(i+1,P[i])

D=UnionFind.group_members()
E=[]
for i in D:
    A,length=D[i],len(D[i])
    if A[0]==0:continue
    index,F=A[0]-1,[]
    while len(F)!=length:
        index=P[index]-1
        F.append(C[index])
    E.append(F)

ans=-float("inf")
for A in E:
    length=len(A)
    if sum(A)<0:
        A=A*2
        for i in range(length):
            point=0
            for j in range(min(K,length)):
                point +=A[i+j]
                ans=max(ans,point)
    else:
        div,mod=divmod(K,length)
        base=(div-1)*sum(A)
        A=A*3
        for i in range(length):
            point=0
            for j in range(mod+length):
                point +=A[i+j]
                ans=max(ans,base+point)
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

UnionFind=UnionFind(N+1)
for i in range(N):
    UnionFind.Unite(i+1,P[i])

D=UnionFind.group_members()
E=[]
for i in D:
    A,length=D[i],len(D[i])
    if A[0]==0:continue
    index,F=A[0]-1,[]
    while len(F)!=length:
        index=P[index]-1
        F.append(C[index])
    E.append(F)

ans=-float("inf")
for A in E:
    length=len(A)
    if sum(A)<0:
        A=A*2
        for i in range(length):
            point=0
            for j in range(min(K,length)):
                point +=A[i+j]
                ans=max(ans,point)
    else:
        div,mod=divmod(K,length)
        base=(div-1)*sum(A)
        A=A*3
        for i in range(length):
            point=0
            ans=max(ans,base)
            for j in range(mod+length):
                point +=A[i+j]
                ans=max(ans,base+point)
print(ans)

Solution (Python):
n,k = map(int,input().split())
p = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]
INF = float("INF")
ans = -INF

for si in range(n):
    x = si
    S = []
    tot = 0
    while True:
        x = p[x]
        S.append(c[x])
        tot += c[x]
        if x == si: break
    l = len(S)
    t = 0
    for i in range(l):
        if i+1 > k: break
        t += S[i]
        now = t
        if tot > 0:
            e = (k-(i+1))//l
            now += tot*e
        ans = max(ans, now)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


def main():
    N, K = NMI()
    P = NLI()
    P = [p-1 for p in P]
    C = NLI()

    seen = [0] * N
    loops = []
    for i in range(N):
        if seen[i] == 1:
            continue
        now = i
        now_loop = [now]
        now_cost = C[now]
        while True:
            seen[now] = 1
            goto = P[now]
            if seen[goto] == 1:
                break
            now_loop.append(goto)
            now_cost += C[goto]
            now = goto
        loops.append([now_loop, now_cost])

    ans = -float("inf")
    for loop, cost in loops:
        C_cum = make_cumulative([C[p] for p in loop])

        for i, start in enumerate(loop):
            for j, end in enumerate(loop):
                if i == j:
                    base = cost
                    moved = len(loop)
                elif i < j:
                    base = C_cum[j] - C_cum[i]
                    moved = j - i
                else:
                    base = cost - (C_cum[i] - C_cum[j])
                    moved = len(loop) + j - i

                if moved > K:
                    continue

                if cost > 0:
                    tmp_K = K - moved
                    num_loop = tmp_K // len(loop)
                    tmp_ans = num_loop * cost + base
                else:
                    tmp_ans = base

                ans = max(ans, tmp_ans)

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]
pow_num = 31
point = [[0] * n for i in range(pow_num)]
point_max = [[0] * n for i in range(pow_num)]
posi = [[0] * n for i in range(pow_num)]

c_set = set(c)
if all([i < 0 for i in c_set]):
    print(max(c_set))
else:
    for i in range(pow_num):
        if i == 0:
            for j in range(n):
                posi[i][j] = p[j]
                point[i][j] = c[p[j]]
            continue
        for j in range(n):
            posi[i][j] = posi[i-1][posi[i-1][j]]
            point[i][j] = point[i-1][j] + point[i-1][posi[i-1][j]]
    for i in range(pow_num):
        if i == 0:
            for j in range(n):
                point_max[i][j] = point[i][j]
            continue
        for j in range(n):
            point_max[i][j] = max(point_max[i-1][j], \
                point[i-1][j] + point_max[i-1][posi[i-1][j]])

    power_count = list()
    for i in range(pow_num):
        if k & (1 << i):
            power_count.append(i)

        ans = 0
        for i in range(n):
            next_posi = i
            cumsum_point = 0
            for posi_idx in power_count:
                if ans < cumsum_point + point_max[posi_idx][next_posi]:
                    ans = cumsum_point + point_max[posi_idx][next_posi]
                cumsum_point += point[posi_idx][next_posi]
                next_posi = posi[posi_idx][next_posi]

    print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Cs = list(map(int, input().split()))
max_list = list()
for i in range(N):
    next = Ps[i] - 1
    scores = [Cs[next]]
    while next != i:
        next = Ps[next] - 1
        scores.append(scores[-1] + Cs[next])
    l = len(scores)
    if K <= l:
        max_list.append(max(scores[:K]))
    else:
        if scores[-1] < 0:
            max_list.append(max(scores))
        else:
            a, b = divmod(K, l)
            cand1 = 0
            if b!=0:
                cand1 = a*scores[-1] + max(scores[:b])
            cand2 = (a-1)*scores[-1] + max(scores)
            max_list.append(max(cand1, cand2))
    
print(max(max_list))

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split(" ")))
for i in range(n):
    p[i] -= 1
c = list(map(int, input().split(" ")))
ans = -10000000000
for start in range(n):
    now = start
    pt = 0
    cycle = 0
    looplen = 0

    while 1:
        now = p[now]
        pt += c[now]
        looplen += 1
        if now == start:
            break

    cycle = pt
    pt = 0
    for i in range(looplen):
        now = p[now]
        pt += c[now]
        aftermove = k - i-1
        if aftermove < 0:
            continue

        loop = aftermove//looplen
        ans = max(ans, pt)
        ans = max(ans, pt+loop*cycle)
print(ans)

Solution (Python):


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    P = [i-1 for i in P]
    ans = -1e19

    for si in range(N):
        index = si
        cycle =[]
        total = 0
        while True:
            index = P[index]
            cycle.append(C[index])
            total = total + C[index]
            if index == si:
                break
        cycle_length = len(cycle)
        count = 0
        for i in range(cycle_length):
            count  = count + cycle[i]
            if i+1 > K:
                break
            num = count
            if total > 0:
                cnt = (K - (i+1)) // cycle_length
                num = num + cnt*total
            ans = max(ans, num)
    print(ans)


main()

Solution (Python):

def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    ans = -INF
    for s in range(N):
        S = []
        x = P[s]
        S.append(C[x])
        tot = C[x]
        while s != x:  
            x = P[x]
            S.append(C[x])
            tot += C[x]
        s_n = len(S)
        t = 0
        for i in range(s_n):
            t += S[i]
            now = t
            if tot > 0:
                loop = (K - i - 1) // s_n
                now += tot * loop
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    resolve()