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):

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

    ans = -10 ** 9
    for start in range(N):
        
        now = start
        cycle = []
        total = 0
        for _ in [0] * N:  
            now = P[now]
            cycle.append(C[now])
            total += C[now]
            if now == start:
                break
        
        length = len(cycle)
        score = 0
        for move in range(length):
            score += cycle[move]
            
            if move >= K:
                break
            
            res = score
            if total > 0:
                laps = (K - (move + 1)) // length
                res += total * laps
            ans = max(ans, res)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = 10**9
    n,k = map(int,input().split())
    P = [0] + list(map(int,input().split()))
    C = [0] + list(map(int,input().split()))

    scores = [0]*n

    for s in range(1,n+1):
        start = s
        dp = [-INF]*(n+1)
        dp[0] = 0
        for i in range(n):
            p = P[s]
            dp[i+1] = dp[i] + C[p]
            
            if start == p:
                break
            s = p
        if k <= i+1:
            scores[start-1] = max(dp[1:k+1])
        elif dp[i+1]<=0:
            scores[start-1] = max(dp[1:])
        else:
            r = k%(i+1)
            q = k//(i+1)
            if r>0:
                scores[start-1] = max(max(dp[1:r+1])+dp[i+1]*q, max(dp[1:]))
            else:
                scores[start-1] = dp[i+1]*(q-1)+max(dp[1:])

    print(max(scores))
main()

Solution (Python):
n,k = map(int, input().split())
p = [0]+[int(x) for x in input().split()]
c = [0]+[int(x) for x in input().split()]

ans=-10**18

for saisyo in range(1,n+1):
    tensuulist=[]
    genzaiti=saisyo

    while(True):
        genzaiti=p[genzaiti]
        tensuulist.append(c[genzaiti])
        if genzaiti==saisyo:
            break

    goukei=sum(tensuulist)
    nagasa=len(tensuulist)
    kaisuu=k
    syou=kaisuu//nagasa
    amari=kaisuu%nagasa

    tensuu=0
    nokorikaisuu=0

    if goukei<=0:
        for i in range(nagasa):
            tensuu+=tensuulist[i]
            ans=max(ans,tensuu)
    else:
        if 3*nagasa<kaisuu:
            tensuu+=goukei*(syou-1)
            nokorikaisuu=nagasa+amari
            for i in range(nokorikaisuu):
                tensuu+=tensuulist[(i%nagasa)]
                ans=max(ans,tensuu)
        else:
            for i in range(kaisuu):
                tensuu+=tensuulist[(i%nagasa)]
                ans=max(ans,tensuu)

print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=[]
for i in range(N):
    score=[]
    B=[]
    count=1
    nex=P[i]-1
    point=C[nex]
    B.append(C[nex])
    score.append(point)
    while count<=K:
        if nex==i:
            break
        nex=P[nex]-1
        point+=C[nex]
        score.append(point)
        B.append(C[nex])
        count+=1
    if count==K:
        ans.append(max(score))
    else:
        if point<=0:
            ans.append(max(score))
        else:
            a=K//count
            b=K%count
            maxpoint=point*(a-1)
            for j in range(b):
                maxpoint+=B[j]
            c=maxpoint
            for j in range(count):
                if b+j<count:
                    c+=B[b+j]
                else:
                    c+=B[b+j-count]
                maxpoint=max(maxpoint,c)
            ans.append(maxpoint)
print(max(ans))

Solution (Python):
def D():
    N, K = map(int, input().split())
    P = [int(n) for n in input().split()]
    C = [int(n) for n in input().split()]
    cycle_sums = [float('-inf')]*N
    cycle_length = [-1]*N
    for i in range(N):
        
        if cycle_sums[i] == float('-inf'): 
            points = 0
            visited_set = set()
            visited_order = []
            while P[i] not in visited_set:
                visited_set.add(P[i])
                visited_order.append(P[i])
                i = P[i]-1
            _sum = 0
            for j in range(len(visited_order)):
                _sum += C[visited_order[j]-1]
            for j in range(len(visited_order)):
                cycle_sums[visited_order[j]-1] = _sum
                cycle_length[visited_order[j]-1] = len(visited_order)
    

    ans = float('-inf')
    for j in range(N):
        i = j
        k = K
        points = 0
        if cycle_sums[i] > 0:
            num_cycles, remainder = divmod(k, cycle_length[i])
            if num_cycles > 0:
                num_cycles -= 1
                remainder += cycle_length[i]
            points += cycle_sums[i] * num_cycles
            k = remainder
        else:
            
            i = P[i]-1
            points += C[i]
            k = min(k, cycle_length[i]-1)
        
        _sum = points

        while k > 0:
            i = P[i]-1
            _sum += C[i]
            points = max(points, _sum)
            k -= 1
        
        ans = max(ans, points)

    return ans
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

print(D())

Solution (Python):
n, k = map(int, input().split())
next = list(map(int, input().split()))
next = list(map(lambda x: x - 1, next))
c = list(map(int, input().split()))

ans = -(10 ** 17)

for i in range(n):
    now = i
    cycle_sum = 0
    cycle_len = 0

    while True:
        cycle_sum += c[now]
        cycle_len += 1
        now = next[now]
        if now == i:
            break

    sum = 0
    cnt = 0

    while True:
        sum += c[now]
        cnt += 1

        if cnt > k:
            break

        laps = (k - cnt) // cycle_len
        score = sum + max(0, cycle_sum) * laps
        ans = max(ans, score)

        now = next[now]
        if now == i:
            break

print(ans)

Solution (Python):
import sys
def main():
  input = sys.stdin.readline
  n, k = map(int , input().split())
  p_list = list(map(int, input().split()))
  c_list = list(map(int, input().split()))
  res = -float('inf')
  
  for s in range(n):
    S = []
    i = p_list[s] - 1
    S.append(c_list[i])
    while i != s:
      i = p_list[i]-1
      S.append(S[-1] + c_list[i])
    if k <= len(S):
      score = max(S[:k])
    elif S[-1] <= 0:
      score = max(S)
    else:
      score1 = S[-1] * (k//len(S) - 1)
      score1 += max(S)
      
      score2 = S[-1] * (k//len(S))
      r = k%len(S)
      if r!=0:
        score2 += max(0, max(S[:r]))
      score = max(score1, score2)
    res = max(res, score)
  print(res)
      

if (__name__=='__main__'):
  main()

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

k-=1

m=int(log2(k)) if 1<k else 1
nxt=[[0]*n for _ in range(m+1)]
point=[[0]*n for _ in range(m+1)]
for i in range(n):
  p[i]-=1
  nxt[0][i]=p[i]
  point[0][i]=c[p[i]]
for j in range(m):
  for i in range(n):
    nxt[j+1][i]=nxt[j][nxt[j][i]]
    point[j+1][i]=point[j][i]+point[j][nxt[j][i]]
min_nk=min(n,k)
ans=-10**18
for s in range(n):
  pla=p[s]
  cur=c[pla]
  if ans<cur:
    ans=cur
  for _ in range(min_nk):
    pla=p[pla]
    cur+=c[pla]
    if ans<cur:
      ans=cur
  if n<k:
    pla=p[s]
    cur=c[pla]
    for i in range(m+1):
      if (k-n)&(1<<i):
        cur+=point[i][pla]
        pla=nxt[i][pla]
    res=cur
    for _ in range(n):
      pla=p[pla]
      cur+=c[pla]
      if res<cur:
        res=cur
    if ans<res:
      ans=res
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    accum=[0]+accum
    
    for x in range(1,l+1):
        if accum[x+l-1]-accum[x-1]<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    accum=[0]+accum
    
    for x in range(1,l+1):
        if accum[x+l-1]-accum[x-1]<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)

Solution (Python):
import numpy as np
from numba import njit

@njit('i8(i8,i8,i8[:],i8[:],i8)', cache=True)
def get_max_score(N, K, plist, slist, max_score):
    for start in range(N):

        total_score_in_loop = 0
        score_loop = []
        now = start
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        
        rem_score, loop_score = 0, 0
        for idx in range(1, len(score_loop)+1):
            rem_score += score_loop[idx-1]
            if total_score_in_loop > 0:
                loop_score = ((K - idx) // len(score_loop)) * total_score_in_loop
            max_score = max(max_score, rem_score + loop_score)
    return max_score

def main():
    N, K = map(int, input().split())
    plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
    slist = np.array([i for i in map(int, input().split())], dtype='int64')
    max_score = -10**15
    max_score = get_max_score(N, K, plist, slist, max_score)
    print(max_score)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from numba import njit

@njit('i8(i8,i8,i8[:],i8[:],i8)', cache=True)
def main(N, K, plist, slist, max_score):
    for start in range(N):

        total_score_in_loop = 0
        score_loop = []
        now = start
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        
        rem_score, loop_score = 0, 0
        for idx in range(1, len(score_loop)+1):
            rem_score += score_loop[idx-1]
            if total_score_in_loop > 0:
                loop_score = ((K - idx) // len(score_loop)) * total_score_in_loop
            max_score = max(max_score, rem_score + loop_score)
    return max_score


N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, 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()))

ans = -10**18
for start in range(N):
    now = start
    cycle = [0]

    while True:
        now = P[now] - 1
        cycle.append(cycle[-1] + C[now])

        if now == start: break

    L = len(cycle)-1
    if cycle[-1] < 0 or K <= L:
        score = max(cycle[1:min(L+1,K)+1])
    else:
        score1 = cycle[-1]*(K//L) + max(cycle[:K%L+1])
        score2 = cycle[-1]*(K//L-1) + max(cycle)
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)

Solution (Python):
(n,k),p,c,*a=[[*map(int,t.split())]for t in open(0)]
while n:
 n-=1;s,x,*l=0,n;f=j=k
 while f:x=p[x]-1;s+=c[x];l+=s,;f=x!=n
 for t in l[:k]:j-=1;a+=[t+j//len(l)*s*(s>0)]
print(max(a))

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

ans = -10 ** 9
for i in range(1, N + 1):
    start = i
    next_ = start
    loop_score = 0
    loop_count = 0
    while True:
        loop_count += 1
        loop_score += C[next_]
        next_ = P[next_]
        if next_ == start:
            break
    in_score = 0
    in_count = 0

    for k in range(K):
        in_count += 1
        in_score += C[next_]

        loop_num = (K - in_count) // loop_count
        score = in_score + max(0, loop_score) * loop_num
        ans = max(ans, score)

        next_ = P[next_]
        if next_ == start:
            break

print(ans)

Solution (Python):
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
while n:
 n-=1;s,x,*l=0,n;f=j=k
 while f:x=p[x]-1;s+=c[x];l+=s,;f=x!=n
 for t in l[:k]:j-=1;a=max(a,t+j//len(l)*s*(s>0))
print(a)

Solution (Python):
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve(start):
    loop = []
    llen = 0
    lsum = 0
    reach = [0]*n

    now = start
    while True:
        nxt = P[now]-1
        loop.append(now)
        llen += 1
        lsum += C[now]
        reach[now] = 1
        if reach[nxt]:
            break
        now = nxt
    
    if lsum <= 0 or llen >= k:
        res = -10 ** 20
        s = 0
        now = start
        for i in range(min(llen, k)):
            s += C[now]
            res = max(res, s)
            now = P[now]-1
        return res
    else:
        s = lsum * (k // llen)
        now = start
        for i in range(k % llen):
            s += C[now]
            now = P[now]-1
        j = loop.index(now)
        res = -10**20
        for i in range(llen):
            j -= 1
            res = max(res, s)
            s -= C[loop[j]]
        return res


def solver():
    ans = -10 ** 20
    for i in range(n):
        ans = max(ans, solve(i))
    return ans


print(solver())

Solution (Python):
from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = -(1e9 + 5)
for i in range(N):
    x = i
    S = deque()
    s = 0
    while True:
        x = P[x] - 1
        S.append(C[x])
        s += C[x]
        if x == i:
            break
    l = len(S)
    a = 0
    for i in range(l):
        a += S[i]
        if i + 1 > K:
            break
        An = a
        if s > 0:
            An += s * ((K - i - 1) // l)
        A = max(A, An)
print(A)

Solution (Python):

import sys
INF = 10**10
def main(N, K, P, C):
    ans = max(C)
    for i in range(N):
        used = [False] * N
        now = 0
        mx = -INF
        cnt = 0
        while True:
            if used[i] or cnt >= K:
                break
            used[i] = True
            i = P[i] - 1
            now += C[i]
            mx = max(mx, now)
            cnt += 1
        tmp = max(mx, now)
        if now > 0:
            cycle, mod = divmod(K, cnt)
            if cycle > 1:
                tmp = max(tmp, now * (cycle - 1) + mx)
            t = now * cycle
            tmp = max(tmp, t)
            for j in range(mod):
                i = P[i] - 1
                t += C[i]
                tmp = max(tmp, t)
        ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    *C, = map(int, input().split())
    main(N, K, P, C)

Solution (Python):

import sys 
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
P = [0] + list(map(int,readline().split()))
C = [0] + list(map(int,readline().split()))

ans = -10 ** 10
for i in range(1,N+1):
    l = 1
    j = P[i]
    s = C[j]
    ans = max(ans, s) 
    while j != i:     
        j = P[j]
        s += C[j]
        l += 1
        if K >= l:
            ans = max(ans, s)
    
    c = 1
    j = P[j]
    t = C[j]
    ans = max(ans, t + ((K - c) // l) * s) 
    
    while j != i:
        j = P[j]
        t += C[j]
        c += 1
        if K >= c:
            ans = max(ans, t + ((K - c) // l) * s) 
print(ans)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    P = [p-1 for p in read_ints()]
    C = read_ints()

    max_score = -math.inf
    for i in range(N):
        cycle_score = C[i]
        scores = [0, C[i]]
        j = P[i]
        k = K
        while k > 1 and i != j:
            cycle_score += C[j]
            scores.append(cycle_score)
            j = P[j]
            k -= 1
        cycle_size = len(scores)-1
        cycle_count = K//cycle_size
        max_score = max(max_score, max(scores[1:]))
        if cycle_count != 0:
            max_score = max(max_score,
                            cycle_score*cycle_count+max(scores[:K%cycle_size+1]),
                            cycle_score*(cycle_count-1)+max(scores[1:]))
    return max_score


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache







n,k=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
ans=-inf
for i in range(n):
    now=i
    total=0
    roop= 0
    po=deque([0])
    for kai in range(1,k+1):
        now=P[now]
        total += C[now]
        roop+=1
        po.append(total)
        ans=max(ans, total)
        if now == i:
            la= kai;break

    else: continue
    if total<0 : continue
    po=list(po)
    ans=max(ans, total* (k//roop) + max(po[:k%roop+1]), total*(k//roop-1) + max(po))
    
print(ans)

Solution (Python):
import numpy as np
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
cycles, check = [], [False]*n
for pi in p:
    if not check[pi-1]:
        curr, cycle = pi, []
        check[pi-1] = True
        while pi != p[curr-1]:
            check[curr-1] = True
            cycle.append(c[curr-1])
            curr = p[curr-1]
        check[curr-1] = True
        cycles.append(cycle + [c[curr-1]])
 
scores = []
for cycle in (np.array(cycle) for cycle in cycles):
    for i in range(cycle.size):
        cum = np.roll(cycle, i).cumsum()
        if cum[-1] > 0 and k > cycle.size:
            scores.append(cum[-1]*(k//cycle.size-1) + np.concatenate([cum, cum[:k % cycle.size]+cum[-1]]).max())
        else:
            scores.append(cum[:min(k, cum.size)].max())
print(max(scores))

Solution (Python):
from itertools import accumulate

N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    path = []

    cur = P[start]
    path = [C[start]]
    while cur != start:
        path.append(C[cur])
        cur = P[cur]

    A = list(accumulate(path))
    q, r = divmod(K, len(path))
    res = 0
    if A[-1] >= 0:
        if r == 0:
            q -= 1
            r += len(path)
        res += A[-1] * q
    elif q >= 1:
        r = len(path)

    ans = max(ans, res + max(A[:r]))

print(ans)

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

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * ((K//k)-1)
                NumberOfCycle = (K%k) + k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)

Solution (Python):
import numpy as np


def parse():
    _, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pc = {i: (pi - 1, ci) for i, (pi, ci) in enumerate(zip(p, c))}
    return k, pc


def read_split():
    k, pc = parse()
    lst = [[]]
    lst[0].append(pc.pop(0))
    while True:
        if not pc:
            break
        p, _ = lst[-1][-1]
        if p in pc:
            pcj = pc.pop(p)
            lst[-1].append(pcj)
        else:
            j = next(iter(pc.keys()))
            pcj = pc.pop(j)
            lst.append([pcj])
    return k, [np.array([ls[1] for ls in lst_], dtype=np.long) for lst_ in lst]


def inner(n, k, s, sim):
    if sim.shape[1] == 1:
        return sim.max()
    if k < n or s <= 0:
        return sim.max()
    div = k // n
    mod = k % n
    if mod == 0:
        return s * (div - 1) + sim.max()
    else:
        return s * div + sim[:, :mod].max()


def main():
    k, data_set = read_split()
    result = min([d.min() for d in data_set])
    for data in data_set:
        n = data.size
        rep = np.repeat(data[None], 2, axis=0).flatten()
        sim = np.array([np.cumsum(rep[i:i+min(k, n)]) for i in range(n)])
        cand = inner(n, k, data.sum(), sim)
        result = max(result, cand)
    print(result)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np


def parse():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pc = {i: (pi - 1, ci) for i, (pi, ci) in enumerate(zip(p, c))}
    return k, pc


def split_simple():
    k, pc = parse()
    lst = [[]]
    lst[0].append(pc.pop(0))
    while True:
        if not pc:
            break
        p, _ = lst[-1][-1]
        if p in pc:
            pcj = pc.pop(p)
            lst[-1].append(pcj)
        else:
            j = next(iter(pc.keys()))
            pcj = pc.pop(j)
            lst.append([pcj])
    return k, [np.array([ls[1] for ls in lst_], dtype=np.long) for lst_ in lst]


def inner(n, k, s, sim):
    
    
    if sim.shape[1] == 1:
        return sim.max()
    if k < n or s <= 0:
        return sim.max()
    div = k // n
    mod = k % n
    
    if mod == 0:
        return max(s * div, s * (div - 1) + sim.max())
    try:
        return max(s * div + sim[:, :mod].max(), s * (div - 1) + sim[:, :mod].max())
    except ValueError:
        print(mod)
        print(sim)
        print(sim.shape)
        raise


def main():
    k, data_set = split_simple()
    result = min([d.min() for d in data_set])
    for data in data_set:
        n = data.size
        rep = np.repeat(data[None], 2, axis=0).flatten()
        
        
        sim = np.array([np.cumsum(rep[i:i+min(k, n)]) for i in range(n)])
        
        cand = inner(n, k, data.sum(), sim)
        result = max(result, cand)
    print(result)


if __name__ == "__main__":
    main()

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()))
PP=[0]*n
A=[0]*n
V=[0]*n
for i in range(n):
  if V[i]==1:
    continue
  B=[i]
  c=1
  j=i
  p=C[i]
  while P[j]!=i:
    j=P[j]
    B.append(j)
    c=c+1
    p=p+C[j]
  for j in B:
    A[j]=c
    PP[j]=p
ans=-10**10
for i in range(n):
  if PP[i]<0:
    aans=0
    f=0
  else:
    if k//A[i]-1>0:
      aans=(k//A[i]-1)*PP[i]
      f=1
    else:
      aans=0
      f=2
  l=i
  aaans=-10**10
  if f==0:
    for j in range(min(k,A[i])):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  elif f==1:
    for j in range(k%A[i]+A[i]):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  else:
    for j in range(min(k,2*A[i])):
      aans=aans+C[P[l]]
      l=P[l]
      if aans>aaans:
        aaans=aans
  if aaans>ans:
    ans=aaans
print(ans)

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

for i in range(N):
    S = []
    j = P[i]-1
    S.append(C[j])

    while i != j:
        j = P[j]-1
        S.append(S[-1] + C[j])

    if K <= len(S):
        score = max(S[:K])

    elif S[-1] <= 0:
        score = max(S)
    
    else:
        score1 = K//len(S) * S[-1]
        r = K%len(S)
        if r != 0:
            score1 += max(0, max(S[:r]))
        score2 = (K//len(S)-1)*S[-1] + max(S)
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break
  L=len(cycle)
  t=0
  for i in range(L):
    t+=cycle[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)

print(ans)

Solution (Python):
from itertools import accumulate

n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [p - 1 for p in P]

check = [False] * n
loops = []

for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)

ans = int(-1e9)

for loop in loops:

    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = int(-1e9)
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k > num and sumL <= 0:
        r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))

    for i in range(num):
        for j in range(i + 1, i + r + 1):
            ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)

    ans = max(ans, ans_tmp)
print(ans)

Solution (Python):
from sys import stdin
input = stdin.readline

def main():
    N, K = map(int, input().rstrip().split())
    P = list(map(int, input().rstrip().split()))
    P = list(map(lambda x: x -1, P))
    C = list(map(int, input().rstrip().split()))
    ans = -10**18
    for i in range(N):
        x = i
        s = []
        total = 0
        while(True):
            x = P[x]
            s.append(C[x])
            total += C[x]
            if x == i:
                break
        l = len(s)
        t = 0
        for j in range(l):
            t += s[j]
            if j + 1 > K:
                break
            now = t
            if total > 0:
                e = (K - j - 1) // l
                now += total * e
            ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
 
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
P = [p-1 for p in P]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = 0
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = 0 
    by_loop = max(sum(L), 0) * div
    if k>num and by_loop == 0:
      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
if ans == 0:
    ans = max(C)
print(ans)