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):
from collections import defaultdict

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):
    ret = defaultdict(list)
    for i in range(self.n):
      ret[self.find(i)].append(i)
    return ret

  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(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

uf = UnionFind(N)

for i in range(N):
  uf.union(i, P[i])

D = uf.all_group_members()
E = defaultdict(list)
F = defaultdict(int)

Num = [0]*N

for root in uf.roots():
  i = root
  n = 0
  E[root].append(0)
  while P[i] != root:
    i = P[i]
    n += 1
    Num[i] = n
    E[root].append(E[root][-1] + C[i])
  E[root].append(E[root][-1] + C[root])
  F[root] = n + 1
  i = root
  while P[i] != root:
    i = P[i]
    E[root].append(E[root][-1] + C[i])
  E[root].append(E[root][-1] + C[root])


ans = -float("inf")

for root, L in E.items():
  loop, k = divmod(K, F[root])
  if k == 0:
    loop -= 1
    k += F[root]
  temp = 0
  if L[-1] >= 0:
    temp += (L[-1]//2) * loop
  else:
    if loop >= 1:
      k = F[root]
  for i in range(F[root]):
    for j in range(i+1, i+k+1):
      ans = max(ans, temp + E[root][j] - E[root][i])

print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)








INF = 1 << 100


def run():
    N, K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    C = list(map(int, sysread().split()))
    P = [p-1 for p in P]

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    
    
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] <= 0 or len(loop)-1 > K:
                j = i
                max_val = -INF
                iter = 0
                while iter < K:
                    iter += 1
                    j += 1
                    if j == len(loop):
                        j = 1
                    val += loop[j]
                    max_val = max(max_val, val)
                    if i == j:
                        break
                
                ans = max(ans, max_val)
                continue


            rest = K
            
            
            
            
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            if rest // (len(loop)-1):
                val1 = val + (rest // (len(loop)-1)) * loopSum[-1]
                rest1 = rest % (len(loop) - 1)
                if rest1:
                    val1 += max(loopSum[1:rest1+1])
                val2 = val + (rest // (len(loop)-1) - 1) * loopSum[-1]
                val2 += max(loopSum[1:])
                val = max(val1, val2)
            else:
                if rest:
                    val += max(loopSum[1:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Solution (Python):
n,k = map(int,input().split())
pn = list(map(int,input().split()))
cn = list(map(int,input().split()))
ans = -float("inf")


for i in range(n): 
    start=i
    now=start
    total = 0 
    ls = [0]

    for j in range(1, k+1):
        now = pn[now]-1
        total += cn[now]
        ans = max(ans, total)
        ls.append(total)
        if now == start:
            rp = j
            break
    else:
        continue  

    if total <= 0:
        continue
    else:
        if k % rp == 0:
            ans2 = total * (k // rp-1) + max(ls)
            ans = max(ans, ans2)
        else:
            ans2 = total * (k//rp) + max(ls[:k%rp+1])
            ans = max(ans, ans2)
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()))

ans = -float("inf")

for st in range(N):
  S = []
  temp = P[st]
  S.append(C[temp])
  while temp != st:
    temp = P[temp]
    S.append(S[-1] + C[temp])
  cnt = len(S)
  loop, k = divmod(K, cnt)
  point = 0
  if S[-1] >= 0:
    if k == 0:
      loop -= 1
      k += cnt
    point += S[-1] * loop
  else:
    if loop >= 1:
      k = cnt
  ans = max(ans, point + max(S[:k]))

print(ans)

Solution (Python):
from collections import deque
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))
    exit()

loop_list = []
visited = [False]*n
d = deque()
for start in range(n):
    if visited[start]:
        continue
    loop = [start]
    d.append(start)
    visited[start] = True
    while True:
        now = d.pop()
        next = p[now]
        d.append(next-1)
        if visited[next-1]:
            loop_list.append(loop)
            break
        else:
            visited[next-1] = True
            loop.append(next-1)


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

Solution (Python):
from itertools import accumulate

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]

seen = [False]*n
ans = -float('inf')
for i in range(n):
    if not seen[i]:
        sc = []
        stop = i
        while True:
            seen[i] = True
            sc.append(c[i])
            if p[i] == stop:
                break
            i = p[i]

        lens = len(sc)
        for j in range(lens):
            if j != 0:
                sc = sc[1:] + [sc[0]]
            ac = list(accumulate(sc))

            if sum(sc) <= 0:
                ans = max(ans, max(ac[:min(k, lens)]))
            else:
                if k%lens == 0:
                    ans = max(ans, ac[-1]*(k//lens-1) + max(ac))
                else:
                    ans = max(ans, ac[-1]*(k//lens) + max(ac[:k%lens]+[0]))
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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()]

    ans = max(C)
    for i in range(N):
        next = P[i]
        cnt = 0
        cycle_value = 0

        while True:
            cycle_value += C[next]
            cnt += 1
            if next == i:
                break
            next = P[next]

        j = 0
        tmp = 0
        next = P[i]
        while True:
            tmp += C[next]
            j += 1
            ans = max(ans, tmp + ((K - j) // cnt) * max(0, cycle_value))
            if j == K or next == i:
                break
            next = P[next]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

def get_cycle_scores(cycle):
    score = 0
    scores = [score]
    for i in cycle:
        score += C[i]
        scores.append(score)
    return scores

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    scores = get_cycle_scores(cycle)
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    
    if K <= len(cycle):
        max_score = max(scores[move] for move in range(1, K+1))
        max_scores.append(max_score)
        continue
    
    if score_per_cycle <= 0:
        max_score = max(scores[move] for move in range(1, cycle_len+1))
        max_scores.append(max_score)
        continue
    
    
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        
        loop_cnt = move // cycle_len
        
        rest_move = move % cycle_len
        
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))

Solution (Python):
import sys

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

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

Ps = [0]+list(map(int, input().split()))
Cs = [0]+list(map(int, input().split()))

uf = UnionFind(N+1)
dic = {}

rlt = -sys.maxsize
for i in range(1,N+1):
  uf.union(i,Ps[i])
  
for i in range(1,N+1):
  j = uf.find(i) 
  if j in dic:
    dic[j] += Cs[Ps[i]]
  else:
    dic[j] = Cs[Ps[i]]
    
rlt = -sys.maxsize

for i in range(1,N+1):
  k = uf.find(i)
  cnt = K//uf.size(k)
  if cnt == 0:
    tmp2 = -sys.maxsize
    tmp3 = 0
    j = i
    for _ in range(1, K+1):
      j = Ps[j]
      tmp3 += Cs[j]
      tmp2 = max(tmp2, tmp3) 
    tmp = tmp2
  
  elif dic[k] <= 0:
    tmp2 = -sys.maxsize
    tmp3 = 0
    j = i
    for _ in range(1, uf.size(k)+1):
      j = Ps[j]
      tmp3 += Cs[j]
      tmp2 = max(tmp2, tmp3)
    tmp = tmp2
    
  else:
    md = K % uf.size(k)
    tmp = 0
    tmp2 = -sys.maxsize
    tmp3 = 0
    j = i
    for l in range(1, md+uf.size(k)+1):
      j = Ps[j]
      if l <= md:
        tmp += Cs[j]
      else:
        tmp3 += Cs[j]
        tmp2 = max(tmp2, tmp3)

    tmp += tmp2 + dic[k]*(cnt-1)
  rlt = max(rlt, tmp)

print(rlt)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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()]

    ans = max(C)
    for i in range(N):
        next = P[i]
        cnt = 0
        tmp = 0

        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == K or next == i:
                break
            next = P[next]

        if cnt == K or tmp <= 0:
            continue

        q = K // cnt
        r = K % cnt
        next = P[i]
        if q != 0:
            tmp *= (q - 1)
            q -= 1
            r += cnt
            ans = max(ans, tmp)
        else:
            tmp = 0
        while r > 0:
            tmp += C[next]
            ans = max(ans, tmp)
            next = P[next]
            r -= 1
    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()))

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
ans=-(10**9)*2
for i in range(N):
  
  if K<=I[i]:
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(K-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  
  elif CN[i]<=0:
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(I[i]-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    syuukai=K//I[i]
    nokori=K%I[i]
    syuukai-=1
    nokori+=I[i]
    d=C[i]
    cnt=d
    nex=P[i]-1
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    cnt+=syuukai*CN[i]
  ans=max(ans,cnt)
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
from collections import deque, defaultdict
def main():
    n, ko = map(int, input().split())
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    scores_all = deque()
    for k1 in range(n):
        scores = deque()
        kita = defaultdict(int)
        kita[k1] = ko
        cnt = ko - 1
        koko = p[k1] - 1
        scores.append(c[koko])
        kita[koko] = cnt
        while cnt:
            cnt -= 1
            koko = p[koko] - 1
            scores.append(c[koko])
            if kita[koko]:
                break
            else:
                kita[koko] = cnt
        cycle_long = kita[koko] - cnt
        scores_a = tuple(accumulate(scores))

        if cnt:
            if scores_a[-1] > 0:
                kaisuu = ko // cycle_long
                s1 = scores_a[-1] * kaisuu
                amari = ko % cycle_long
                if amari:
                    t = max(0, max(scores_a[:amari]))
                    s1 += t
                s2 = scores_a[-1] * (kaisuu - 1)
                s2 += max(scores_a)
                scores_all.append(max(s1, s2))
            else:
                scores_all.append(max(scores_a))
        else:
            scores_all.append(max(scores_a))
    print(max(scores_all))

if __name__ == '__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
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 S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N, K = MI()
P = LI()
C = LI()
loops = []
C_loop = []
for i in range(N):
    j = i
    loops.append([i])
    C_loop.append([0])

    while (P[i] - 1) != j:
        i = P[i] - 1
        C_loop[-1].append(C_loop[-1][-1] + C[i])
        loops[-1].append(i)

    C_loop[-1].append(C_loop[-1][-1] + C[P[i] - 1])


ans_list = [0] * N

for i in range(N):
    if K <= len(loops[i]):
        ans_list[i] = max(C_loop[i][j] for j in range(1, K + 1))
    else:
        if C_loop[i][-1] <= 0:
            ans_list[i] = max(C_loop[i])
        else:
            a = K // len(loops[i])
            ans_list[i] = max(a * C_loop[i][-1] + max(C_loop[i][j] for j in range(K % len(loops[i]) + 1)), (a - 1) * C_loop[i][-1] + max(C_loop[i]))

print(max(ans_list))

Solution (Python):
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))







ans = -float("inf")
for i in range(N):
    q = deque([(i, 0, 0)])
    cycle_score = -1
    cycle_count = -1
    cycle_start = None
    scores = {} 
    while q:
        node1, score, count = q.popleft()
        
        if K < count:
            break
        if 0 < count: 
            ans = max(ans, score)
        if node1 in scores:
            
            if score > 0:
                
                
                cycle_score = score
                cycle_count = count
                cycle_start = node1
            break
        scores[node1] = (score, count)
        
        
        
        node2 = P[node1] - 1
        weight = C[node2]
        q.append((node2, score + weight, count + 1))

    
    if cycle_start is not None:
        cycle_len = cycle_count - scores[cycle_start][1]
        
        loop = (K - scores[cycle_start][1]) // cycle_len - 1

        count = loop * cycle_len + scores[cycle_start][1]
        score = scores[cycle_start][0] + loop * (cycle_score - scores[cycle_start][0])
        
        q = deque([(cycle_start, score, count)])
        while q:
            node1, score, count = q.popleft()
            
            if count > K:
                break

            ans = max(ans, score)
            
            
            node2 = P[node1] - 1
            weight = C[node2]
            q.append((node2, score + weight, count + 1))

print(ans)

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

vis = [False] * N
ans = [-float("inf")] * N

for root in range(N):
  if vis[root]:
    continue
  vis[root] = True
  
  cycle = [root]
  costs = [C[root]]
  u = P[root]
  vis[u] = True
  
  while u != root:
    cycle.append(u)
    costs.append(C[u])
    u = P[u]
    vis[u] = True

  L = len(cycle)
  S = sum(costs)
  for i, v in enumerate(cycle):
    cnt = 0
    for step in range(1, min(L, K) + 1):
      cnt += costs[(i + step) % L]
      val1 = cnt
      val2 = cnt + (K - step) // L * S
      ans[v] = max(ans[v], val1, val2)

print(max(ans))

Solution (Python):
n, k = map(int, input().split())
pn = list(map(int, input().split()))
cn = list(map(int, input().split()))

ans = -float('inf')

for i in range(n): 
    start = i
    now = start
    total = 0
    ls = [0]

    for j in range(1, k+1):
        now = pn[now]-1
        total += cn[now]
        ans = max(ans, total)
        ls.append(total)
        if now == start:
            rp = j
            break
    else:
        continue

    if total <= 0:
        continue
    else:
        if k % rp == 0:
            s = k % rp
            ans2 = total * (k // rp-1) + max(ls)
            ans = max(ans, ans2)
        else:
            s = k % rp
            ans2 = total * (k//rp) + max(ls[:s+1])
            ans = max(ans, ans2)
print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
p=lnii()
c=lnii()

ans=-10**18
for i in range(n):
  ini_x=i
  x=i
  point=[]

  t_ans=0
  cnt=0
  t_max=-10**18
  while True:
    x=p[x]-1
    t_point=c[x]
    point.append(t_point)
    t_ans+=t_point
    t_max=max(t_max,t_ans)
    cnt+=1
    if x==ini_x:
      break

  if t_ans<0:
    ans=max(ans,t_max)
  else:
    num=k//cnt
    num-=1
    zan=k-(num*cnt)
    c_ans=t_ans*num
    for j in range(zan):
      x=p[x]-1
      c_ans+=c[x]
      ans=max(ans,c_ans)

print(ans)

Solution (Python):
import sys


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

def smax(b,nn):
    cc=0
    bmax9=-10**20
    for i in range(nn):

       b=p[b]
       cc+=c[p[b]]

       bmax9=max(bmax9,cc)
    return bmax9,cc

if k<=n:
    bmax=-10**20
    for st in range(n):
        bmax9,cc=smax(st,k)
        bmax=max(bmax,bmax9)
    print(bmax)
    sys.exit()
    
bmax=-10**20
for st in range(n):
    cc=0
    b=st
    chk=[-1]*n
    chk[st]=0
    for i in range(n):
       b=p[b]
       if chk[b]>=0:
           break
       else:
           chk[b]=i+1




    ki=chk[b]
    kc=i-chk[b]+1
    k2=(k-ki-1)%kc+ki+1

    bmax1,cc1=smax(st,ki+kc)
    bmax0,cc0=smax(st,ki)
    ccc=cc1-cc0
    if ccc<=0:
        bmax9,cc=smax(st,k2+kc)
    else:
        bmax9,cc=smax(st,k2+kc)
        bmax9+=ccc*((k-ki-1)//kc-1)

    bmax=max(bmax,bmax9)
print(bmax)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

N, K = MAP()
A = [a-1 for a in LIST()]
C = LIST()
MAX = 32

N = len(A)

nxt = list2d(MAX, N, -1)

score = list2d(MAX, N, -1)

mx = list2d(MAX, N, -1)
for i, a in enumerate(A):
    nxt[0][i] = a
    score[0][i] = C[a]
    mx[0][i] = C[a]

for k in range(1, MAX):
    for i in range(N):
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]
        score[k][i] = score[k-1][i] + score[k-1][nxt[k-1][i]]
        mx[k][i] = max(mx[k-1][i], score[k-1][i] + mx[k-1][nxt[k-1][i]])

ans = -INF
for i in range(N):
    cur = i
    sm = 0
    for k in range(MAX-1, -1, -1):
        if K >> k & 1:
            ans = max(ans, sm + mx[k][cur])
            sm += score[k][cur]
            cur = nxt[k][cur]
    ans = max(ans, sm)
print(ans)

Solution (Python):
N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
Disp = -10**9
for TN in range(0,N):
    Now = Next[TN]
    Point = GetP[Now]
    MAXP = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        MAXP = max(MAXP,Point)
        if Now==TN:
            RoopFlag = True
            break
    if RoopFlag and Point>0:
        Omit = K-RoopC*(K//RoopC)
        PointO = 0
        MAXO = 0
        for TO in range(0,Omit):
            Now = Next[Now]
            PointO += GetP[Now]
            MAXO = max(MAXO,PointO)          
        Disp = max(Disp,max(Point*(K//RoopC)+MAXO,Point*((K//RoopC)-1)+MAXP))
    else:
        Disp = max(Disp,MAXP)
print(Disp)

Solution (Python):
"""
解説動画のコードを参考にしました
https://atcoder.jp/contests/abc175/submissions/15945829
"""

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

ans = int(-1e18)

for start in P:
    pos = start
    scores = [] 

    while True:
        pos = P[pos-1] 
        scores.append(C[pos-1]) 
        
        if pos == start: break

    
    L = len(scores)
    S = sum(scores)
    period_score = 0
    for i in range(L):
        period_score += scores[i] 
        
        if i+1 > K: break
        total_score = period_score
        
        if S > 0:
            total_score += S * ((K-(i+1)) // L)
        ans = max(ans, total_score)

print(ans)

Solution (Python):
n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
score_max=max(C)

for L in range(n):
  score=0
  d=[0]*n
  r=0
  d[L]=1
  
  for _ in range(k):
    r+=1
    L=P[L]-1
    score+=C[L]
    score_max=max(score,score_max)
    
    if d[L]==0:
      d[L]=1
    
    elif score<0:
      break
    else:
      
      
      roop=(k//r)-1
      h=(k%r)+r
      score*=roop
      score_max=max(score,score_max)

      
      for _ in range(h):
        L=P[L]-1
        score+=C[L]
        score_max=max(score,score_max)
      break
print(score_max)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

N, K = MAP()
A = [a-1 for a in LIST()]
C = LIST()
MAX = 32

N = len(A)
nxt = list2d(MAX, N, -1)
score = list2d(MAX, N, -1)
mx = list2d(MAX, N, -1)
for i, a in enumerate(A):
    nxt[0][i] = a
    score[0][i] = C[a]
    mx[0][i] = max(C[a], 0)

for k in range(1, MAX):
    for i in range(N):
        nxt[k][i] = nxt[k-1][nxt[k-1][i]]
        score[k][i] = score[k-1][i] + score[k-1][nxt[k-1][i]]
        mx[k][i] = max(mx[k-1][i], score[k-1][i] + mx[k-1][nxt[k-1][i]])

ans = -INF
K -= 1
for a in A:
    cur = a
    sm = C[a]
    for k in range(MAX-1, -1, -1):
        if K >> k & 1:
            ans = max(ans, sm + mx[k][cur])
            sm += score[k][cur]
            cur = nxt[k][cur]
    ans = max(ans, sm)
print(ans)

Solution (Python):
n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
score_max=max(C)

for L in range(n):
  score=0
  d=[0]*n
  r=0
  d[L]=1
  
  for _ in range(k):
    r+=1
    L=P[L]-1
    score+=C[L]
    score_max=max(score,score_max)
    
    if d[L]==0:
      d[L]=1
    
    elif score<0:
      break
    else:
      roop=(k//r)-1
      
      h=(k%r)+r
      score*=roop
      score_max=max(score,score_max)

      
      for _ in range(h):
        L=P[L]-1
        score+=C[L]
        score_max=max(score,score_max)
      break
print(score_max)

Solution (Python):
from itertools import accumulate
import sys
sys.setrecursionlimit(10**8)

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]

seen = [False]*n
ans = -float('inf')
for i in range(n):
    if not seen[i]:
        sc = []
        stop = i
        while True:
            seen[i] = True
            sc.append(c[i])
            if p[i] == stop:
                break
            i = p[i]

        lens = len(sc)
        for j in range(lens):
            if j != 0:
                sc = sc[1:] + [sc[0]]
            ac = list(accumulate(sc))

            if sum(sc) <= 0:
                ans = max(ans, max(ac[:min(k, lens)]))
            else:
                if k%lens == 0:
                    ans = max(ans, ac[-1]*(k//lens-1) + max(ac))
                else:
                    ans = max(ans, ac[-1]*(k//lens) + max(ac[:k%lens]))
print(ans)

Solution (Python):
N, K = map(int, input().split())
P, C = [list(map(int, input().split())) for _ in range(2)]
ans = max(C)
for i in range(N):
    m = [0] * (N+1)
    k = i
    for j in range(N):
        m[j+1] = m[j] + C[k]
        k = P[k]-1
        if k == i:
            break
    if m[j+1] > 0:
        ans = max(ans, m[j+1] * (K//(j+1)-1) + max(m + [m[j+1] + m[k+1] for k in range(K%(j+1))]))
    else:
        ans = max(ans, max(m[1:min(j+1,K)+1]))
print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
p=lnii()
c=lnii()

ans=-10**18
for i in range(n):
  ini_x=i
  x=i
  point=[]

  t_ans=0
  cnt=0
  t_max=-10**18
  while True:
    x=p[x]-1
    t_point=c[x]
    point.append(t_point)
    t_ans+=t_point
    t_max=max(t_max,t_ans)
    cnt+=1
    if x==ini_x:
      break

  if t_ans<0:
    ans=max(ans,t_max)
  else:
    num=k//cnt
    num-=1
    c_ans=t_ans*num
    c_max=c_ans
    zan=k-(num*cnt)
    for j in range(zan):
      x=p[x]-1
      c_ans+=c[x]
      c_max=max(c_max,c_ans)
    ans=max(ans,c_max)

print(ans)