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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    p = list(map(int, readline().split()))
    p = [x - 1 for x in p]
    c = list(map(int, readline().split()))
    ans = -INF

    for i in range(n):
        cur = i
        nx = -1
        cnt = 0
        score_dict = dict()
        score_dict[0] = 0
        score = 0
        rem = k
        while rem > 0 and nx != i:
            cnt += 1
            rem -= 1
            nx = p[cur]
            score += c[nx]
            score_dict[cnt] = score
            ans = max(ans, score)
            cur = nx

        if rem > 0 and score > 0:
            loop = (rem - 1) // cnt
            if loop > 0:
                score += score * loop
                rem -= loop * cnt
            for j in range(rem + 1):
                st = score + score_dict[j]
                ans = max(ans, st)

    print(ans)


if __name__ == '__main__':
    main()

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

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

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()))
score = [0] * (n + 1)

max_score = -10 ** 9
for i in range(n):
    x = i
    temp_max = [-10 ** 9] * (n + 1)
    for j in range(1, n + 1):
        score[j] = score[j - 1] + c[p[x]]
        temp_max[j] = max(temp_max[j-1], score[j])
        x = p[x]
        if x == i:
            break
    if j >= k:
        max_score = max(max_score, temp_max[k])
    elif score[j] < 0:
        max_score = max(max_score, temp_max[j])
    else:
        m = k // j
        a = score[j] * (m - 1) + temp_max[j]
        b = score[j] * m + temp_max[k % j]
        max_score = max(max_score, a, b)
print(max_score)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def naive(K, P, C):
    P = P - 1
    N = len(P)
    INF = 1 << 60
    ret = -INF
    for v in range(N):
        for n in range(1, K + 1):
            s = 0
            w = v
            for _ in range(n):
                s += C[w]
                w = P[w]
            ret = max(ret, s)
    return ret

@njit((i8, i8[:], i8[:]), cache=True)
def main(K, P, C):
    N = len(P)
    INF = 1 << 60
    P = P - 1
    best_score = -INF
    for v in range(N):
        w = v
        L = 0
        S = 0
        while True:
            S += C[w]
            L += 1
            w = P[w]
            if v == w:
                break
        score = 0
        w = v
        for n in range(1, L + 1):
            
            score += C[w]
            w = P[w]
            if n > K:
                break
            max_add = (K - n) // L
            x = score + max(S * 0, S * max_add)
            best_score = max(best_score, x)
    return best_score

N, K = map(int, readline().split())
P = np.array(readline().split(), np.int64)
C = np.array(readline().split(), np.int64)

print(main(K, P, C))

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

d = [[0]*N for _ in [0]*N]
l = [0]*N
for i in range(N):
    j = i
    cnt = 0
    while True:
        prev_j = j
        j = P[j]-1
        d[i][j] = d[i][prev_j] + C[j]
        cnt += 1
        if j==i: break
    l[i] = cnt

ans = -(10**10)
for i in range(N):
    n = (K-N)//l[i]
    tmp = max(0,d[i][i]) * n
    k = K - n*l[i]
    j = i
    for _ in range(2*N):
        if k<=0: break
        k -= 1
        tmp += C[j]
        j = P[j] -1
        ans = max(ans,tmp)

print(ans)

Solution (Python):
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
if max(C) < 0:
    print(max(C))
else:
    maxAll = 0
    isCovered = [False] * n
    index = 0
    while index < n:
        if isCovered[index]:
            index += 1
            continue
        else:
            cycleCValue = []
            newIndex = index
            while newIndex != index or not cycleCValue:
                isCovered[newIndex] = True
                cycleCValue.append(C[P[newIndex] - 1])
                newIndex = P[newIndex] - 1
            maxValue = 0
            cycleCPartialSum = [0]
            for elem in cycleCValue:
                cycleCPartialSum.append(cycleCPartialSum[-1] + elem)
            for i in range(len(cycleCValue)): 
                if i > k:
                    continue
                for j in range(len(cycleCValue)): 
                    if i + j <= len(cycleCValue):
                        curSum = cycleCPartialSum[i + j] - cycleCPartialSum[j]
                    else:
                        curSum = cycleCPartialSum[(i + j) % len(cycleCValue)] + cycleCPartialSum[-1] - cycleCPartialSum[j]
                    if cycleCPartialSum[-1] > 0:
                        curSum += ((k - i) // len(cycleCValue)) * cycleCPartialSum[-1]
                    if curSum > maxValue:
                        maxValue = curSum
            if maxAll < maxValue:
                maxAll = maxValue
            index += 1
    print(maxAll)

Solution (Python):


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

answer = max(C)
for i in range(N):
  pos = P[i] - 1
  score = C[pos]
  score_list = [score]
  step = 1
  while pos!=i and step<K:
    pos = P[pos] - 1
    score += C[pos]
    score_list.append(score)
    step += 1
  score_max = max(score_list)
  if score_list[-1]>0 and step<K:
    loop = K//step
    amari = K%step
    for j in range(step):
      if j<amari:
        score_max = max(score_max, score_list[-1]*loop+score_list[j])
      else:
        score_max = max(score_max, score_list[-1]*(loop-1)+score_list[j])
  answer = max(answer,score_max)

print(answer)

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

ans = -float('inf')
v = []
for n in range(N):
    loop, score = 0, 0
    t = n
    for i in range(min(N, K)):
        n = P[n]-1
        score += C[n]
        ans = max(ans, score)
        if n == t:
            loop = i+1
            break
    v.append((loop, score))

for n in range(N):
    loop, score = v[n]
    if loop > 0 and score > 0:
        r = (K-1)//loop
        nscore = r*score
        for i in range(K-r*loop):
            n = P[n]-1
            nscore += C[n]
            ans = max(nscore, ans)
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = [int(a)-1 for a in input().split()]
C = [int(a) for a in input().split()]
ma = -10 ** 10
for i in range(N):
    l = 1
    j = P[i]
    s = C[j]
    ma = max(ma, s)
    while j != i:
        j = P[j]
        s += C[j]
        l += 1
        if K >= l:
            ma = max(ma, s)
    
    c = 1
    j = P[j]
    t = C[j]
    if K >= c:
        ma = max(ma, t + (K - c) // l * s)
    
    while j != i:
        j = P[j]
        t += C[j]
        c += 1
        if K >= c:
            ma = max(ma, t + (K - c) // l * s)

print(ma)

Solution (Python):
def nasu(s):
  x = s
  ma = MC
  su = 0
  L = []
  for i in range(K):
    x = P[x] - 1
    su += C[x]
    L.append(C[x])
    ma = max(ma, su)
    if x == s:
      break
  else:
    return ma
  if su <= 0:
    return ma
  n = i + 1
  div, mod = divmod(K, n)
  ans = (div - 1) * su + ma
  da = div * su
  for i in range(mod):
    da += L[i]
    ans = max(ans, da)
  return ans

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

ans = MC
for i in range(N):
  ans = max(ans, nasu(i))
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    p = LI()
    for i in range(n):
        p[i] -= 1
    c = LI()
    bfs = [0]*n
    lis = []
    for i in range(n):
        if not bfs[i]:
            bfs[i] = 1
            x = i
            path = [c[x]]
            while 1:
                x = p[x]
                if bfs[x]:
                    break
                path.append(c[x])
                bfs[x] = 1
            lis.append([0]+list(accumulate(path*2)))
    ans = -float("inf")
    for path in lis:
        n = len(path) >> 1
        m = k//n
        if k%n == 0:
            m -= 1
        s = m*path[n]
        if s < 0:
            s = 0
            res = n
        else:
            res = k-m*n
        for l in range(n):
            for j in range(1,res+1):
                ns = s+path[l+j]-path[l]
                if ans < ns:
                    ans = ns
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, k = na()
f = na()
c = na()

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

def mx(a, inf, sup):
    n = len(a)
    b = a + a
    ret = -1000000009 if inf > 0 else 0
    for i in range(n):
        s = 0
        for j in range(sup):
            s += b[i+j]
            if j >= inf-1:
                ret = max(ret, s)
    return ret

done = [False] * n
ans = -1000000007
for i in range(n):
    if not done[i]:
        a = []
        cur = i
        while not done[cur]:
            done[cur] = True
            a.append(c[cur])
            cur = f[cur]
        s = sum(a)
        need = k
        if need >= len(a):
            if s >= 0:
                can = need//len(a)*s + mx(a, 0, need % len(a))
                if need > 1:
                    can = max(can, (need//len(a)-1)*s + mx(a, 0, len(a)))
                else:
                    can = max(can, mx(a, 1, len(a)))
            else:
                can = mx(a, 1, len(a))
        else:
            can = mx(a, 1, need)
        ans = max(ans, can)

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

best = max(C)
for i in range(N):
    curr = 0
    score = [0]
    start = i
    while P[start] != i:
        start = P[start]
        curr += C[start]
        score.append(curr)
    cycle_score = score[-1] + C[i]
    cycle_len = len(score)

    for j in range(cycle_len):
        if j <= K and j != 0:
            cycles = (K - j)//cycle_len
            thing = score[j] + max(0, cycle_score) * cycles
            best = max(best, thing)
        elif j == 0 and K >= cycle_len:
            thing = cycle_score * K // cycle_len
            best = max(best,thing)

print(best)