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
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    N, K = mis()
    P = list(map(lambda x: x-1, mis()))
    C = lmis()
    ans = -INF
    for i in range(N):
        p = i
        tmp_score = 0
        k = K
        cycle = 0
        while k:
            p = P[p]
            tmp_score += C[p]
            ans = max(ans, tmp_score)
            k -= 1
            cycle += 1
            if p==i:
                if tmp_score < 0:
                    break
                elif k > cycle*2:
                    skip_loop = (k - cycle)//cycle
                    tmp_score *= skip_loop + 1
                    k -= skip_loop * cycle
        ans = max(ans, tmp_score)
    print(ans)








main()

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        q = deque([])
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            q.append(j)
            score += C[j]
            cnt += 1
            j = P[j]
        for j in q:
            f_cnt[j] = cnt
            f_score[j] = score
    
    

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def solve():
  ans = -float('inf')
  N, K = map(int, input().split())
  P = list(map(lambda x:int(x)-1, input().split()))
  C = list(map(int, input().split()))
  for i in range(N):
    score = 0
    now = i
    visited = [-1]*N
    scores = [0]*N
    visited[now] = 0
    for j in range(1,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
      if visited[now]>=0:
        cyc = j - visited[now]
        up = score - scores[now]
        break
      scores[now] = score
      visited[now] = j
    else:
      continue
    if up<=0:
      continue
    cnt = j+1
    if K-cyc>=j:
      score += (K-cyc-j)//cyc * up
      ans = max(ans, score)
      cnt += (K-cyc-j)//cyc*cyc
    for j in range(cnt,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
  return ans
print(solve())

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
p.insert(0, 0)
c.insert(0, 0)
visit = [0] * (n + 1)
cyclelist = []
for i in range(1, n + 1):
    if visit[i] == 0:
        a = [c[i]]
        visit[i] = 1
        while visit[p[i]] == 0:
            i = p[i]
            visit[i] = 1
            a.append(c[i])
        cyclelist.append(a)
ans = -1145141919810
for cycle in cyclelist:
    s = sum(cycle)
    l = len(cycle)
    a = 0
    if l < k and s > 0:
        a = s * ((k - 1) // l)
    now = 0
    x = k % l
    if x == 0:
        x = l
    for i in range(min(k, l)):
        now += cycle[i]
        for j in range(l):
            now += cycle[(i + j + 1) % l] - cycle[j]
            if i < x:
                ans = max(ans, a + now)
            else:
                ans = max(ans, now)
print(ans)

Solution (Python):
from sys import maxsize
from itertools import product

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

used = [0] * n
ss = []
for i in range(n):
    if used[i]:
        continue
    now = i
    s = []
    while not used[now]:
        used[now] = 1
        s.append(c[now])
        now = p[now]
    ss.append(s)

res = -maxsize
for s in ss:
    s_len = len(s)
    cumsum = [0]
    
    for i in range(2*s_len):
        cumsum.append(cumsum[-1] + s[i%s_len])

    max_sum = [-maxsize] * s_len
    for i, j in product(range(s_len), repeat=2):
        max_sum[j] = max(max_sum[j], cumsum[i+j] - cumsum[i])

    for i in range(s_len):
        if i > k:
            continue
        v = (k - i) // s_len
        if i == 0 and v == 0:
            continue
        if cumsum[s_len] > 0:
            res = max(res, max_sum[i] + cumsum[s_len] * v)
        elif i > 0:
            res = max(res, max_sum[i])
print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j]
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    
    

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()

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

lim = 60
nex = [[0] * N for _ in range(lim)]
val = [[0] * N for _ in range(lim)]
cnd = [[0] * N for _ in range(lim)]

for i in range(N):
    nex[0][i] = P[i] - 1
    val[0][i] = C[i]
    cnd[0][i] = C[i]

for d in range(lim - 1):
    for i in range(N):
        nex[d + 1][i] = nex[d][nex[d][i]]
        val[d + 1][i] = val[d][i] + val[d][nex[d][i]]
        cnd[d + 1][i] = max(cnd[d][i], val[d][i] + cnd[d][nex[d][i]])

res = -10 ** 9
for i in range(N):
    sum_ = 0
    offset = i
    for d in reversed(range(lim)):
        if K & 1 << d:
            res = max(res, sum_ + cnd[d][offset])
            sum_ += val[d][offset]
            offset = nex[d][offset]

print(res)

Solution (Python):
from itertools import accumulate

def max_from_acc(A, b):
    r = -10**9-1
    acc = [0] + list(accumulate(A + A[:b]))
    for i in range(len(A)):
        for j in range(1, b+1):
            r = max(r, acc[i+j]-acc[i])
    return r

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]

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



ans = -10**9-1
for loop in loops:
    t =len(loop)
    div, mod = divmod(k, t)
    if mod == 0:
        mod = t
        div -= 1
    C_loop = [C[p] for p in loop]
    loop_score = sum(C_loop)

    if t >=k:
        ans = max(ans, max_from_acc(C_loop, k))
    else:
        if loop_score > 0:
            ans = max(ans, max_from_acc(C_loop, mod)+loop_score*div)
        else:
            ans = max(ans, max_from_acc(C_loop, t))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,K=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
if K == 1:
    print(max(c));exit()
ans = -10**10
def cycle(k):
    mo=k
    clen=0
    cscore=0
    flg = True
    cmax=[-10**10]
    while (mo != k or flg):
        clen+=1
        cscore+=c[mo]
        mo = p[mo]
        cmax.append(max(cmax[-1],cscore))
        if mo == k:
            flg = False
    if cscore<0:
        return cmax[min(K-1,clen-1)]
    return cscore*((K-1)//clen)+cmax[(K-1)%clen+1]
for i in range(n):
    a=cycle(i)
    if a>ans:
        ans = a
print(ans)

Solution (Python):
from collections import deque
it = lambda: list(map(int, input().strip().split()))


def maximise(L, R, cycle):
    cur = 0
    ans = max(cycle)
    queue = deque([0])
    dp = [0] * (2 * L + 1)
    for i, num in enumerate(cycle + cycle):
        j = i + 1
        cur += num
        while queue and j - queue[0] > R:
            queue.popleft()
        if queue:
            ans = max(ans, cur - dp[queue[0]])
        while queue and dp[queue[-1]] >= cur:
            queue.pop()
        queue.append(j)
        dp[j] = cur
    return ans


def get(K, cycle):
    L = len(cycle)
    T = sum(cycle)

    if K > L:
        B = (K - 1) // L
        R = K - B * L
    else:
        B = 0
        R = K
    return max(maximise(L, K, cycle), maximise(L, R, cycle) + max(0, B * T))


def solve():
    
    N, K = it()
    P = it()
    C = it()

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

    cycles = []
    seen = [False] * N
    for i in range(N):
        if not seen[i]:
            cycle = []
            first = curr = i
            while True:
                seen[curr] = True
                cycle.append(C[curr])
                curr = P[curr]
                if curr == first:
                    break
            cycles.append(cycle)
    
    
    ans = float('-inf')
    for cycle in cycles:
        ans = max(ans, get(K, cycle))
    return ans


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

Solution (Python):
INF=10**20

N,K=map(int,input().split())

array=list(map(int,input().split()))
P=[]
C=list(map(int,input().split()))
for i in array:
    P.append(i-1)

ans=-1*INF

for i in range(N):
    v=i
    cycle_sum=0
    cycle_cnt=0

    while(True):
        cycle_cnt+=1
        cycle_sum+=C[v]
        v=P[v]
        if v==i:
            break

    path=0
    cnt=0

    while(True):
        cnt+=1
        path+=C[v]

        if cnt>K:
            break

        num=(K-cnt)//cycle_cnt
        score=path+max(0,cycle_sum)*num
        ans=max(ans,score)

        v=P[v]
        if v==i:
            break

print(ans)

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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**20

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)+1):
            for j in range(len(li)):
                if k >= cnt:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

print(ans)

Solution (Python):

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

score_output = -1000000000
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = 0
    loop  = 0
    score_max = -1000000000
    while True:
        step  += 1
        score += C[ichi]
        ichi   = (P[ichi] -1)
        if i ==  (P[ichi] -1):
            score += C[ichi]
            break
        
    path = 0
    cnt  = 0
    
    while True:
        cnt  += 1
        path += C[ichi]
        
        if cnt > K:
            break
        
        loop = int((K - cnt) / (step+ 1))
        if score > 0:
            score_max = path + loop * score
        else:
            score_max = path
        if score_max > score_output:
            score_output = score_max

        ichi   = P[ichi]-1
        if i == (P[ichi] -1):
            break

print(score_output)