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: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = [int(x)-1 for x in input().split()]
c = [int(x) for x in input().split()]
each_point = []
checked = [0]*n

for i in range(n):
  now = i
  check = []
  max_point = c[p[now]]
  point = 0
  
  if checked[i]:
    pass
  else:
    for j in range(k):
      if now in check:
        l = len(check)
        lastpoint = point * int(k/l)
        for e in range(k%l):
          now = p[now]
          lastpoint += c[now]
        each_point.append(lastpoint)

        now = check.index(now)+1
        c1 = check[now:]
        c2 = check[:now]
        for e in reversed(c1):
          each_point.append(p[e])
        for e in reversed(c2):
          each_point.append(p[e])
        break
      check.append(now)  
      checked[now] = 1
      now = p[now]
      point += c[now]
      if max_point < point:
        max_point = point
  
  each_point.append(max_point)
  
print(max(each_point))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

#それぞれの開始マスに対して以下を調べる O(N^2)

loop_bgn = [0] * N
loop_num = [1] * N
loop_pre = [0] * N
loop_sum = [0] * N

for i in range(N):
    #1)循環の開始マス
    cnt = [0] * (N + 1)
    now_p = P[i]
    cnt[now_p] = 1
    while True:
        now_p = P[now_p - 1]
        if cnt[now_p]:
            loop_bgn[i] = cnt[now_p]
            break
        cnt[now_p] = 1


    #3)ループまでの合計
    now_p = P[i]
    while now_p != loop_bgn[i]:
        now_p = P[now_p - 1]
        loop_pre[i] += C[now_p - 1]

    #2)ループの数
    #4)ループ内合計
    now_p = P[loop_bgn[i] - 1]
    loop_sum[i] += C[loop_bgn[i] - 1]
    while now_p != loop_bgn[i]:
        loop_num[i] += 1
        loop_sum[i] += C[loop_bgn[i] - 1]
        now_p = P[now_p - 1]
print(loop_bgn)
print(loop_num)
print(loop_pre)
print(loop_sum)

"""


最大値は
1) K <= Nのとき
O(NK)
2) K > N のとき
a) Nまでの最大値 O(N^2)
b) ループまでの合計+ループ数*ループ合計+余りでの最大値

"""

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    P_list = list(map(int, sys.stdin.readline().split()))
    C_list = list(map(int, sys.stdin.readline().split()))


    score_max = -float("inf")

    for i in range(N):
        idx = P_list[i] - 1
        visited = {}
        c_sum = 0
        cum_sum = [0]
        cnt = 0

        while True:
            if (idx in visited) or (cnt > K):
                break

            c_sum += C_list[idx]
            cum_sum.append(c_sum)
            visited[idx] = cnt

            idx = P_list[idx] - 1
            cnt += 1
        

        if cnt <= K:
            cnt_cycle = cnt - visited[idx]
            cum_sum_delta = cum_sum[cnt] - cum_sum[ visited[idx] ]
            K_remain = K - cnt
            times = K_remain // cnt_cycle
            
            if cum_sum_delta >= 0:
                if times >= 1:
                    # calculate cum_sum from previous cycle to end
                    c_sum += (times - 1) * cum_sum_delta
                    cum_sum.append(c_sum)
                    K_remain = (K_remain % cnt_cycle) + cnt_cycle
            
            else:
                K_remain = 0


            for j in range(K_remain):
                c_sum += C_list[idx]
                cum_sum.append(c_sum)

                idx = P_list[idx] - 1
        
        
        score_max = max( score_max , max(cum_sum[1:]) )

    
    print(score_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
l=list(map(int,input().split()))
inf=10**11 * (-1)
point_l=list(map(int,input().split()))
import math
l_count=[0]*N
from collections import deque
def search(first):
   l_count[first]=1
   tmp_l=deque([])
   start=first
   count=0
   next=l[start]-1
   while first!=next:
      count+=1
      start=next
      l_count[start]=1
      tmp_l.append(point_l[start])
      next=l[start]-1
   l_count[next]=1
   tmp_l.append(point_l[next])
   more= math.ceil((K-len(tmp_l))/len(tmp_l)) if K>len(tmp_l) else 0
   plus=K%len(tmp_l) if len(tmp_l)!=K else K
   maximum=inf
   for i in range(len(tmp_l)):
      tmp=0
      mem=inf
      for j in range(min(plus,len(tmp_l))):
         tmp+=tmp_l[j]
         mem=max(mem,tmp)
      maximum=max(maximum,mem)
      tmp_l.rotate()
   return more*sum(tmp_l)+maximum if more*sum(tmp_l)>0 else maximum
ans=inf
for i in range(N):
   if l_count[i] == 0:
      ans=max(ans,search(i))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    P_list = list(map(int, sys.stdin.readline().split()))
    C_list = list(map(int, sys.stdin.readline().split()))


    score_max = -float("inf")

    for i in range(N):
        idx = P_list[i] - 1
        visited = {}
        c_sum = 0
        cum_sum = [0]
        cnt = 0

        while True:
            if (idx in visited) or (cnt > K):
                break

            c_sum += C_list[idx]
            cum_sum.append(c_sum)
            visited[idx] = cnt

            idx = P_list[idx] - 1
            cnt += 1
        

        if cnt < K:
            cnt_cycle = cnt - visited[idx]
            cum_sum_delta = cum_sum[cnt] - cum_sum[ visited[idx] ]
            K_remain = K - cnt
            times = K_remain // cnt_cycle
            
            if cum_sum_delta >= 0:
                if times >= 1:
                    # calculate cum_sum from previous cycle to end
                    c_sum += (times - 1) * cum_sum_delta
                    cum_sum.append(c_sum)
                    K_remain = (K_remain % cnt_cycle) + cnt_cycle
            
            else:
                K_remain = 0


            for j in range(K_remain):
                c_sum += C_list[idx]
                cum_sum.append(c_sum)

                idx = P_list[idx] - 1
        
        
        score_max = max( score_max , max(cum_sum[1:]) )

    
    print(score_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    P_list = list(map(int, sys.stdin.readline().split()))
    C_list = list(map(int, sys.stdin.readline().split()))


    score_max = -float("inf")

    for i in range(N):
        idx = P_list[i] - 1
        visited = {}
        c_sum = 0
        cum_sum = [0]
        cnt = 0

        while True:
            if (idx in visited) or (cnt > K):
                break

            c_sum += C_list[idx]
            cum_sum.append(c_sum)
            visited[idx] = cnt

            idx = P_list[idx] - 1
            cnt += 1
        

        if cnt < K:
            cnt_cycle = cnt - visited[idx]
            cum_sum_delta = cum_sum[cnt] - cum_sum[ visited[idx] ]
            K_remain = K - cnt
            times = K_remain // cnt_cycle
            
            if cum_sum_delta >= 0:
                if times >= 1:
                    # calculate cum_sum from previous cycle to end
                    c_sum += (times - 1) * cum_sum_delta
                    K_remain = (K_remain % cnt_cycle) + cnt_cycle
            
            else:
                K_remain = 0


            for j in range(K_remain):
                c_sum += C_list[idx]
                cum_sum.append(c_sum)

                idx = P_list[idx] - 1
        
        
        score_max = max( score_max , max(cum_sum[1:]) )

    
    print(score_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    P_list = list(map(int, sys.stdin.readline().split()))
    C_list = list(map(int, sys.stdin.readline().split()))


    score_max = -float("inf")

    for i in range(N):
        idx = P_list[i] - 1
        visited = {}
        c_sum = 0
        cum_sum = [0]
        cnt = 0

        while True:
            if (idx in visited) or (cnt > K):
                break

            c_sum += C_list[idx]
            score_max = max(score_max, c_sum)
            cum_sum.append(c_sum)
            visited[idx] = cnt

            idx = P_list[idx] - 1
            cnt += 1
        

        if cnt < K:
            cnt_cycle = cnt - visited[idx]
            cum_sum_delta = cum_sum[cnt] - cum_sum[ visited[idx] ]
            K_remain = K - cnt
            times = K_remain // cnt_cycle
            
            if cum_sum_delta >= 0:
                if times >= 1:
                    # calculate cum_sum from previous cycle to end
                    c_sum += (times - 1) * cum_sum_delta
                    score_max = max(score_max, c_sum)
                    K_remain = (K_remain % cnt_cycle) + cnt_cycle
            
            else:
                K_remain = 0


            for j in range(K_remain):
                c_sum += C_list[idx]
                score_max = max(score_max, c_sum)
                cum_sum.append(c_sum)

                idx = P_list[idx] - 1


    print(score_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import io
#from collections import Counter
#from collections import deque
#from decimal import Decimal
#import bisect
#from functools import reduce
#import heapq


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    P_list = list(map(int, sys.stdin.readline().split()))
    C_list = list(map(int, sys.stdin.readline().split()))


    score_max = -float("inf")

    for i in range(N):
        idx = P_list[i] - 1
        visited = {}
        c_sum = 0
        cum_sum = [0]
        cnt = 0

        while True:
            if (idx in visited) or (cnt > K):
                break

            c_sum += C_list[idx]
            cum_sum.append(c_sum)
            visited[idx] = cnt

            idx = P_list[idx] - 1
            cnt += 1
        

        if cnt < K:
            cnt_cycle = cnt - visited[idx]
            cum_sum_delta = cum_sum[cnt] - cum_sum[ visited[idx] ]
            K_remain = K - cnt
            times = K_remain // cnt_cycle
            
            if times >= 1:
                # calculate cum_sum from previous cycle to end
                c_sum += (times - 1) * cum_sum_delta
                K_remain = (K_remain % cnt_cycle) + cnt_cycle

            for j in range(K_remain):
                c_sum += C_list[idx]
                cum_sum.append(c_sum)

                idx = P_list[idx] - 1
        
        
        score_max = max( score_max , max(cum_sum[1:]) )

    
    print(score_max)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main(N, K, plist, slist, max_score):
    for i in range(N):
      j = i
      loop_score = 0
      high = [-10**15,0]
      loop = 0
      for k in range(N+1):
        loop_score += slist[j]
        loop += 1
        if high[0] < loop_score:
          high = [loop_score, k]
        j = plist[j]
        if j == i:
          break
      if loop_score < 0:
        tmp_max = high[0]
      else:
        tmp_max = high[0] + (K - high[1] - 1)//(loop) * loop_score
      max_score = max(max_score, tmp_max)
    return max_score
 
 
N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main(N, K, plist, slist, max_score):
    for i in range(N):
      j = i
      loop_score = 0
      high = [0,0]
      loop = 0
      for k in range(N):
        loop_score += slist[j]
        loop += 1
        if high[0] < loop_score:
          high = [loop_score, k]
        j = plist[j]
        if j == i:
          break
      if loop_score < 0:
        tmp_max = high[0]
      else:
        tmp_max = high[0] + loop_score * (K - high[1] - 1)//(loop)
      max_score = max(max_score, tmp_max)
    return max_score
 
 
N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main(N, K, plist, slist, max_score):
    for i in range(N):
      j = i
      loop_score = 0
      high = [0,0]
      score = []
      for k in range(K):
        loop_score += slist[j]
        score.append(loop_score)
        if high[0] < loop_score:
          high = [loop_score, k]
        j = plist[j]
        if j == i:
          break
      if loop_score < 0:
        tmp_max = high[0]
      else:
        tmp_max = high[0] + loop_score * (K - high[1] - 1)//(len(score))
      max_score = max(max_score, tmp_max)
    return max_score
 
 
N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
moves = [0] + list(map(int, input().split()))
points = [0] + list(map(int, input().split()))
INF = 10**10

arrived = [0 for _ in range(N+1)]
answer = -INF
for move in range(1, N+1):
  if arrived[move] == 1:
    continue
  else:
    arrived[move] = 1
    komas = [move]
    next = moves[move]
    while(arrived[next] == 0):
      arrived[next] = 1
      komas.append(next)
      next = moves[next]
    len_k = len(komas)
    sum_k = [0 for _ in range(len_k*2)]
    sum_k[0] = points[komas[0]]
    for i in range(1, len_k*2):
      sum_k[i] = sum_k[i-1] + points[komas[i%len_k]]
    scores = [-INF for _ in range(len_k+1)]
    for j in range(len_k):
      for k in range(1, len_k+1):
        scores[k] = max(scores[k], sum_k[j+k] - sum_k[j])
    if K > len_k and scores[len_k] > 0:
      max_s = -INF
      max_k = -INF
      for m in range(1, len_k+1):
        if m <= K%len_k:
          max_k = max(max_k, scores[m])
        max_s = max(max_s, scores[m])
      answer = max(answer, max_k + scores[len_k]*(K//len_k), max_s)
    else:
      max_s = -INF
      for m in range(1, min(K, len_k)+1):
        max_s = max(max_s, scores[m])
      answer = max(answer, max_s)
print(answer)

Submission status: Wrong Answer

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

score = []
ans = -10 ** 10
o = k // n
z = k % n

for i in range(n):
    score.append(0)
    if k <= n or sum(c) <= 0:
        a = p[i] - 1
        for j in range(k):
            score[i] += c[a]
            a = p[a] - 1
            if score[i] > ans:
                ans = score[i]

if k > n and sum(c) > 0:
    for l in range(n):
        score[l] += sum(c) * o
        
        b = p[l] - 1
        for m in range(z):
            score[l] += c[b]
            b = p[b] - 1
            if score[l] > ans:
                ans = score[l]
    
    for q in range(n):
        score[q] = sum(c) * (o-1)
        d = p[q] - 1
        for r in range(n):
            score[q] += c[d]
            d = p[d] - 1
            if score[q] > ans:
                ans = score[q]

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    ans = -INF
    for i in range(N):
        # iを含むサイクルの探索
        cycle = []
        c = i
        while True:
            c = P[c]
            cycle.append(c)
            if c == i:
                break
        len_cycle = len(cycle)
        # print(cycle)

        # 最大スコアの探索
        score = 0

        # Kの残り
        r = K
        cycle_score_total = sum([C[j] for j in cycle])
        if len_cycle < K:
            # 周回して増えるなら周回する
            if cycle_score_total > 0:
                score += K // len_cycle * cycle_score_total
                # 周回後の余り
                r = K % len_cycle
            # 周回して増えないなら周回しない
            else:
                # サイクル一周までの範囲でどこまでもいける
                r = len_cycle

        # Kの残っている範囲で最大スコア探索
        if r > 0:
            cycle_score = [C[j] for j in cycle[:r]]
            cycle_score_cum = list(itertools.accumulate(cycle_score))
            score += max(cycle_score_cum)

        ans = max(score, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    ans = -INF
    for i in range(N):
        # iを含むサイクルの探索
        cycle = []
        c = i
        while True:
            c = P[c]
            cycle.append(c)
            if c == i:
                break
        len_cycle = len(cycle)

        # 最大スコアの探索
        score = 0

        # Kの残り
        r = K
        cycle_score_total = sum([C[j] for j in cycle])
        if len_cycle < K:
            # 周回して増えるなら周回する
            if cycle_score_total > 0:
                score += K // len_cycle * cycle_score_total
                # 周回後の余り
                r = K % len_cycle
            # 周回して増えないなら周回しない
            else:
                # サイクル一周までの範囲でどこまでもいける
                r = len_cycle

        # Kの残っている範囲で最大スコア探索
        # cycle_score = [C[cycle[j]] for j in range(r)]
        # cycle_score_cum = list(itertools.accumulate(cycle_score))
        cycle_score_cum = [0]
        score += max(cycle_score_cum)

        ans = max(score, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    # Pをサイクルに分割
    cycle_C = []
    visited = [False] * N
    for i in range(N):
        if not visited[i]:
            c = i
            tmp_C = [C[c]]
            while True:
                visited[c] = True
                c = P[c]
                if visited[c]:
                    cycle_C.append(tmp_C)
                    break
                tmp_C.append(C[c])
    # print(cycle_C)

    ans = -INF
    for i in cycle_C:
        cycle_sum = sum(i)
        # print(cycle_sum)

        # Kがサイクル長より大きく、1週の点数が正ならば、周回する
        if len(i) < K and cycle_sum > 0:
            # サイクルを2つくっつけて累積和を取り、その差を全探索
            i_cum = list(itertools.accumulate(i * 2, initial=0))
            tmp = -INF
            for j, k in itertools.combinations(range(len(i) * 2), 2):
                if k - j <= K % len(i):
                    tmp = max(i_cum[k] - i_cum[j], tmp)
            tmp += K // len(i) * cycle_sum 

        else:
            i_cum = list(itertools.accumulate(i * 2, initial=0))
            tmp = -INF
            for j, k in itertools.combinations(range(len(i) * 2), 2):
                if k - j <= K:
                    tmp = max(i_cum[k] - i_cum[j], tmp)

        ans = max(tmp, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p_list = list(map(lambda x: int(x) - 1, input().split()))
c_list = list(map(int, input().split()))

max_score = -(1 << 64)
cycles = []
cycled = [False] * n
for i in range(n):
    if cycled[i]:
        continue

    cycle = [i]
    cycled[i] = True
    while p_list[cycle[-1]] != cycle[0]:
        cycle.append(p_list[cycle[-1]])
        cycled[cycle[-1]] = True

    cycles.append(cycle)

for cycle in cycles:
    cycle_len = len(cycle)

    accum = [0]
    for i in range(cycle_len * 2):
        accum.append(accum[-1] + c_list[cycle[i % cycle_len]])

    cycle_score = accum[cycle_len]

    max_series_sums = [max([accum[i + length] - accum[i]
                            for i in range(cycle_len)])
                       for length in range(cycle_len)]

    if cycle_len >= k:
        score = max(max_series_sums[1:k + 1])
    elif cycle_score <= 0:
        score = max(max_series_sums[1:])
    else:
        max_cycle_num, cycle_rem = divmod(k, cycle_len)
        score = max(cycle_score * (max_cycle_num - 1) + max(max_series_sums),
                    cycle_score * max_cycle_num + max(max_series_sums[:cycle_rem + 1]))

    max_score = max(max_score, score)

print(max_score)

Submission status: Wrong Answer

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

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


maxscore = 0

for i in range(N):
    score = 0

    guess = P[i]
    for j in range(K):
        score += C[guess-1]
        guess = P[guess-1]

        if score > maxscore:
            maxscore = score


print(maxscore)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    loop_score = 0
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, score2)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    else:
        score = MAX

    ans = max(ans, score)


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    loop_score = 0
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if j == k:
            score = MAX
            break
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, score2)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    ans = max(ans, score)


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    loop_score = 0
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, score2)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    ans = max(ans, score)


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import random

def main():
  n, k = map(int, input().strip().split())
  lp = list(map(lambda p:int(p)-1, input().strip().split()))
  lc = list(map(int, input().strip().split()))
  
  used = [0] * n
  loops = []
  cnt = 0
  for i in range(n):
    if used[i] == 1:
      continue
      
    ic = i
    loop = []
    while True:
      loop.append(lc[ic])
      used[ic] = 1      
      cnt += 1
      ic = lp[ic]
      if used[ic] == 1:
        break
    if len(loop) > 0:
      loops.append(loop)
    
  def f(loop, k):
    if max(loop) < 0:
      return max(loop)
    
    score = 0
    if sum(loop) > 0:
      score += (k // len(loop)) * sum(loop)
      k = k % len(loop)
    k = min(k, len(loop)-1)
    loop = 2 * loop
    
    i = 0
    subscores = [0]
    subscore = 0
    cnt = 0
    while i < len(loop):
      if loop[i] >= 0:
        subscore += loop[i]
        cnt += 1
        if cnt > k:
          subscore -= loop[i-k]
        if cnt >= k:
          subscores.append(subscore)
      else:
        subscores.append(subscore)
        subscore = 0
        cnt = 0
      i += 1
      
    score += max(subscores)
    return score
  
  print(max([f(loop, k) for loop in loops]))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    start = i
    next = p[i]
    loop_score = 0
    score = 0
    MAX = -float("INF")
    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == start:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score)
                    next = p[next]
                score = max(score1, score2)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    ans = max(ans, score)


print(ans)