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(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
P=tuple(map(int1,input().split()))
C=tuple(map(int,input().split()))
loop=[[-INF,0] for _ in range(N)]
used=[False]*N
for v in range(N):
    stack=[]
    d=0
    cnt=0
    while True:
        if not used[P[v]]:
            v=P[v]
            stack.append(v)
            used[v]=True
            d+=C[v]
            cnt+=1
        else:
            for vv in stack:
                loop[vv][0]=d
                loop[vv][1]=cnt
            break
ans=-INF
for i in range(N):
    d=0
    v=i
    for cnt in range(K):
        v=P[v]
        if loop[v][0]==-INF:
            d+=C[v]
            ans=max(ans,d)
        else:
            break
    loopstart=v
    MAX=-INF
    dd=0
    f=False
    for ccnt in range(1,K-cnt+1):
        loopn=(K-ccnt)//loop[loopstart][1]
        if v!=loopstart or not f:
            dd+=C[v]
            ans=max(ans,d+dd,d+dd+loopn*loop[loopstart][0])
            v=P[v]
        else:
            break
        f=True
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:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    elif k % loop == 0:
        res = max(res, score[-1] * (k // loop), score[-1] * (k // loop - 1) + max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    uf = UnionFind(n)
    for i in range(n):
        uf.union(i, p[i]-1)
    G = [[] for _ in range(uf.group_count())]
    idx = 0
    st = set()
    for i in range(n):
        if not i in st:
            x = i
            while not x in st:
                G[idx].append(c[x])
                st.add(x)
                x = p[x] - 1
            idx += 1
    ans = max(c) 
    for i in range(len(G)):
        sum_g = sum(G[i])
        tmp_k = k
        if sum_g > 0:
            tmp = sum_g * (tmp_k // len(G[i]))
            tmp_k %= len(G[i])
            csum = [0]
            for v in G[i]:
                csum.append(v)
            for v in G[i]:
                csum.append(v)
            for j in range(len(csum)-1):
                csum[j+1] += csum[j]
            tmp_tmp = 0
            for j in range(len(G[i])+1):
                for l in range(1, tmp_k+1):
                    if tmp_tmp < csum[j+l] - csum[j]:
                        tmp_tmp = csum[j+l] - csum[j]
            if 0 < tmp_tmp:
                tmp += tmp_tmp
            if ans < tmp:
                ans = tmp
            if k > len(G[i]):
                tmp_k = k
                tmp = sum_g * ((tmp_k // len(G[i]))-1)
                tmp_k = len(G[i])
                csum = [0]
                for v in G[i]:
                    csum.append(v)
                for v in G[i]:
                    csum.append(v)
                for j in range(len(csum)-1):
                    csum[j+1] += csum[j]
                tmp_tmp = 0
                for j in range(len(G[i])+1):
                    for l in range(1, tmp_k+1):
                        if tmp_tmp < csum[j+l] - csum[j]:
                            tmp_tmp = csum[j+l] - csum[j]
                if 0 < tmp_tmp:
                    tmp += tmp_tmp
                if ans < tmp:
                    ans = tmp
        else:
            if tmp_k > len(G[i]):
                tmp_k = len(G[i])
            csum = [0]
            for v in G[i]:
                csum.append(v)
            for v in G[i]:
                csum.append(v)
            for j in range(len(csum)-1):
                csum[j+1] += csum[j]
            for j in range(len(G[i])):
                for l in range(1, tmp_k+1):
                    if ans < csum[j+l] - csum[j]:
                        ans = csum[j+l] - csum[j]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

data = []
loopdata = []
oneloop = []
for i in range(N):
  temp = [-INF]
  step = 1
  flag = [0 for i in range(N)]
  now = P[i]-1
  score = C[now]
  best = score
  temp.append(best)
  flag[now] = step
  while True:
    step += 1
    now = P[now]-1
    if flag[now]:
      loopdata.append([flag[now],step])
      score += C[now]
      best = max(best,score)
      temp.append(best)
      oneloop.append(score-temp[flag[now]])
      break
    score += C[now]
    best = max(best,score)
    temp.append(best)
    flag[now] = step
  data.append(temp)

best = -INF
for i in range(N):
  if K < loopdata[i][1]:
    best = max(best,max(data[i][:K+1]))
  else:
    if oneloop[i]<0:
      best = max(best,max(data[i]))
    else:
      mod = loopdata[i][1]-loopdata[i][0]
      k = K - (loopdata[i][0]-1)
      p = (k-1)//mod
      q = k-p*mod
      score = -INF
      for j in range(len(data[i])-1):
        if j < loopdata[i][0]:
          score = max(score,data[i][j])
        else:
          if j <= (loopdata[i][0]-1)+q:
            score = max(score,data[i][j]+oneloop[i]*p)
          else:
            score = max(score,data[i][j]+oneloop[i]*(p-1))
      best = max(best,score)
print(best)

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

ans = -10**10
for i in range(N):
    T = []
    Check = [0]*N
    move = i
    count = 1
    while(True):
        if Check[move] != 0:
            break
        Check[move] = count
        T.append(C[P[move]])
        move = P[move]
        count += 1
    s = Check[move] - 1
    result_1 = -10**10
    total = 0
    for j in range(min(s, K)):
        total += T[j]
        result_1 = max(result_1, total)
    result_2 = -10**10
    total = 0
    for j in range(min(len(T), K)):
        total += T[j]
        result_2 = max(result_2, total)
    if K >= len(T):
        result_3 = 0
        result_3 += sum(T[:s])
        result_3 += sum(T[s:])*((K - len(T[:s])) // len(T[s:]))
        result_4 = result_3
        total = result_3
        for j in range((K - len(T[:s])) % len(T[s:])):
            total += T[j]
            result_3 = max(result_3, total)
        total = result_4
        for j in T[s:][::-1]:
            total -= j
            result_4 = max(result_4, total)
    if K >= len(T):
        if result_4 != 0:
            ans = max([result_1, result_2, result_3, result_4, ans])
        else:
            ans = max([result_1, result_2, result_3, ans])
    else:
        ans = max([result_1, result_2, ans])
print(ans)

Solution (Python):
N,K=map(int,input().split())
P,C=[list(map(int,input().split())) for i in range(2)]
r=-10**18
for j in range(N):
    d=[0]*(N+1)
    p=j
    for i in range(N):
        p=P[p]-1
        d[i+1]=d[i]+C[p]
        if p==j:
            break
    q=max(d[1:K+1]) if K<i+1 else max(d[1:i+1]) if d[i+1]<0 else max(max(d)+d[(i+1)]*(K//(i+1)-1),max(d[:K%(i+1)+1])+d[i+1]*(K//(i+1)))
    r=max(r,q)
print(r)

Solution (Python):
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        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,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(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()))

U=Union_Find(N+1)

for i in range(1,N+1):
    U.union(i,P[i])

Cycle_Point={}
for a in U.roots():
    if a==0:
        continue

    b=P[a]
    S=C[a]
    while a!=b:
        S+=C[b]
        b=P[b]
    Cycle_Point[a]=S

Ans=-float("inf")

for x in range(1,N+1):
    group=U.find(x)
    Round_Point=Cycle_Point[group]
    cycle_size=U.size(x)

    rap,remain=divmod(K,cycle_size)

    if rap==0:
        Temp_Score=0
        Score=C[P[x]]

        p=x
        for _ in range(min(cycle_size,K)):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)
    elif Round_Point>0:
        p=x
        L=[0]*(cycle_size+1)

        Temp_Score=0
        for k in range(cycle_size):
            p=P[p]
            Temp_Score+=C[p]
            L[k+1]=Temp_Score

        alpha=Round_Point*rap+max(L[:remain+1])
        beta=Round_Point*(rap-1)+max(L)
        Score=max(alpha,beta)

    else:
        Temp_Score=0
        Score=C[P[x]]

        p=x
        for _ in range(min(cycle_size,K)):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)


    Ans=max(Ans,Score)
    assert 1

print(Ans)

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

flag = [False for i in range(n + 1)]
r = []
num = 1
while num < n + 1:
    if flag[num] == False:
        temp = [c[num]]
        flag[num] = True
        num2 = p[num]
        while flag[num2] == False:
            flag[num2] = True
            temp.append(c[num2])
            num2 = p[num2]
        else:
            r.append(temp)
            num += 1
    else:
        num += 1
ans = -float("inf")
for i in r:
    temp = sum(i)
    sum_i = [0]
    for j in range(len(i)):
        sum_i.append(sum_i[-1] + i[j])
    for j in range(len(i)):
        sum_i.append(sum_i[j + 1] + temp)
    num1 = k % len(i)
    num2 = k // len(i)
    if temp < 0:
        for j in range(1, min(len(i), k) + 1):
            for l in range(len(i)):
                ans = max(ans, sum_i[l + j] - sum_i[l])
    else:
        if num2 >= 1:
            for j in range(1, len(i) + 1):
                for l in range(len(i)):
                    ans = max(ans, sum_i[l + j] - sum_i[l] + temp * (num2 - 1))
        for j in range(1, num1 + 1):
            for l in range(len(i)):
                ans = max(ans, sum_i[l + j] - sum_i[l] + temp * num2)
print(ans)

Solution (Python):
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	
	if len(ruisekiwa) >= k:
		tr = max(ruisekiwa[:k])
		
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			
			
			
			if k%(len(ruisekiwa)-1) >= 1:
				tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			else:
				tr = max(ruisekiwa[:-1])+ms-(ruisekiwa[-1]-ruisekiwa[0])
			
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
p = [i-1 for i in p]
MINI = -10**9-1

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


union_find = UnionFind(n)
score_map = {}
for i in range(n):
    union_find.union(i, p[i])

for root in union_find.roots():
    n_c = p[root]
    score = c[n_c]
    while n_c != root:
        n_c = p[n_c]
        score += c[n_c]
    score_map[root] = score

ans = MINI
for i in range(n):
    mx = MINI
    score = 0
    m = k
    root = union_find.find(i)
    lap_score = score_map[root]
    if lap_score > 0:
        _d = (k // union_find.size(root)) - 1
        score += lap_score*_d
        mx = max(mx, score)
        m -= _d*union_find.size(root)
    else:
        m = min(k, union_find.size(root))
    if m == 0:
        ans = max(mx, ans)
        continue
    n_c = p[i]
    score += c[n_c]
    mx = max(mx, score)
    m -= 1
    while m > 0:
        n_c = p[n_c]
        score += c[n_c]
        mx = max(mx, score)
        m -= 1
    ans = max(mx, ans)
print(ans)

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

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

USE=[0]*N
ANS=-1<<100
for i in range(N):
    if USE[i]==1:
        continue
    else:
        USE[i]=1
        A=[C[P[i]]]
        NOW=P[i]

        while NOW!=i:
            USE[NOW]=1
            A.append(C[P[NOW]])
            NOW=P[NOW]
            
        

        S=sum(A)
        SCORE=0
        if S>0:
            SCORE=S*(K//len(A))
            rest=K%len(A)

            A2=A+A+A
            S2=[0]
            for a in A2:
                S2.append(S2[-1]+a)

            restscore=-1<<100

            for i in range(len(A)):
                for j in range(i+1,i+rest+1):
                    
                    restscore=max(restscore,S2[j]-S2[i])

            

            ANS=max(ANS,SCORE+restscore)

            if K//len(A)>=1:
                SCORE=S*(K//len(A) - 1)
                rest=len(A)

                restscore=-1<<100

                for i in range(len(A)):
                    for j in range(i+1,i+rest+1):
                        
                        restscore=max(restscore,S2[j]-S2[i])

                

                ANS=max(ANS,SCORE+restscore)
                
        else:
            SCORE=0
            rest=min(K,len(A))

            A2=A+A+A
            S2=[0]
            for a in A2:
                S2.append(S2[-1]+a)

            restscore=-1<<100

            for i in range(len(A)):
                for j in range(i+1,i+rest+1):
                    
                    restscore=max(restscore,S2[j]-S2[i])

            

            ANS=max(ANS,SCORE+restscore)
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()))
done = [False] * N
ans = -10**30
must_negative = all([c < 0 for c in C])
for i in range(N):
  if done[i]:
    continue
  loop = [i]
  done[loop[-1]] = True
  while not done[P[loop[-1]]]:
    loop.append(P[loop[-1]])
    done[loop[-1]] = True
    
  
  scores = [C[i] for i in loop]
  
  cumsum = [0]
  for s in scores * 3:
    cumsum.append(cumsum[-1] + s)
  
  L = len(scores)
  if cumsum[L] >= 0:
    
    l = max(0, (K - L) // L )
    k_max = K - l * L
    
    base_score = cumsum[L] * l
  else:
    k_max = min(K, 2 * L)
    
    base_score = 0
  for i in range(L):
    for k in range(k_max+1):
      score = base_score + cumsum[i + k] - cumsum[i]
      
      if must_negative and score == 0:
        continue
      ans = max(ans, score)
print(ans)

Solution (Python):
n,k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
    
flags = [0]*n
roots = []
for i in range(n):
  if flags[i] == 1:
    continue
  root = [i+1]
  while True:
    root.append(p[root[-1]-1])
    flags[root[-1]-1] = 1 
    if root[-1] == i+1:
      root.pop(-1)
      break
  roots.append(root)

ans = max(c)
for root in roots:
  root.extend(root)
  ruisekiwa = [0]*len(root)
  ruisekiwa[0] = c[root[0]-1]
  for i in range(1, len(root)):
    ruisekiwa[i] = ruisekiwa[i-1] + c[root[i]-1]
  scoreCir = ruisekiwa[len(root)//2-1]
  
  scoreForRoot = -10**15
  for i in range(1, min(k+1, len(root)//2+1)): 
    scoreForKaisuu = -10**15
    for j in range(0, len(root)//2):
      score = ruisekiwa[j+i] - ruisekiwa[j]
      scoreForKaisuu = max(score, scoreForKaisuu)
    
    if scoreCir > 0 and k-i >= len(root)//2:
      
      scoreForKaisuu += (k-i)//(len(root)//2)*scoreCir
    scoreForRoot = max(scoreForKaisuu, scoreForRoot)
  ans = max(ans, scoreForRoot)
print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
P = {i:n-1 for i, n in enumerate(list(map(int, input().split())))}
C = {i:n for i, n in enumerate(list(map(int, input().split())))}

cand = []
for i in range(N):
    current = i
    max_val = [C[P[current]]]
    sum_val = C[P[current]]
    while P[current]!=i:
        current = P[current]
        sum_val += C[P[current]]
        if sum_val>max_val[-1]:
            max_val.append(sum_val)
        else:
            max_val.append(max_val[-1])
    if K<=len(max_val):
        cand.append(max_val[K-1])
    else:
        if sum_val<=0:
            cand.append(max_val[-1])
        else:
            tmp_score = sum_val*(K//len(max_val))
            if K%len(max_val)>0:
                tmp_score += max_val[K%len(max_val)-1]
            cand.append(max(sum_val*(K//len(max_val)-1)+max_val[-1], tmp_score))
print(max(cand))

Solution (Python):
int1 = lambda x: int(x) - 1

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

visited = set()
cycles = []
for i in range(N):
    if i not in visited:
        cur = P[i]
        cycle = [i]
        while cur != i:
            visited.add(cur)
            cycle.append(cur)
            cur = P[cur]
        cycles.append(cycle)

ans = -float('inf')
for cycle in cycles:
    l = len(cycle)
    score = [0]
    for x in cycle * 2:
        score.append(score[-1] + C[x])

    
    lst = [0] * (min(K, l) + 1)
    lst[0] = -float('inf')
    for i in range(1, min(K, l) + 1):
        tmp = -float('inf')
        for j in range(l):
            tmp = max(tmp, score[j + i] - score[j])
        lst[i] = tmp

    lap = K // l
    if lap == 0:
        ans = max(ans,
                  max(lst))
    else:
        around_score = lst[l]
        ans = max(ans,
                  max(lst),
                  around_score * (lap - 1) + max(lst),
                  around_score * lap + max(lst[:K % l + 1]))
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
INF = 10**18

n, k = map(int, input().split())
p = [int(item) - 1 for item in input().split()]
c = [int(item) for item in input().split()]
visited = [0] * n
cycles = []

for i in range(n):
    if visited[i]:
        continue
    nc = []
    v = i
    visited[v] = True
    nc.append(c[v])
    while not visited[p[v]]:
        v = p[v]
        visited[v] = True
        nc.append(c[v])
    cycles.append(nc)

ans = -INF 
for cycle in cycles:
    length = len(cycle)
    c_num = max(0, (k - 1) // length - 1)
    total = max(0, sum(cycle) * c_num)
    rest = k - (c_num * length)
    l_cycle = cycle + cycle + cycle
    for l in range(length):
        total_rest = 0
        for diff in range(rest):
            total_rest += l_cycle[l + diff]
            ans = max(ans, total + total_rest)

print(ans)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().rstrip()


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


    maxscore = -10 ** 9 - 10
    for i in range(N):
        vis_val = [-10 ** 10] * N
        vis_time = [0] * N
        score = 0
        current = i
        k = 1
        flag=0
        while k <= K:
            current = P[current] - 1
            score += C[current]
            if vis_time[current]:
                if score - vis_val[current] <= 0:
                    roopmax = max(vis_val)
                    flag=1
                    break
                else:

                    one_cicle = k - vis_time[current]
                    one_val = score - vis_val[current]
                    rem = (K - k) // one_cicle
                    score += rem * one_val
                    k += one_cicle *rem
                    roopmax = score
                    k+=1
                    while k <= K:
                        current = P[current] - 1
                        score += C[current]
                        roopmax = max(roopmax, score)
                        k+=1
                        flag=1

            vis_val[current] = score
            vis_time[current] = k
            k += 1
        if flag==0:
            roopmax=max(vis_val)

        maxscore = max(roopmax, maxscore)

    print(maxscore)

if __name__ == "__main__":
    main()

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
INF=-(10**20)
X=[[INF]*(N+1) for i in range(N)]
Y=[0]*N
Z=[0]*N
R=[0]*N
S=set()
V=0
for i in range(N):
  S=set()
  V=i
  S.add(i)
  for j in range(N):
    V=P[V]
    if V in S:
      Z[i]=V
      break
  X[i][0]=0
  for j in range(N):
    Y[i]+=1
    V=P[V]
    X[i][j+1]=X[i][j]+C[V]
    if Z[i]==V:
      R[i]=X[i][j+1]
      break
A=INF
Q=0
T=0
U=0
D=0
E=0
for i in range(N):
  D=K
  V=i
  E=0
  for j in range(min(N,K)):
    if Z[i]==V:
      break
    V=P[V]
    E+=C[V]
    D-=1
  i=V
  D,K=K,D
  if R[i]<=0:
    for j in range(1,min(Y[i],K)+1):
      A=max(A,X[i][j]+E)
  else:
    S=max((K//Y[i])-1,0)
    Q=R[i]*S
    T=0
    U=INF
    V=i
    for j in range(K-S*Y[i]):
      V=P[V]
      T+=C[V]
      U=max(T,U)
    Q+=U
    A=max(A,Q+E)
  D,K=K,D
print(A)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

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

flag = [0]*N
ans = max(C)
for i in range(N-1):
    if flag[i] != 0:
        continue
    A = [C[i]]
    flag[i] = 1
    a = i
    j = P[i]-1
    while j != i:
        A.append(C[j])
        flag[j] = 1
        j = P[j]-1
    a = len(A)
    s = 0
    if sum(A) > 0:
        if K//a > 0:
            s = sum(A)*(K//a-1)
            r = K % a + a
        else:
            s = 0
            r = K % a
    else:
        s = 0
        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)
    s += m
    ans = max(ans,s)

print(ans)