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.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -float('inf')
for i in range(n):
    x = i
    tot = 0
    s = []
    while True:
        x = p[x] - 1
        tot += c[x]
        s.append(c[x])
        if x == i:
            break
    t = 0
    l = len(s)
    for i in range(l):
        t += s[i]
        if i+1 > k:
            break
        now = t
        if tot > 0:
            e = (k-i-1)//l
            now += tot*e
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        route_append = route.append
        position = start
        while True:
            route_append(score_on[position])
            position = jumps_from[position]
            if position == start:  # Looped
                break

        length = len(route)
        total = sum(route)
        accum_tmp = 0
        for i, score in enumerate(route):
            accum_tmp += score
            if i + 1 > moves:
                break
            accum = accum_tmp
            if total > 0:
                accum += total * ((moves - (i + 1)) // length)
            ans = max(ans, accum)

        # if total > 0:
        #     q, mod = divmod(moves, length)
        #     if mod == 0:
        #         candidate = total * q
        #     else:
        #         candidate = max(list(accumulate(route))[:mod]) + total * q
        # else:
        #     candidate = max(list(accumulate(route))[:min(moves, length)])
        # ans = max(ans, candidate)
    return ans


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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = tuple(map(int,input().split()))
for i in range(n):
  p[i] -= 1

ans = -float('inf')
v = [False for _ in range(n)]
for i in range(n):
  j = i
  if v[j]:
    continue
  r = []
  while(v[j] == False):
    r.append(j)
    v[j] = True
    j = p[j]
  cr = []
  for ri in r:
    cr.append(c[ri])
  k1 = k%len(cr)
  k2 = k//len(cr)
  if k2 > 0:
    k1 += len(cr)
    k2 = max(k2-1,0)
  cr2 = cr+cr+cr
  #print(k1,k2,cr)
  now = -float('inf')
  csum = [0 for _ in range(len(cr2)+1)]
  for i0 in range(len(cr2)):
    csum[i0+1] = csum[i0]+cr2[i0]
  for i0 in range(len(cr)):
    for i1 in range(k1):
      now = max(csum[i0+i1+1]-csum[i0],now)
  if sum(cr) > 0:
    now += sum(cr)*k2
  ans = max(ans,now)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[7]:


from itertools import accumulate


# In[19]:


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]


# In[20]:


check = [False]*N
ans = -float("inf")
for i in range(N):
    if not check[i]:
        score = []
        stop = i
        while 1:
            check[i] = True
            score.append(C[i])
            if P[i] == stop:
                break
            i = P[i]
        length = len(score)
        for j in range(length):
            if j != 0:
                score = score[1:] + [score[0]]
            ac = list(accumulate(score))
            if sum(score) <= 0:
                ans = max(ans, max(ac[:min(K,length)]))
            else:
                if K%length == 0:
                    ans = max(ans, ac[-1]*(K//length-1)+max(ac))
                else:
                    ans = max(ans, ac[-1]*(K//length) + max(ac[:K%length]))
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
def main():
 
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
 
    # グルーピング
    import copy
    P2 = set(P)
    Group = []
    while len(P2)>0:
        temp = list(P2)[0]
        tempGroup = []
        while temp in P2:
            tempGroup.append(temp)
            P2.remove(temp)
            temp = P[temp-1]
        Group.append(tempGroup)
    Point = []
    for x in Group:
        tempPoint = []
        for p in x:
            tempPoint.append(C[p-1])
        Point.append(tempPoint)
 
    #print(Group)
    #print(Point)
 
    max00 = -10**9
    for x in Point:
        sumx = sum(x)
        tempx = copy.copy(x)
        tempx.extend(x)
        lenx = len(x)
        max0 = -10**9
        dp = [0]*lenx
        if sumx <= 0 or K < lenx:
            for i in range(min(lenx-1,K)):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                max0 = max(max0,max(dp))
                #print(dp)
        else:
            K2 = K % lenx
            SN = int(K/lenx)
            for i in range(lenx):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                #print(dp)
                if i < K2:
                    max0 = max(max0,max(dp) + sumx*SN)
                    #print(max0)
                else:
                    max0 = max(max0,max(dp) + sumx*(SN-1))
        max00 = max(max00,max0)
    print(max00)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
P = list(map(lambda x:x - 1, map(int,readline().split())))
C = list(map(int,readline().split()))

# 全ての頂点からスタートして、ループを探す
# ループを一周したときの得点が正であれば、
# ・[可能な限り - 1]回ループを回して、あとは得点が最大になるところまで歩く
# (-1回は、最後のループは回し切らないほうが良いパターンがあるため)

ans = - (10 ** 10)
for start in range(N):
  cur = start
  point_sum = 0
  cnt = 0
  best = []
  while True:
    cur = P[cur] # 次に進む
    cnt += 1 # ステップ数を記録
    point_sum += C[cur] # 得点を加算
    if len(best) == 0:
      best.append(point_sum)
    else:
      best.append(max(best[-1], point_sum))
    if cur == start:
      break # 始点に戻っていたらそこで終了
  #print("start",start,"best",best,"point_sum",point_sum)
  
  # ここから場合分け
  # 1.ループの得点が正のとき
  # 1.1. 可能な限りループを回して、そのあと最も得点が高いところまで行く
  # 1.2. [可能な限り - 1]回ループを回して、そのあと最も得点が高いところまで行く
  # 2.ループの得点が正でないとき
  # 2.1. Kがループ一周以上の回数のときは好きな得点を選べる
  # 2.2. Kがループ一周未満の回数のときは、そこまでの最高得点を選ぶ
  
  # 1.
  if point_sum > 0:
    # 1.1.
    loop_count = K // cnt # 可能な限り回したときのループ数
    case1_point = loop_count * point_sum
    rest = K % cnt
    if rest > 0:
      case1_point += best[rest - 1]
    #print("case1_point",case1_point)
    
    point = case1_point
    # 1.2.
    if loop_count > 0: # ループが一回以上あるときのみ検討可能
      loop_count -= 1
      case2_point = loop_count * point_sum
      # ループを一回省略しているので、好きな数を選べる
      case2_point += best[-1]
      #print("case2_point",case2_point)
      if point < case2_point:
        point = case2_point
    if ans < point:
      ans = point
  else:
    # 2. ループの得点が正でないとき
    point = 0
    if cnt <= K: # 2.1. 好きな得点を選べる
      point = best[-1]
      #print("2.1.point",point)
    else:
      # 2.2 行けるとこまで
      point = best[cnt - 1]
     # print("2,2.point",point)
    if ans < point:
      ans = point
  
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))

S = []
for i in range(N):
    p, si = i, [0]
    ps = set()
    while P[p] not in ps:
        p = P[p]
        ps.add(p)
        si.append(si[-1] + C[p])
    si = si[1:]
    S.append(si)


ans = -float('inf')
for i in range(N):
    for j in range(len(S[i])):
        if K - j - 1 < 0:
            continue

        if S[i][-1] > 0:
            roop = (K - j - 1) // len(S[i])
            ans = max(ans, S[i][-1] * roop + S[i][j])
        else:
            ans = max(ans, S[i][j])

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0 and K >= N:
        q, K = divmod(K, N)
        K += N
        ans = sumC * (q - 1)
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now):
        acc = C[now]
        ret = acc
        for _ in range(K - 1):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start))

    return mx + ans

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j+1 > K: break
    now = t
    if tot > 0:
      now += tot*((K-(j+1))//l)
    ans = max(ans, now)

print(ans)

Submission status: Accepted

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

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    cycle = 0
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        cycle += 1
        if pos == i: break
    q,r = divmod(k,cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)

Submission status: Accepted

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

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    # cycle = 0
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        # cycle += 1
        if pos == i: break
    q,r = divmod(k,l+1)
    if r == 0 and q > 1:
        r = l+1
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)

Submission status: Accepted

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = -float("inf")
    pos = n

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans = max(ans,tmp)
    
    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0 and K > cnt:
        pos = n
        d = K%cnt
        tmp = (K//cnt-1)*tmp
        ans = max(ans,tmp)
        for _ in range(d+cnt):
            pos = P[pos]-1
            tmp += C[pos]
            ans = max(ans,tmp)

    return ans

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

ans = -float("inf")
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Accepted

Solution code:
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 = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    t = 0
    for i in range(l):
        t += score[i]
        if i + 1 > k:
            break
        now = t
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())

P = list(map(int,input().split()))

C = list(map(int,input().split()))

ans = -10000000000

if K <= N:
    for i in range(N):
        count = 0
        tmp_point = 0
        nv = i
        while count < K:
            nvv = P[nv]
            nvv -= 1
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
    print(ans)
else:
    loop = [0]*N
    for i in range(N):
        count = 0
        check = [False]*N
        tmp_point = 0
        nv = i
        while True:
            nvv = P[nv]
            nvv -= 1
            if check[nvv] == True:
                break
            check[nvv] = True
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
        loop[i] = [tmp_point, count, i]
    loop.sort(reverse=True)
    #print(loop)
    new_ans = -10000000
    for value, counter, key in loop:
        if value < 0:
            break
        shou = K//counter-1
        amari = K%counter+counter
        tmp_ans = value*shou
        new_ans = max(new_ans, tmp_ans)
        count = 0
        nv = key
        while count < amari:
            nvv = P[nv]
            nvv -= 1
            tmp_ans += C[nvv]
            count += 1
            nv = nvv
            new_ans = max(new_ans, tmp_ans)

        
    print(max(loop[0][0], ans, new_ans))

Submission status: Accepted

Solution code:
def main():
    n, k = [int(e) for e in input().split()]
    P = [int(e) for e in input().split()]
    C = [int(e) for e in input().split()]

    A = []
    for i in range(1, n + 1):
        score = 0
        max_score = -(10 ** 18)
        move_count = 0
        di = i
        S = set()
        while True:
            di = P[di - 1]
            if di in S or move_count == k:
                break

            score += C[di - 1]
            if max_score < score:
                max_score = score

            move_count += 1
            S.add(di)

        if score > 0 and move_count < k:
            re = None
            if k % move_count != 0:
                re = k % move_count
                score = score * (k // move_count)
            else:
                re = move_count
                score = score * (k // move_count - 1)

            max_score = score
            di = i
            for si in range(re):
                di = P[di - 1]
                score += C[di - 1]
                if max_score < score:
                    max_score = score

        A.append(max_score)

    print(max(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def func(x):
    return x - 1
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
P = [0] + list(map(int,readline().split()))
C = [0] + list(map(int,readline().split()))

check = [False]*(N+1)
data = []
for i in range(1,N+1):
    if check[i]:
        continue
    cnt = 0
    point = []
    n = i
    while True:
        if check[n]:
            break
        check[n] = True
        cnt += 1
        point.append(C[n])
        n = P[n]
    data.append((cnt,point))

S = len(data)
INF = 10**31
ans = -INF
for i in range(S):
    cnt,point = data[i]
    a = K // cnt
    b = K % cnt
    tt = -INF
    P = [0]+point+point
    SS = list(accumulate(P))
    sum_point = sum(point)
    if a == 0:
        for k in range(1,b+1):
            for i in range(cnt):
                t = SS[i+k]-SS[i]
                tt = max(t,tt)
        tmp = tt
    elif sum_point <= 0:
        for k in range(1,cnt):
                for i in range(cnt):
                    t = SS[i+k]-SS[i]
                    tt = max(t,tt)
        tmp = tt
    else: 
        tmp1 = sum_point * a
        tmp2 = sum_point * (a-1)
        tt1 = 0
        tt2 = 0
        for k in range(1,b+1):
            for i in range(cnt):
                t1 = SS[i+k]-SS[i]
                tt1 = max(t1,tt1)
        tmp1 += tt1

        for k in range(1,cnt):
            for i in range(cnt):
                t2 = SS[i+k]-SS[i]
                tt2 = max(t2,tt2)
        tmp2 += tt2

        tmp = max(tmp1,tmp2)

    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

N, K = cin()
P = cin()
C = cin()
for i in range(N):  P[i] -= 1

ans = -(10 ** 9 + 7)

for i in range(N):
    c = []
    j = i
    
    while(P[j] != i):
        j = P[j]
        c.append(C[j])
    c.append(C[i])
    
    if sum(c) <= 0:
        acc = [0]
        for i in c:  acc.append(acc[-1] + i)
        ans = max(ans, max(acc[1:K + 1]))
        
    else:
        loop_cnt = K // len(c)
        loop_mod = K - len(c) * loop_cnt
        acc = [(loop_cnt - 1) * sum(c)]
        for i in c:  acc.append(acc[-1] + i)
        for i in range(loop_mod):  acc.append(acc[-1] + c[i])
        ans = max(ans, max(acc))
        
print(ans)

Submission status: Accepted

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

# Pが1,2,...Nの順列なので、1,2,3,4,5,3,4,5,...のような途中からのループは起こり得ない
# スタートの点数が入らないのは面倒なので、スタートの次のマスから考える

ans = -(10**9)
# どのマスから始めるか
for i in range(1, N + 1):
    # ループに入るまでの経路(iの次から)
    route = []
    visit = [False] * (N + 1)
    visit[i] = True
    now = i
    while True:
        next = P[now]
        # まだ訪れていないマスの場合
        if visit[next] == False:
            visit[next] = True
            route.append(next)
            now = next
        # 既に訪れたマスの場合
        else:
            break
    # iに戻ってくる
    route.append(i)

    cumsum = [0]
    for x in route:
        cumsum.append(cumsum[-1] + C[x])
    # print(cumsum)

    # ループするほど損する場合
    if cumsum[-1] <= 0:
        if K >= len(route):
            tmp = max(cumsum[1:])
        else:
            tmp = max(cumsum[1:K + 1])
        ans = max(ans, tmp)
    # ループするほど得する場合
    else:
        loop_size = len(route)
        loop_cnt = K // loop_size
        spare_cnt = K % loop_size
        # (loop_cnt -1)回ループしたところから
        cumsum2 = [cumsum[-1] * (loop_cnt - 1)]
        for x in route:
            cumsum2.append(cumsum2[-1] + C[x])
        for x in route[:spare_cnt]:
            cumsum2.append(cumsum2[-1] + C[x])
        tmp = max(cumsum2[1:])
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n,k=[int(i) for i in raw_input().split()]
p=[int(i)-1 for i in raw_input().split()]
c=[int(i) for i in raw_input().split()]
maxx=-10**18
for i in range(n):
  ct=0;j=0;pos=i
  v=[0]*n
  arr=[]
  while j<k:
    if(v[pos]==1):
  	    break
    v[pos]=1
    ct+=c[pos]
    pos=p[pos]
    arr.append(ct)
    j+=1
  val=0
  if(ct>0):
  	val=ct*((k-j)/j)
  else:
  	val=0
  k1=k
  k1%=j
  k1+=j
  for i1 in range(len(arr)):
  	if(k1-i1>j):
  	    maxx=max(maxx,val+arr[i1],val+ct+arr[i1])
  	else:
  	    maxx=max(maxx,val+arr[i1])
print maxx

Submission status: Accepted

Solution code:
import itertools as it

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

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    # 累積和
    scores = list(it.accumulate([0]+[C[i] for i in cycle]))
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    # 1cycle以下の場合は全て調べればよし
    if K <= len(cycle):
        max_score = max(scores[1:K+1])
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがマイナスならサイクルを回らないのがハイスコア
    if score_per_cycle <= 0:
        max_score = max(scores[1:])
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがプラスなら限界までサイクルを回るのがハイスコア
    # ラスト1cycleのスコアを調べる
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        # 何周したか
        loop_cnt = move // cycle_len
        # あまり
        rest_move = move % cycle_len
        # スコア = 1周ごとのスコア * 何周したか + あまり
        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))

Submission status: Accepted

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

#到達したかの判定
#masu=[0]*(n+1)
#nは1~n
def junkan(N):
  #到達したかの判定
  masu=[0]*(n+1)
  ans=0
  ans22=-(10**9+1)
  junkan_flag=False
  now_mas=p[N-1]
  count=0
  masu[now_mas]=1
  #このwhileはせいぜい5000
  while True:
    if count>=k:
      break
    if (count!=0 and masu[now_mas]==1):
      junkan_flag=True
      break
    count+=1
    ans+=c[now_mas-1]
    
    if ans22<ans:
      ans22=ans
      
    masu[now_mas]=1
    now_mas=p[now_mas-1]
  if junkan_flag==True and ans>0:
    ans=(((k-1)//count)-1)*ans
    
    if ans22<ans:
      ans22=ans
    for i in range(k-((k-1)//count-1)*count):
      ans+=c[now_mas-1]
      if ans22<ans:
        ans22=ans
        
      now_mas=p[now_mas-1]
    return max(ans,ans22)
  
  else:
    return max(ans,ans22)
answ=-(10**9+1)

for i in range(1,n+1):
  hantei=junkan(i)
  if answ < hantei:
    answ=hantei
print(answ)

Submission status: Accepted

Solution code:
import math

def split_to_loops(G):
    # G[i]: i の次の頂点(0 <= i <= |G|-1) を格納しているリストがあるとき、
    # ループ単位にリストを分割する。
    # ex) G = [1, 3, 4, 0, 2]
    # => "0 -> 1 -> 3 -> 0" というループと
    #    "2 -> 4 -> 2" というループがある
    # このメソッドでは、[[0,1,3],[2,4]]が返される

    loops = []
    _all = set(range(len(G)))

    while _all:
        s = _all.pop()
        loop = [s]
        v = G[s]
        while v != s:
            _all.remove(v)
            loop.append(v)
            v = G[v]

        loops.append(loop)

    return loops

def find_max_continued(A, n):
    # A 内で連続した1個以上n個以内の領域の合計の最大値を見つける
    # ex) A = [-2, 4, 3, -1, 2, 6, 4, 5, -3], n = 3
    #       => [6, 4, 5] の合計 =15 が最大
    # ex) A = [-2, 4, 3, -1, 2, 6, -4, 5, -3], n = 3
    #       => [2, 6] の合計 =8 が最大
    # ex) A = [-2, 4, 3, -1, 2, 6, -4, 5, -3], n = 4
    #       => [3, -1, 2, 6] の合計 =10 が最大
    # ex) A = [-2, -4, -3, -1, -2, -6, -4, -5, -3], n = 3
    #       => [-1] の合計 =-1 が最大

    # n = 1のとき
    _max = max(A)

    # n = 2以上
    L = len(A)
    for d in range(2, min(n+1, L+1)):
        _sum = sum(A[:d])
        _max = max(_max, _sum)
        # 領域を右にずらしながら合計を計算することで、O(L) で計算できる 
        for i in range(d, L):
            _sum += A[i] - A[i-d]
            _max = max(_max, _sum)
        for i in range(d):
            _sum += A[i] - A[L-d+i]
            _max = max(_max, _sum)

    return _max

def find_max_in_one_loop(loop, K, C):
    # loopにおける1回以上K回以内の移動でのスコアの最大値を見つける
    L = len(loop)
    loop_c = [C[v] for v in loop] # ループに登場するマスのスコアのリスト

    # 一周したときのスコア
    sum_1_loop = sum(loop_c)
    # print(f'{loop_c=}, {sum_1_loop=}')

    if sum_1_loop < 0:
        # 一周したときに負になるようなら、ループしないほうがいい
        return find_max_continued(loop_c, min(K, L))
    else:
        # 一周以上移動できない場合
        if K < L:
            return find_max_continued(loop_c, K)

        # 一周以上移動できる場合
        # できるだけループしたほうがいい

        n_loops = K // L # ループできる回数

        # ただし、スコアが [1 1 1 -2] のようになっている場合、
        # 1周するより負の数を避けて途中で終了したほうがいいので、
        # 一旦わざとループできる回数から1周分減らしておく
        n_loops -= 1
        
        score = sum_1_loop * n_loops
        K -= n_loops * L # 残りの移動回数 (L <= K < 2*L)

        # 一周未満の時のスコアの最大値
        score_no_loop = find_max_continued(loop_c, L)
        # print(f'{K=}, {L=}, {n_loops=}, {score=}, {score_no_loop=}')
        # 一周してさらにK-L回以内で移動するときのスコア
        score_loop = sum_1_loop
        if K != L:
            # print(f'{K=}, {L=}, {K-L}, {find_max_continued(loop_c, K - L)}')
            score_loop += find_max_continued(loop_c, K - L)
        # 最後、一周しないほうがいいか、一周したほうがいいか、スコアの大きいほうを選ぶ
        score += max(score_no_loop, score_loop)
        return score

def main():
    N, K = map(int, input().split())
    # P は番号を1引くことで配列で扱いやすくする
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))

    # ループごとに分割
    # ex) P = [1, 3, 4, 0, 2]
    # => "0 -> 1 -> 3 -> 0" というループと
    #    "2 -> 4 -> 2" というループがある
    # => loops = [[0,1,3],[2,4]]
    loops = split_to_loops(P)
    # print(f'{loops=}')

    ans = -(10 ** 10)
    for loop in loops:
        # [0,1,3] などのループ単位で、1回以上K回以内の移動での最大値を見つける
        # その最大値の中からさらに最大値を見つけて、答えとする
        ans = max(ans, find_max_in_one_loop(loop, K, C))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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])

#print(Num, E, F, sep="\n")
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)