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):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

    x = [False] * (N+1)

    ans = -INF
    for i in range(1,N+1):
        
        z = [0] * (N+1)
        y = [0] * (N+1)
        cnt = 0
        cnt_max = -INF
        z[i] = 1
        q = collections.deque()
        q.append(i)
        j = 1
        while q:
            u = q.popleft()
            x[u] = True

            v = P[u-1]
            cnt += C[v-1]
            y[u] = cnt
            cnt_max = max(cnt,cnt_max)
            if j >= K:
                break
            j += 1
            if z[v] > 0:
                r = j - z[v]
                cnt += ((K - j) // r) * (cnt+C[P[v-1]-1]-y[v])
                j += r * ((K - j) // r)
                z = [0] * (N+1)
                cnt_max = max(cnt,cnt_max)
                q.append((v))
            else:
                z[v] = j
                q.append(v)
        ans = max(ans,cnt_max)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    P = tuple(map(lambda x: int(x) - 1, input().split()))
    C = tuple(map(int, input().split()))
    ans = -10**18

    for i in range(N):
        k = K
        D = [[0, 0] for i in range(N)]
        x = i
        X, Y = 0, 0
        count = 0
        score = 0
        for j in range(K):
            if D[P[x]][0] == 0:
                score += C[P[x]]
                D[P[x]][0] = score
                D[P[x]][1] = count
                x = P[x]
                count += 1
            else:
                X = D[P[x]][0] - C[P[x]]
                score -= X
                L = (count - D[P[x]][1])
                k -= D[P[x]][1]

                score *= (k // L) - 1
                l = (K % L) + L
                score += X
                ans = max(ans, score)
                for _ in range(l):
                    score += C[P[x]]
                    ans = max(ans, score)
                    x = P[x]

                break
            if score > ans:
                ans = score
    print(ans)


main()

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


inf = float("inf")


ans = max(C)  
for pos in range(N):
    i = pos
    score = 0
    cycleLen = None
    cycleGain = None
    bestInc = 0
    k = 0
    while k < K:
        i = P[i]
        score += C[i]
        ans = max(ans, score)

        if i == pos:
            cycleLen = k + 1
            numCycles = max(0, (K - k - cycleLen) // cycleLen)
            if k + numCycles * cycleLen < K:
                k += numCycles * cycleLen
                score += numCycles * score
        k += 1

print(ans)

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()))
if max(c) <= 0:
    print(max(c))
    exit()
ans = 0
for begin in range(n):
    i = p[begin]
    s = c[i]
    round = 1
    score = 0
    kk = 0
    while i != begin:
        i = p[i]
        s += c[i]
        round += 1
    if k < round:
        kk = k
    else:
        if s > 0:
            score += s * (k // round)
            kk = k % round
        else:
            kk = round
    smax = 0
    now = 0
    i = begin
    while kk > 0:
        i = p[i]
        now += c[i]
        smax = max(now, smax)
        kk -= 1
    roundmax = 0
    if k // round >= 1 and s > 0:
        kk = round
        now = 0
        i = begin
        while kk > 0:
            i = p[i]
            now += c[i]
            roundmax = max(now, roundmax)
            kk -= 1
        ans = max(ans, score-s+roundmax, score+smax)
    else:
        ans = max(ans, score + smax)

print(ans)

Solution (Python):
n,k = map(int, input().split())
pl = [0] + list(map(int, input().split()))
cl = [0] + list(map(int, input().split()))

ans = (10**18)*(-1)
for start in range(1,n+1):
    val = 0
    vals = []
    already_set = set()
    curr_mass = start
    while True:
        next_mass = pl[curr_mass]
        point = cl[next_mass]
        if next_mass in already_set:
            break
        else:
            vals.append(point)
            already_set.add(next_mass)
            curr_mass = next_mass
    
    if k <= len(vals):
        c_max = vals[0]
        c_val = vals[0]
        
        for v in vals[1:k]:
            c_val += v
            c_max = max(c_max, c_val)
        
        ans = max(c_max,ans)
    else:
        v_sum = sum(vals)
        if v_sum <= 0:
            c_max = vals[0]
            c_val = vals[0]
            
            for v in vals[1:]:
                c_val += v
                c_max = max(c_max, c_val)
            
            ans = max(c_max,ans)
        else:
            if k%len(vals) > 0:
                loop_cnt = k//len(vals)
                rem = k - loop_cnt*len(vals)
                c_max = v_sum*loop_cnt
                c_val = v_sum*loop_cnt
                if rem > 0:
                    for v in vals[:rem]:
                        c_val += v
                        c_max = max(c_max, c_val)
                
                ans = max(c_max,ans)
            else:
                loop_cnt = k//len(vals) - 1
                rem = len(vals)
                c_max = v_sum*loop_cnt
                c_val = v_sum*loop_cnt
                if rem > 0:
                    for v in vals[:rem]:
                        c_val += v
                        c_max = max(c_max, c_val)
                
                ans = max(c_max,ans)
    
print(ans)

Solution (Python):
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()



N, K = In.ints()

P = In.ints()
C = [-1] + In.ints()

connection = [-1 for i in range(N+1)]

for i in range(N):
    connection[i+1] = P[i]

ans = -99999999999

for i in range(1, N+1):
    start = connection[i]
    tempans = C[start]
    tempk = K-1

    ans = max(ans, tempans)
    seen = [False for i in range(N+1)]
    seen[start] = True    

    while tempk > 0:
        nex = connection[start]
        if not seen[nex]:
            start=nex
            seen[start]=True
            tempans += C[start]
            ans = max(ans, tempans)
            tempk-=1            
        else:
            break
    
    if tempk>N:
        if tempans<0:
            continue
        
        
        stepsround = K-tempk
        howManyRounds = (tempk//stepsround)-1

        tempans += tempans*howManyRounds
        tempk-=howManyRounds*stepsround

        ans = max(ans, tempans)
    
    while tempk > 0:        
        start=connection[start]            
        tempans += C[start]
        ans = max(ans, tempans)
        tempk-=1            



Out.int(ans)




if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

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

max_score = -10 ** 9 - 1
for i in range(n):
    tmp_score=-10**9 -1
    score = 0
    count = 0
    next_point = p[i] - 1
    while next_point != i and count < k:
        score += c[next_point]
        next_point = p[next_point] - 1
        count += 1
        if tmp_score < score:
            tmp_score = score
            max_count = count
    if count < k:
        score += c[next_point]
        count += 1
    if tmp_score < score:
        tmp_score = score
        max_count = count

    cycle_score = score
    if cycle_score > 0 and count < k:
        score = cycle_score * (k // count)
        tmp_k = k - ((k // count)*count)
        count=0
        next_point=p[i]-1
        under_k_score=-10**9-1
        score2=0
        while next_point != i and count < tmp_k:
            score2 += c[next_point]
            next_point = p[next_point] - 1
            count += 1
            if under_k_score < score2:
                under_k_score = score2
                max_count = count
        if under_k_score+cycle_score > tmp_score:
            score += under_k_score
        else:
            score += -cycle_score + tmp_score
        if max_score < score:
            max_score=score
    else:
        if max_score < tmp_score:
            max_score=tmp_score

print(max_score)

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()))
loops = []
used = set()
for i in range(n):
    if i in used:
        continue
    used.add(i)
    tmp = [i]
    nxt = p[i]
    while nxt not in used:
        tmp.append(nxt)
        used.add(nxt)
        nxt = p[nxt]
    loops.append(tmp)

def calc(l,r,cs):
    if r == 0:
        return 0
    tmp = -float("inf")
    for i in range(2*l):
        for j in range(i+1, min(2*l, i+r)+1):
            x = cs[j] - cs[i]
            if tmp < x:
                tmp = x
    return tmp

ans = -float("inf")

for loop in loops:
    s = sum(c[i] for i in loop)
    l = len(loop)
    tmp_loop_score = [c[i] for i in loop]
    for i in loop:
        tmp_loop_score.append(c[i])

    tmp_ans_max = max(tmp_loop_score)
    ans = max(ans, tmp_ans_max)

    cs = [0]
    for i in range(2*l):
        cs.append(cs[-1] + tmp_loop_score[i])

    if s > 0:
        m = k//l
        tmp_ans = m*s
        r = k%l
        tmp_ans += calc(l,r,cs)
        r = min(l, k)
        tmp_ans = max(tmp_ans, calc(l,r,cs))
        if m > 0:
            tmp = (m-1)*s
            r = (k%l) + l
            tmp += calc(l,r,cs)
            tmp_ans = max(tmp, tmp_ans)
    else:
        r = min(2*l, k)
        tmp_ans = calc(l,r,cs)

    ans = max(ans, tmp_ans)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n,k = l_in()
P = l_in()
C = l_in()

s = min(k,n)

res = -(10**10)
for start in range(n):
    j = start
    current = 0
    tmp = -(10**10)
    for i in range(1, k+1):
        j = P[j]-1
        current += C[j]
        tmp = max(tmp, current)
        if j == start:
 

            loop=current
            
            if current > 0:
                s = k%i
                add = current*(k//i)

                j = start
                current = 0

                for i2 in range(1, s+1):
                    j = P[j]-1
                    current += C[j]
                    tmp = max(tmp, current+add)


                if k//i >= 2:
                    add = loop*(k//i - 1) 
                    j = start
                    current = 0

                    for _ in range(i): 
                        j = P[j]-1
                        current += C[j]
                        tmp = max(tmp, current+add)
            break
                
    res = max(tmp, res)
    
print(res)

Solution (Python):

import sys


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):
    res = - 10 ** 10
    for i in range(N):
        lmax = - 10 ** 10
        nlmax = 0
        cp = P[i] - 1
        cl = 1
        cs = C[cp]
        css = []
        css.append(cs)
        while cp != i:
            if cs > lmax and cl <= K:
                lmax = cs
                nlmax = cl
            cp = P[cp] - 1
            cl += 1
            cs += C[cp]
            css.append(cs)
        if cs > lmax and cl <= K:
            lmax = cs
            nlmax = cl
        syc = cs
        length = cl
        
        nloop = max(0, K // length - 1)
        x = K % length
        if K // length >= 1:
            nokori = lmax
            for j in range(x):
                nokori = max(nokori, syc + css[j])
        else:
            nokori = lmax
        res = max(res, max(lmax, syc * nloop + nokori))
        
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    P = [int(next(tokens)) for _ in range(N)]  
    C = [int(next(tokens)) for _ in range(N)]  
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
from collections import deque
import itertools
import heapq

from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint




def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    
    n,k = map(int, input().split())
    p=list(map(int,input().split()))
    c = list(map(int, input().split()))
    loop=min(n,k)
    score=-INFI
    arr=set()
    loopscore=[]
    tempscore=0
    for i in range(n):
        temp=i
        arr = set()
        loopscore = []
        temp2=0
        iscore=0
        tempscore=0
        for j in range(loop):
            if p[temp]-1 in arr:
                break
            tempscore+=c[p[temp]-1]
            arr.add(p[temp]-1)
            temp=p[temp]-1
            loopscore.append(tempscore)

        if len(loopscore)<k:
            if loopscore[-1]>0:
                temp2=k//len(loopscore)-1
                if temp2<=0:
                    temp2=0
            iscore=temp2*loopscore[-1]
            nokori = k - (temp2 * len(loopscore))
            last=loopscore[-1]
            temploop=list(map(lambda x: x+last,loopscore))
            loopscore.extend(temploop)

            nokoriscore=max(loopscore[:nokori])
            iscore+=nokoriscore
        else:
            iscore=max(loopscore[:k])
        score=max(score,iscore)

    print(score)




if __name__ == "__main__":

    main()

Solution (Python):
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Cs = list(map(int, input().split()))

cycles = []
cycleSums = []
visited = [False]*N
for i, p in enumerate(Ps):
    if visited[i]:
        continue
    cycle = []
    now = i
    S = 0
    while not visited[now]:
        visited[now] = True
        now = Ps[now] - 1
        cycle.append(Cs[now])
        S += Cs[now]
    cycles.append(cycle)
    cycleSums.append(S)

ans = float('-inf')
for cycle, cycleSum in zip(cycles, cycleSums):
    L = len(cycle)
    cycle = cycle + cycle
    DPL = L + 1
    DPL2 = K % L + 1
    M = float('-inf')
    M2 = float('-inf')
    dp = [None]*DPL
    dp[0] = 0
    for c in cycle:
        ndp = [None]*DPL
        ndp[0] = 0
        for i in range(1, DPL):
            if dp[i-1] is None:
                break
            tmp = dp[i-1] + c
            ndp[i] = 0 if 0 > tmp else tmp
            M = M if M > tmp else tmp
            if i < DPL2:
                M2 = M2 if M2 > tmp else tmp
        dp = ndp
    if cycleSum > 0:
        if K % L != 0:
            tmp = cycleSum * (K // L) + M2
            tmp2 = cycleSum * ((K // L)-1) + M
            tmp = tmp if tmp > tmp2 else tmp2
        else:
            tmp = cycleSum * ((K // L)-1) + M
    else:
        tmp = M
    ans = ans if ans > tmp else tmp

print(ans)

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

score = [[] for _ in range(n)]
for i in range(1, n + 1):
    x = [i]
    s = 0
    while True:
        x.append(p[x[-1] - 1])
        s += c[x[-1] - 1]
        score[i - 1].append(s)
        if x[-1] == i:
            break

ans = -1e20
for i in range(n):
    l = len(score[i])
    for j in range(min(k, l)):
        tmp = score[i][j]
        if 0 < score[i][-1]:
            tmp += ((k - j - 1) // l) * score[i][-1]
        ans = max(tmp, ans)
print(ans)

Solution (Python):
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
ps = [p-1 for p in ps]
visited = [False] * n
from collections import deque
ds = []
sums = []
for i in range(n):
    if visited[i]: continue
    q = deque([])
    q.append(i)
    s = cs[i]
    d = [i]
    while len(q) > 0:
        u = q.popleft()
        visited[u] = True
        nx = ps[u]
        if visited[nx]: continue
        d.append(nx)
        q.append(nx)
        s += cs[nx]
    sums.append(s)
    ds.append(d)


from itertools import accumulate
def calcmax(d,s,k,cs):
    cnt = 0
    l = len(d)
    div, rest_ = divmod(k-1, l)
    rest_ += 1
    if s > 0:
        cnt += div*s
    d2 = d*2
    c_ = [cs[j] for j in d2]
    acc = list(accumulate(c_))
    mx = - 1<<50
    if s < 0:
        for rest in range(1,l+1):
            for i in range(rest,l*2):
                c = acc[i] - acc[i-rest]
                mx = max(mx,c)
        return mx
    for rest in range(1,rest_+1):
        for i in range(rest,l*2):
            c = acc[i] - acc[i-rest]
            
            mx = max(mx, c)
    
    return cnt + mx

ans = -1 << 50
for d,s in zip(ds,sums):
    
    c = calcmax(d,s,k,cs)
    ans = max(ans,c)
print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))
    S = 0
    M = C[0]

    for s in range(N):
        t = 0
        p = s
        m = C[s]
        i = 0
        skipped = False
        while i < K:
            t += C[p]
            p = P[p]
            i += 1
            m = max(m, t)
            if p == s and not skipped:
                if t <= 0:
                    break
                skipped = True
                skip = K // i - 2
                if skip < 1:
                    continue
                t += t * skip
                m = max(m, t)
                i += i * skip
        M = max(M, m)

    return M

print(main())

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
if K == 1:
    print(max(C))
    import sys
    sys.exit()
uf = UnionFind(N)
for i in range(N):
    uf.union(i, P[i]-1)

ans = -float("inf")
for x in uf.all_group_members().values():
    n = len(x)
    m_score = [-float("inf")] * (n+1)
    m_score[0] = 0
    sum_c = 0
    for i in x:
        tmp_score = 0
        tmp_pos = i
        sum_c += C[i]
        for j in range(n):
            tmp_pos = P[tmp_pos]
            tmp_pos -= 1
            tmp_score += C[tmp_pos]
            m_score[j+1] = max(tmp_score, m_score[j+1])
    if sum_c <= 0:
        ans = max(max(m_score[1:]), ans)
    elif K <= n:
        ans = max(ans, max(m_score[1:K+1]))
    elif K % n == 0:
        ans = max(sum_c * (K//n-1) + max(m_score[1:]), ans) 
    else:
        ans = max(sum_c * (K//n) + max(m_score[:(K%n)+1]), ans)
print(ans)

Solution (Python):
n, k = map(int, input().split())
Ps = list(map(int, input().split()))
Ps.insert(0,0)
Cs = list(map(int, input().split()))
Cs.insert(0,0)
Ls = [0] * (n + 1)  
As = [0] * (n) 


for i in range(1,n + 1):
  count = 1
  temp = Ps[i]
  while temp != i:
    temp = Ps[temp]
    count += 1
  Ls[i] = count


for i in range(1, n + 1):
  ans = 0
  p = [0] * Ls[i]  
  tempIndex = i
  tempSum = 0
  for j in range(Ls[i]):
    tempIndex = Ps[tempIndex]
    tempSum += Cs[tempIndex]
    p[j] = tempSum
  
  
  if p[-1] <= 0:
    ans = max(p[:min(k,Ls[i])])
  else:
    q, r = divmod(k, Ls[i])
    
    start = (q - 1) * p[-1]
    anss = [0] * (r + Ls[i])
    anss.insert(0, start)
    tempIndex = i
    tempSum = start
    for z in range(r + Ls[i]): 
      tempIndex = Ps[tempIndex]
      tempSum += Cs[tempIndex]
      anss[z + 1] = tempSum
    ans = max(anss)
  As[i-1] = ans
print(max(As))

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

been = [False]*N
n_been=0
loops = []

while True:
    
    for i in range(N):
        if not been[i]:
            now=i
            break
    else:
        break
    cand=[]       
    for _ in range(N):
        if been[now]:
            break
        else:
            cand.append(C[now])
            been[now]=True

        now = P[now]-1
    loops.append(cand)

ans=-10**20
for l in loops:
    m=len(l)
    sum_l = sum(l)
    
    rui =[None]*(m+1)
    rui[0]=0
    for i in range(m):
        rui[i+1] = rui[i]+l[i]

    if sum_l>0:
        k_gene = range(max(0,K-m), K+1)
    else:
        k_gene = range(1,min(m,K)+1)
    for k in k_gene:
        for i in range(m):
            if m-i>=k:

                cand =rui[i+k]-rui[i]
            else:

                cand = rui[-1]-rui[i] +sum_l* ((k-m+i)//m) + rui[(k-m+i)%m] 
            ans=max(ans,cand)
            

print(ans)

Solution (Python):
n,k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
l = []
check = [True]*n
for i in range(1,n+1):
    if (check[i-1]==True):
        s = i
        sl = []
        tnp = i
        for j in range(n):
            tnp = p[tnp-1]
            check[tnp-1] = False
            sl.append(c[tnp-1])
            if (tnp==s):
                break
        l.append(sl)

ans = -float("inf")
for i in range(len(l)):
    if (len(l[i])<=k):
        if (sum(l[i])>0):
            x = k%len(l[i])
            if (x==0):
                tnp = 0
            else:
                tnp = -float("inf")
            for p in range(1,x+1):
                wa = sum(l[i][:p])
                tnp = max(tnp,wa)
                for j in range(len(l[i])):
                    wa -= l[i][j]
                    wa += l[i][(j+p)%len(l[i])]
                    tnp = max(tnp,wa)
            ans = max(ans, tnp + sum(l[i])*(k//len(l[i])) )
    tnp = -float("inf")
    for p in range(1,min(k,len(l[i]))+1):
        wa = sum(l[i][:p])
        tnp = max(tnp,wa)
        for j in range(len(l[i])):
            wa -= l[i][j]
            wa += l[i][(j+p)%len(l[i])]
            tnp = max(tnp,wa)
    ans = max(ans, tnp)
    if (len(l[i])<=k and sum(l[i])>0):
        ans = max(ans, tnp+sum(l[i])*(k//len(l[i])-1))
print(ans)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,k, = map(int,readline().split())
*p, = map(int,readline().split())
*c, = map(int,readline().split())

for i in range(n): p[i] -= 1

ans = [-1<<31]*n
pos = list(range(n))
val = [0]*n
for i in range(min(k,n)):

    for j in range(n):
        pos[j] = p[pos[j]]
        val[j] += c[pos[j]]
        if ans[j] < val[j]: ans[j] = val[j]



    
    

pos = list(range(n))
val = [0]*n

pp = p[:]
vv = [c[p[j]] for j in range(n)]

k -= n

if k < 0:
    print(max(ans))
    
    exit()



for i in range(31):
    vvv = vv[:]
    ppp = pp[:]
    if k&1:
        for j in range(n):
            val[j] += vvv[pos[j]]
            pos[j] = pp[pos[j]]
        
    
    
    for j in range(n):
        vvv[j] += vv[pp[j]]
    for j in range(n):
        ppp[j] = pp[pp[j]]
    vv = vvv
    pp = ppp
    
    k >>= 1



for i in range(n):
    for j in range(n):
        pos[j] = p[pos[j]]
        val[j] += c[pos[j]]
        if ans[j] < val[j]: ans[j] = val[j]


print(max(ans))

Solution (Python):
LI = lambda: list(map(int, input().split()))

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

INF = 10 ** 10


def all_minus():
    for c in C:
        if c > 0:
            return False
    return True


def main():
    if all_minus():
        ans = max(C)
        print(ans)
        return
        
    ans = -INF
    for i in range(N):
        w = [0]
        d = {i: 0}
        j = 1
        x = P[i] - 1
        while x not in d:
            d[x] = j
            w.append(w[j - 1] + C[x])
            x = P[x] - 1
            j += 1

        a, b = d[x], j
        for _ in range(b - a):
            w.append(w[-1] + C[x])
            x = P[x] - 1

        if K < 2 * b - a or w[b] - w[a] <= 0:
            v = max(w[:K + 1])
            ans = max(ans, v)
            continue
        
        v = w[a]
        k = K - a
        r = k // (b - a) - 1
        k -= r * (b - a)
        v += r * (w[b] - w[a])
        v += max(w[a : a + k + 1]) - w[a]
        ans = max(ans, v)
    print(ans)
        
                
if __name__ == "__main__":
    main()

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

R = [False] * (N+1)
S = []

for st in range(1, N+1):
    if R[st]: continue
    loop = []
    x = st
    while not R[x]:
        loop.append(C[x])
        R[x] = True
        x = P[x]

    if max(loop)<=0:
        S.append(max(loop))
        continue

    L = len(loop)
    K0 = K//L
    K1 = K%L

    T = [0]
    for c in loop: T.append(T[-1]+c)
    tot = T[-1]

    smax = smax_l = 0
    for i in range(L):
        for j in range(i, L):
            l = j-i+1
            
            ss = T[j+1]-T[i]
            smax = max(smax, ss)
            smax = max(smax, tot-ss)
            if l  <=K1: smax_l = max(smax_l, ss)
            if L-l<=K1: smax_l = max(smax_l, tot-ss)

    s = smax_l + K0*max(0,tot)
    if K0>0: s = max(s, smax+(K0-1)*max(0,tot))
    S.append(s)

print(max(S))