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()))
maximum = -10**9
for i in range(n):
    totalfull = 0; totalcut = 0; count = 0; location = i
    maximumfull = -10**9; maximumcut = -10**9
    for j in range(min(n, k)):
        location = p[location]-1
        totalfull += c[location]
        maximumfull = max(maximumfull, totalfull)
        count += 1
        if location == i: break
    for j in range(k%count):
        location = p[location]-1
        totalcut += c[location]
        maximumcut = max(maximumcut, totalcut)
    maximum = max(maximum, max(maximumfull, max((k//count-1)*totalfull+maximumfull, k//count*totalfull+maximumcut)))
print(maximum)

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=-float("inf")

for start in range(N):
    cur=P[start]
    scores=[C[cur]]
    for _ in range(K):
        if cur==start:
            break
        cur = P[cur]
        scores.append(C[cur]+scores[-1])

    for goal in range(len(scores)):
        no_loop_sum=scores[goal]
        remain_hops=K-goal-1

        if scores[-1]>0:
            loops=remain_hops//len(scores)
        else:
            loops=0
        ans=max(ans,no_loop_sum+scores[-1]*loops)
print(ans)

Solution (Python):
def find(vals,l):
    ans = -float('inf')
    for i in range(len(vals)//2):
        curr = vals[i+l-1]
        if i-1 >= 0:
            curr -= vals[i-1]

        ans = max(ans,curr)

    
    return ans

def dfs(edges,node,k,costs,visited):
    nodes = []
    stack = [node]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            nodes.append(node)
            stack.append(edges[node])

    vals = []
    for node in nodes:
        vals.append(costs[node-1])

    vals.extend(vals)
    for i in range(1,len(vals)):
        vals[i] += vals[i-1]

    total = vals[-1]//2
    if total >= 0:
        ans = total*(k//(len(vals)//2))
    else:
        ans = 0

    max_val = -float('inf')
    
    val = -float('inf')
    if k >= len(vals)//2:
        for i in range(1,len(vals)//2+1):
            max_val = max(max_val,find(vals,i))

        if total >= 0:
            max_val += ans-total

    
    val = -float('inf')
    
    k %= (len(vals)//2)
    
    for i in range(1,k+1):
        val = max(val,find(vals,i))

    return max(max_val,ans+val)

def main():
    n,k = map(int,input().split())
    perm = list(map(int,input().split()))
    costs = list(map(int,input().split()))
    edges = [-1]*(n+1)
    for i in range(n):
        edges[i+1] = perm[i]

    ans = -float('inf')
    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            ans = max(ans,dfs(edges,i,k,costs,visited))

    print(ans)

main()

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

frag, loop, lcnt = set(), [], []
for i in range(n):
    if i in frag:
        continue
    now, tmpl, tmpc = i, [], 0
    while (now not in frag):
        frag.add(now), tmpl.append(now)
        now = p[now] - 1
        tmpc += c[now]
    else:
        loop.append(tmpl * 2)
        lcnt.append(tmpc)

lacc = []
for l in loop:
    tmp = [0]
    for li in l[1:]: 
        tmp.append(tmp[-1] + c[li])
    lacc.append(tmp)

ans = min(c)
for l, la, lc in zip(loop, lacc, lcnt):
    llen = len(l) // 2
    num = k % llen
    for cnt in range(1, min(llen + 1, k + 1)):
        for i in range(len(l) - cnt - 1):
            tmp = la[i + cnt] - la[i]
            tmp2 = tmp + lc * (k // llen - (cnt > num))
            ans = max(ans, tmp, tmp2)
print(ans)

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



def main():
    n, k = map(int, input().split())
    p = [int(x)-1 for x in input().split()]
    c = list(map(int, input().split()))
    
    doubling = [[0]*n for i in range(31)]
    doubling_max = [[0]*n for i in range(31)]
    place = [[0]*n for i in range(31)]
    
    ans = -1000000000
    for i in range(n):
        sub = c[p[i]]
        if sub >= 0:
            break
        if ans < sub:
            ans = sub
        if i == n-1:
            print(ans)
            sys.exit()
            
    
    for i in range(31):
        if i == 0:
            for j in range(n):
                doubling[i][j] = c[p[j]]
                place[i][j] = p[j]
            continue
        for j in range(n):
            place[i][j] = place[i-1][place[i-1][j]]
            doubling[i][j] = doubling[i-1][j]+doubling[i-1][place[i-1][j]]
    
    for i in range(31):
        if i == 0:
            for j in range(n):
                doubling_max[i][j] = doubling[i][j]
            continue
        for j in range(n):
            doubling_max[i][j] = max(doubling_max[i-1][j], doubling[i-1][j]+doubling_max[i-1][place[i-1][j]])
    
    ans = 0
    judge = []
    key = 0
    while k:
        if k%2:
            judge.append(key)
        k //= 2
        key += 1
    judge.reverse()
    
    for i in range(n):
        pl = i
        key = 0
        for j in range(len(judge)):
            if ans < key+doubling_max[judge[j]][pl]:
                ans = key+doubling_max[judge[j]][pl]
            key += doubling[judge[j]][pl]
            pl = place[judge[j]][pl]
        

    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()))
INF = 10**18
ans = - INF
used = [0] * N
candidate = []

for i in range(N):
    if used[i]: continue
    now = i
    used[i] = 1
    tmp = [i]
    
    while P[now]-1 not in tmp:
        used[P[now]-1] = 1
        tmp.append(P[now]-1)
        now = P[now]-1

    candidate.append(tmp)

for tmp in candidate:
    M = len(tmp)
    accumT = []
    for t in tmp:
        accumT.append(C[t])
    loop = 3
    accumT = [0] + list(accumulate(accumT*loop))
    res = - INF

    if K <= M:
        for i in range(loop*M+1):
            for j in range(i+1,loop*M+1):
                if j-i > K:
                    break
                res = max(res,accumT[j]-accumT[i])
        ans = max(ans,res)
    else:
        SUM = accumT[M]
        if SUM > 0:
            addition = SUM * (K//M - 1)
            for i in range(loop*M+1):
                for j in range(i+1,loop*M+1):
                    if j-i > K%M+M:
                        break
                    res = max(res,accumT[j]-accumT[i])
            ans = max(ans,res+addition)
        else:
            for i in range(loop*M+1):
                for j in range(i+1,loop*M+1):
                    if j-i > M:
                        break
                    res = max(res,accumT[j]-accumT[i])
            ans = max(ans,res)
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P, C):
    P = [p-1 for p in P]

    done = set()
    cycles = []
    for i in range(N):
        c = i
        t = []
        while c not in done:
            n = P[c]
            done.add(c)
            t.append(c)
            c = n
        if t:
            cycles.append(t)

    ans = -INF
    for c in cycles:
        cs = sum(C[v] for v in c)
        if cs > 0:
            m = max(0, (K // len(c)) - 1)
            k = K - len(c) * m
            a = cs * m
            ans = max(ans, a)
        else:
            k = min(len(c), K)
            a = 0

        b = a
        for u in c:
            a = b
            for _ in range(k):
                v = P[u]
                a += C[v]
                ans = max(ans, a)
                u = v

    return ans


def main():
    N, K = read_int_n()
    P = read_int_n()
    C = read_int_n()
    print(slv(N, K, P, C))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,K = MI()
P = LI()
C = LI()

for i in range(N):
    if C[i] >= 0:
        break
else:
    print(max(C))
    exit()

from itertools import accumulate


def f(A):  
    a = len(A)
    res = 0
    if sum(A) > 0:
        if K // a > 0:
            res = sum(A) * (K // a - 1)
            r = K % a + a
        else:
            r = K % a
    else:
        r = K % a + a

    A = [0] + A + A + A
    S = list(accumulate(A))
    m = 0
    for i in range(a):
        for k in range(1, r + 1):
            b = S[i + k] - S[i]
            m = max(m, b)
    res += m
    return res


flag = [0]*N
ans = 0
for i in range(N-1):
    if flag[i] != 0:
        continue
    A = [C[i]]
    flag[i] = 1
    j = P[i]-1
    while j != i:
        A.append(C[j])
        flag[j] = 1
        j = P[j]-1
    ans = max(ans,f(A))

print(ans)

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

DP=[[C[P[n]]] for n in range(N)]

for start in range(N):
    visited=set()
    cur=P[start]
    while cur not in visited:
        visited.add(cur)
        cur = P[cur]
        DP[start].append(C[cur]+DP[start][-1])


for n in range(N):
    DP[n]=DP[n][:-1]

ans=-float("inf")

for start in range(N):
    for goal in range(min(K,len(DP[start]))):
        no_loop_sum=DP[start][goal]
        remain_hops=K-goal-1
        if DP[start][-1]>0:
            loops=remain_hops//len(DP[start])
        else:
            loops=0
        ans=max(ans,no_loop_sum+DP[start][-1]*loops)
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())


    p = [int(i)-1 for i in ipt().split()]


    c = [int(i) for i in ipt().split()]
    ma = -10**18
    al = [False]*n
    for i in range(n):
        if al[i]:
            continue
        pts = []
        nap = i
        for j in range(n):
            nap = p[nap]
            pts.append(c[nap])
            al[nap] = True
            if nap == i:
                break
        ln = len(pts)
        jt = k%ln+ln
        sma = 0
        for jp in pts:
            sma += jp
        if sma > 0:
            nm = (k//ln-1)*sma
        else:
            nm = 0
        pts *= 2
        ma1 = -10**18

        for ji in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[ji-jj]

                if ma1 < sm:
                    ma1 = sm
        ma1 += nm
        if ma < ma1:
            ma = ma1


    print(ma)




    return None

if __name__ == '__main__':
    main()

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

frag, loop, lcnt = set(), [], []
for i in range(n):
    if i in frag:
        continue
    now, tmp, tmpc = i, [], 0
    while True:
        frag.add(now), tmp.append(now)
        now = p[now] - 1
        tmpc += c[now]
        if now in frag:
            loop.append(tmp * 2)
            lcnt.append(tmpc)
            break

lacc = []
for l in loop:
    tmp = [0]
    for li in l[1:]: 
        tmp.append(tmp[-1] + c[li])
    lacc.append(tmp)

ans = min(c)
for l, la, lc in zip(loop, lacc, lcnt):
    llen = len(l) // 2
    num = k % llen
    for cnt in range(1, min(llen + 1, k + 1)):
        for i in range(len(l) - cnt - 1):
            tmp = la[i + cnt] - la[i]
            tmp2 = tmp + lc * (k // llen - (cnt > num))
            ans = max(ans, tmp, tmp2)
print(ans)

Solution (Python):
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def calc(arr, k):
    s = sum(arr)
    n = len(arr)
    kp = k % n if s > 0 else k
    if kp == 0:
        kp = n

    ll = min(kp, n)
    cm = max(arr)
    for i in range(n):
        cn = 0
        for ki in range(i, i+ll):
            cn += arr[ki % n]
            cm = max(cn, cm)

    if s > 0:
        return s * ((k-1)//n) + cm
    else:
        return cm


def main():
    n, k = _ia()
    p = list(map(lambda x: x-1, _ia()))
    c = list(_ia())

    f = [False] * n
    g = []
    for idx in range(n):
        if f[idx]:
            continue

        nxt = idx
        tmp = [c[nxt]]
        f[nxt] = True

        for _ in range(n):
            nxt = p[nxt]
            if nxt == idx:
                break
            tmp.append(c[nxt])
            f[nxt] = True

        g.append(tmp)

    return max(calc(gi, k) for gi in g)


if __name__ == "__main__":
    print(main())

Solution (Python):
n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = float('-inf')

ans = minc


def get_loop(i):
    pos = i
    cnt = 0
    cur_score = 0
    while cnt == 0 or pos != i:
        pos = p[pos]
        cur_score = cur_score + c[pos]
        cnt += 1
    return cnt, cur_score



def solve(pos, k):
    score = minc
    cur_score = 0
    loop_length, loop_score = get_loop(pos)
    if k >= 2 * loop_length and loop_score > 0:
        
        cur_score = loop_score * ((k - loop_length) // loop_length)
        score = max(cur_score, score)
        k = k % loop_length + loop_length
    else:
        k = min(k, 2 * loop_length)
    for _ in range(k):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    
    return score

for i in range(n):
    ans = max(ans, solve(i, k))
print(ans)

Solution (Python):
n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
CC = [[] for _ in range(n)]
for idx, p in enumerate(P):
    CC[idx].append(C[p])
    pp = P[p]
    for _ in range(n):
        CC[idx].append(C[pp])
        pp = P[pp]
        if pp == p:
            break
        
from itertools import accumulate
ans = -2*(10**9)
for cc in CC:
    cca = list(accumulate(cc))
    if cca[-1] <= 0:
        
        if k < len(cc):
            ans = max(ans, max(cca[:k]))
        else:
            ans = max(ans, max(cca))
    else:
        
        kk, r = divmod(k, len(cc))
        if r == 0:
            ans = max(ans, kk*cca[-1], (kk-1)*cca[-1]+max(cca))
        else:
            ans = max(ans, kk*cca[-1] + max(cca[:r]))
print(ans)

Solution (Python):
n,k = map(int,input().split())
p = list(map(int,input().split()))
used = [0]*n
c = list(map(int,input().split()))
ans = -float("INF")
def calc(x):
    l = []
    now = x
    score = 0
    while used[now] == 0:
        used[now] = 1
        l.append(c[now])
        now = p[now]-1
    S = sum(l)
    le = len(l)
    if S > 0 and k > le:
        score += (k//le-1)*S
        mod = k%le
        now = 0
        for i in range(le):
            cal = 0
            for j in range(le):
                if j <= mod:
                    now = max(now,cal+S)
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    else:
        mod = min(le,k)
        now = -float("INF")
        for i in range(le):
            cal = 0
            for j in range(mod):
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    
for i in range(n):
    if used[i] == 0:
        ans = max(ans,calc(i))
print(ans)

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


def read():
    N, K = map(int, input().strip().split())
    P = [0] + list(map(int, input().strip().split()))
    C = [0] + list(map(int, input().strip().split()))
    return N, K, P, C


def solve(N, K, P, C):
    max_score = -10**9
    
    for i in range(1, N+1):
        
        D = [0 for i in range(N+1)]
        
        size = 0
        
        j = i
        score = 0
        while True:
            size += 1
            j = P[j]
            D[size] = D[size-1] + C[P[j]]
            if i == j:
                break
        round_score = D[size]
        for i in range(1, min(K, size)+1):
            max_score = max(max_score, D[i])
        
        if D[size] > 0 and K > size:
            base_score = round_score * ((K // size)-1)
            max_score = max(max_score, base_score)
            for i in range(1, size+1):
                max_score = max(max_score, base_score + D[i])
            base_score = round_score * (K // size)
            for i in range(1, min(K%size, size)+1):
                max_score = max(max_score, base_score + D[i])
    return max_score


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
n,k = map(int,input().split())
p = list(map(int,input().split()))
used = [0]*n
c = list(map(int,input().split()))
ans = -float("INF")
def calc(x):
    l = []
    now = x
    score = 0
    while used[now] == 0:
        used[now] = 1
        l.append(c[now])
        now = p[now]-1
    S = sum(l)
    le = len(l)
    if S > 0 and k > le:
        score += (k//le-1)*S
        mod = k%le+le
        now = 0
        for i in range(le):
            cal = 0
            for j in range(mod):
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    else:
        mod = min(le,k)
        now = -float("INF")
        for i in range(le):
            cal = 0
            for j in range(mod):
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    
for i in range(n):
    if used[i] == 0:
        ans = max(ans,calc(i))
print(ans)

Solution (Python):
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
g = []
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g.append(y)
  else:
    g.append(max(e))
print(max(g))

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

data = [[0 for i in range(n+1)] for j in range(n)]
loop = [10**10 for i in range(n)]
for i in range(n):
    j = i
    for t in range(1,n+1):
        j = p[j]
        data[i][t] += data[i][t-1] + c[j]
        if j == i:
            loop[i] = min(loop[i],t)

ans = -10**10



for i in range(n):
    for j in range(1,min(n,k)+1):
        if j > loop[i]:break
        if data[i][loop[i]] <= 0:
            ans = max(ans,data[i][j])
        else:
            ans = max(ans,data[i][loop[i]]*((k-j)//loop[i])+data[i][j])

print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]

ans = -float('inf')
for i in range(n):
    now = i
    c_sum = [0]
    s = set()
    cnt = 0
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        cnt += 1
        now = p[now]
        if now in s:
            break
    c_sum = c_sum[1:]
    if k < cnt:
        ans = max(ans, max(c_sum[: k]))
    else:
        score = c_sum[-1]
        count = k // cnt
        k_ = k - count*cnt
        score *= count
        score_2 = score - c_sum[-1]
        score_2 += max(c_sum)
        if k_ > 0:
            score += max(0, max(c_sum[:k_]))
        ans = max(ans, score, max(c_sum), score_2)
print(ans)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**18
m = 10**9 + 7

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

    ans = - INF
    used = [0] * N
    candidate = []

    for i in range(N):
        if used[i]: continue
        now = i
        used[i] = 1
        tmp = [i]
        
        while P[now]-1 not in tmp:
            used[P[now]-1] = 1
            tmp.append(P[now]-1)
            now = P[now]-1
        
        candidate.append(tmp)

    
    for tmp in candidate:
        M = len(tmp)
        accumT = []
        for t in tmp:
            accumT.append(C[t])
        loop = 3
        accumT = [0] + list(accumulate(accumT*loop))
        res = - INF

        if K <= M:
            for i in range(loop*M+1):
                for j in range(i+1,loop*M+1):
                    if j - i > K: 
                        break
                    res = max(res,accumT[j]-accumT[i])
            ans = max(ans,res)
        else:
            SUM = accumT[M]
            if SUM > 0:
                addition = SUM * (K//M - 1)
                for i in range(loop*M+1):
                    for j in range(i+1,loop*M+1):
                        if j - i > K%M+M:
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res+addition)
            else:
                for i in range(loop*M+1):
                    for j in range(i+1,loop*M+1):
                        if j - i > M:
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	n, k = tin()
	
	al = lin()
	cl=lin()
	dd=[0]*n
	for i in range(n):
		if dd[i]!=0:
			continue
		cc=set()
		pos = i
		point=0
		n_node=0
		while pos not in cc:
			cc.add(pos)
			pos=al[pos]-1
			point+=cl[pos]
			n_node+=1
			
		for p in cc:
			dd[p] = (point, n_node)
	
	ret=-mod*mod
	for i in range(n):
		pi, ni = dd[i]
		if pi < 0:
			point=0
			pmax=-mod*mod
			pos=i
			for _ in range(ni):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(pmax, point)
			ret = max(ret, pmax)
		elif k < ni*2:
			point=0
			pmax=-mod*mod
			pos=i
			for _ in range(k):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(pmax, point)
			ret = max(ret, pmax)
		else:
			point = pi*((k//ni)-1)
			nk=k%(ni) + ni
			pos = i
			pmax = point
			for _ in range(nk):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(point, pmax)
			ret = max(ret, pmax)
	return ret
		
		
			
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
p = LI()
c = LI()
C = []
S = []
for i in range(n):
    lst = [-1]*n
    cnt = 0
    idx = i
    s = 0
    while lst[idx] == -1:
        lst[idx] = cnt
        s += c[idx]
        cnt += 1
        idx = p[idx] - 1
    C.append(cnt)
    S.append(s)

if n >= k:
    ans = -10**10
    for i in range(n):
        cnt = 0
        ret = 0
        idx = p[i]
        while cnt < k:
            ret += c[idx-1]
            idx = p[idx-1]
            cnt += 1
            ans = max(ans, ret)
    print(ans)
else:
    ans = -10**10
    for i in range(n):
        if S[i] > 0:
            tmp = S[i] * (k // C[i])
            r = k % C[i]
            cnt = 0
            ret = 0
            idx = p[i]
            if r == 0:
                tmp -= S[i]
                r = C[i]
            while cnt < r:
                ret += c[idx-1]
                idx = p[idx-1]
                cnt += 1
                ans = max(ans, tmp + ret)
        else:
            cnt = 0
            ret = 0
            idx = p[i]
            while cnt < n:
                ret += c[idx-1]
                idx = p[idx-1]
                cnt += 1
                ans = max(ans, ret)
    print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())


    p = [int(i)-1 for i in ipt().split()]


    c = [int(i) for i in ipt().split()]
    ma = -10**18
    al = [False]*n
    for i in range(n):
        if al[i]:
            continue
        pts = []
        nap = i
        for j in range(n):
            nap = p[nap]
            pts.append(c[nap])
            al[nap] = True
            if nap == i:
                break
        ln = len(pts)
        jt = (k-1)%ln
        jt += 1+ln
        sma = 0
        for jp in pts:
            sma += jp
        if sma > 0:
            nm = ((k-1)//ln-1)*sma
        else:
            nm = 0
        pts *= 2
        ma1 = -10**18

        for ji in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[ji-jj]

                if ma1 < sm:
                    ma1 = sm
        ma1 += nm
        if ma < ma1:
            ma = ma1


    print(ma)




    return None

if __name__ == '__main__':
    main()

Solution (Python):
N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10**9-1
for i in range(N):
    cumsum = [0]*(N+1)
    seen = [-1]*N
    K_ = K
    now = i
    j = 0
    while K_ > 0 and seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        K_ -= 1
        j += 1
    if K_ == 0:
        ans = max(ans, max(cumsum[1:j+1]))
    else:
        if cumsum[j] > 0:
            loop_size = j
            loop_n = K//loop_size - 1
            tmp = loop_n*cumsum[loop_size]
            tmp += max(max(cumsum[1:loop_size+1]), cumsum[loop_size] + max(cumsum[0:K_%loop_size+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j+1]))
print(ans)

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

visited = [False for _ in range(n)]
lp = []
lp_cum = []

ans = -10**9
for i in range(n):
	if not visited[i]:
		lp.append([i])
		lp_cum.append([0, c[i]])
		visited[i] = True
		while not visited[p[lp[-1][-1]]]:
			lp[-1].append(p[lp[-1][-1]])
			lp_cum[-1].append(lp_cum[-1][-1] + c[lp[-1][-1]])
			visited[lp[-1][-1]] = True
		t_sum, t_num = lp_cum[-1][-1], len(lp[-1])
		for x in range(1, len(lp_cum[-1])):
			for y in range(x):
				r_sum, r_num = lp_cum[-1][x] - lp_cum[-1][y], x-y
				if t_sum <= 0:
					if r_num <= k:
						ans = max(ans, r_sum)
				else:
					if r_num <= k:
						ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))
				if x < len(lp_cum[-1])-1 or y > 0:
					r_sum, r_num = lp_cum[-1][-1] - lp_cum[-1][x] + lp_cum[-1][y], len(lp[-1])-x+y
					if t_sum <= 0:
						if r_num <= k:
							ans = max(ans, r_sum)
					else:
						if r_num <= k:
							ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))

print(ans)