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:
from itertools import accumulate 

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

ans = -10**9-1
seen = [False]*N
for i in range(N):
    if seen[i]:
        continue
    loop = []
    now = i
    while seen[now] == False:
        seen[now] = True
        loop.append(C[now])
        now = P[now]
    loop_size = len(loop)
    loop_score = sum(loop)
    cumsum = [0]+list(accumulate(loop+loop))
    for j in range(1, loop_size+2):
        for l in range(loop_size):
            r = l+j
            subseq = cumsum[r] - cumsum[l]
            ans = max(ans, subseq, subseq+loop_score*((K-j)//loop_size))
print(ans)

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
routes = list(map(int, input().split()))
points = list(map(int, input().split()))

def separation(routes, points):
    remain = [i for i in routes]
    pos_ans = []
    tmp = remain[0]
    pos_cirs = []
    remain.remove(tmp)
    pos_cirs.append(points[tmp-1])
    while True:
        if routes[tmp-1] in remain:
            pos_cirs.append(points[routes[tmp-1]-1])
            tmp = routes[tmp-1]
        else:
            pos_ans.append(pos_cirs)
            tmp = remain[0]
            pos_cirs = []
            pos_cirs.append(points[tmp-1])
        remain.remove(tmp)
        if len(remain) == 0:
            pos_ans.append(pos_cirs)
            break
    return pos_ans

ans = -10**18
point_g = separation(routes, points)

for i in range(len(point_g)):
    tmp_point = point_g[i]
    total = sum(tmp_point)
    partial_points = []
    if total <= 0:
        for j in range(len(tmp_point)):
            tmp_sum = tmp_point[j]
            partial_points.append(tmp_sum)
            for l in range(1,len(tmp_point)):
                if l + j < len(tmp_point):
                    tmp_sum += tmp_point[j+l]
                    partial_points.append(tmp_sum)
                else:
                    tmp_sum += tmp_point[l+j - len(tmp_point)]
                    partial_points.append(tmp_sum)  
            
        if ans < max(partial_points):
            ans = max(partial_points)
            
    else:
        circulations = k // len(tmp_point) 
        remain_time = k % len(tmp_point)
        tmp_ans = total * circulations
        for j in range(len(tmp_point)):
            tmp_sum = tmp_point[j]
            partial_points.append(tmp_sum)
            for l in range(1,remain_time):
                if l + j < len(tmp_point):
                    tmp_sum += tmp_point[j+l]
                    partial_points.append(tmp_sum)
                else:
                    tmp_sum += tmp_point[l+j - len(tmp_point)]
                    partial_points.append(tmp_sum)
        
        if ans < tmp_ans + max(partial_points):
            ans = tmp_ans + max(partial_points)
            
print(ans)

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
routes = list(map(int, input().split()))
points = list(map(int, input().split()))

def separation(routes, points):
    remain = [i for i in routes]
    ans, pos_ans = [], []
    tmp = remain[0]
    cirs, pos_cirs = [], []
    remain.remove(tmp)
    cirs.append(tmp)
    pos_cirs.append(points[tmp-1])
    while True:
        if routes[tmp-1] in remain:
            cirs.append(routes[tmp-1])
            pos_cirs.append(points[routes[tmp-1]-1])
            tmp = routes[tmp-1]
        else:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            tmp = remain[0]
            cirs, pos_cirs = [], []
            cirs.append(tmp)
            pos_cirs.append(points[tmp-1])
        remain.remove(tmp)
        if len(remain) == 0:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            break
    return ans, pos_ans

ans = -10**18
route_g, point_g = separation(routes, points)

for i in range(len(route_g)):
    tmp_point = point_g[i]
    total = sum(tmp_point)
    partial_points = []
    if total <= 0:
        for j in range(len(tmp_point)):
            tmp_sum = tmp_point[j]
            partial_points.append(tmp_sum)
            for l in range(1,len(tmp_point)):
                if l + j < len(tmp_point):
                    tmp_sum += tmp_point[j+l]
                    partial_points.append(tmp_sum)
                else:
                    tmp_sum += tmp_point[l+j - len(tmp_point)]
                    partial_points.append(tmp_sum)  
            
        if ans < max(partial_points):
            ans = max(partial_points)
            
    else:
        circulations = k // len(tmp_point) 
        remain_time = k % len(tmp_point)
        tmp_ans = total * circulations
        for j in range(len(tmp_point)):
            tmp_sum = tmp_point[j]
            partial_points.append(tmp_sum)
            for l in range(1,remain_time):
                if l + j < len(tmp_point):
                    tmp_sum += tmp_point[j+l]
                    partial_points.append(tmp_sum)
                else:
                    tmp_sum += tmp_point[l+j - len(tmp_point)]
                    partial_points.append(tmp_sum)
        
        if ans < tmp_ans + max(partial_points):
            ans = tmp_ans + max(partial_points)
            
print(ans)

Submission status: Wrong Answer

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 = max(C)
for start in range(N):
    now = P[start]
    score = C[now]
    c = K-1
    k = 1
    kick = [score]
    step = None
    kick_score = None
    x = True
    if now == start:
        step = k
        kick_score = score
        x = False
    while c > 0 and k < N and x:
        now = P[now]
        score += C[now]
        ans = max(ans, score)
        c -= 1
        k += 1
        kick.append(score)
        if now == start:
            step = k
            kick_score = score
            break
    if step != None and kick_score > 0 and K%step != 0:
        ans = max(ans, kick_score*(K//step)+max(kick[:K%step]))
print(ans)

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
routes = list(map(int, input().split()))
points = list(map(int, input().split()))

def separation(routes, points):
    remain = [i for i in routes]
    ans, pos_ans = [], []
    tmp = remain[0]
    cirs, pos_cirs = [], []
    remain.remove(tmp)
    cirs.append(tmp)
    pos_cirs.append(points[tmp-1])
    while True:
        if routes[tmp-1] in remain:
            cirs.append(routes[tmp-1])
            pos_cirs.append(points[routes[tmp-1]-1])
            tmp = routes[tmp-1]
        else:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            tmp = remain[0]
            cirs, pos_cirs = [], []
            cirs.append(tmp)
            pos_cirs.append(points[tmp-1])
        remain.remove(tmp)
        if len(remain) == 0:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            break
    return ans, pos_ans

ans = -10**18
route_g, point_g = separation(routes, points)

for i in range(len(route_g)):
    tmp_point = point_g[i]
    total = sum(tmp_point)
    partial_points = []
    if total < 0:
        for l in range(1, len(tmp_point)+1):
            for j in range(len(tmp_point)):
                if l + j <= len(tmp_point):
                    partial_points.append(sum(tmp_point[j:j+l]))
                else:
                    partial_points.append(sum(tmp_point[j:]) + sum(tmp_point[:l+j-len(tmp_point)]))
        if ans < max(partial_points):
            ans = max(partial_points)
    else:
        circulations = k // len(tmp_point) 
        remain_time = k - circulations
        tmp_ans = total * circulations
        for l in range(1, remain_time+1):
            for j in range(len(tmp_point)):
                if l + j <= len(tmp_point):
                    partial_points.append(sum(tmp_point[j:j+l]))
                else:
                    partial_points.append(sum(tmp_point[j:]) + sum(tmp_point[:l+j-len(tmp_point)]))
        if ans < tmp_ans + max(partial_points):
            ans = tmp_ans + max(partial_points)
            
print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()


ignore = [-1] * N
ans = -float('inf')
for i in range(N):
    if ignore[i] >= 0:
        continue
    ### ループ生成 ###
    ignore[i] = 1
    opt_l = [i]
    to = P[i]
    while ignore[to] == -1:
        opt_l.append(to)
        ignore[to] = 1
        to = P[to]
    ###
    ### 作成したループで得点リスト生成 ###
    n = len(opt_l)
    point = [0] * n
    for i in range(n):
        point[i] = C[opt_l[i]]
    ###
    ### 得点リスト内の連続する区間の総和のうちの最大値を累積和を使って求める ###
    sum_roop = sum(point)
    # ループの累積和作成
    imos = [0]
    point += point
    for i in range(len(point)):
        imos.append(imos[i] + point[i])
    #
    ran = min(n, K)
    for i in range(ran):
        # 区間の大きさran以下についての総和を求める
        for j in range(1, ran + 1):
            if sum_roop >= 0:
                opt = imos[i + j] - imos[i] + ((K - j) // n) * sum_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)
    ###
print(ans)

Submission status: Wrong Answer

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

p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

p_flag = [0 for _ in range(len(p))]
loop_max = []
loop_len = []
S = []
ans = []

for i in range(len(p)):
    if p_flag[i] == 1:
        continue
    now = i
    temp_len = 0
    temp_s = 0
    temp_max = - (10**9 + 1)
    while True:
        now = p[now] - 1
        temp_len += 1
        temp_s += c[now]
        if temp_max < c[now]:
            temp_max = c[now]
        p_flag[now] = 1

        # 最初に戻ってきたら
        if now == i:
            break

    loop_len.append(temp_len)
    loop_max.append(temp_max)
    S.append(temp_s)

for i in range(len(S)):
    if S[i] > 0:
        ans.append(((k-1)//loop_len[i])*S[i] + loop_max[i])
    else:
        ans.append(loop_max[i])

# print(loop_max)
# print(ans)
print(max(ans))

Submission status: Wrong Answer

Solution code:
n , k = map(int, input().split())
routes = list(map(int, input().split()))
points = list(map(int, input().split()))

def separation(routes, points):
    remain = [i for i in routes]
    ans, pos_ans = [], []
    tmp = remain[0]
    cirs, pos_cirs = [], []
    remain.remove(tmp)
    cirs.append(tmp)
    pos_cirs.append(points[tmp-1])
    while True:
        if routes[tmp-1] in remain:
            cirs.append(routes[tmp-1])
            pos_cirs.append(points[routes[tmp-1]-1])
            tmp = routes[tmp-1]
        else:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            tmp = remain[0]
            cirs, pos_cirs = [], []
            cirs.append(tmp)
            pos_cirs.append(points[tmp-1])
        remain.remove(tmp)
        if len(remain) == 0:
            ans.append(cirs)
            pos_ans.append(pos_cirs)
            break
    return ans, pos_ans

ans = -10**18
route_g, point_g = separation(routes, points)

for i in range(len(route_g)):
    tmp_point = point_g[i]
    total = sum(tmp_point)
    point_list = tmp_point + tmp_point + tmp_point
    if total < 0:
        print(0)
    else:
        circulations = k // len(tmp_point) 
        tmp_ans = total * circulations
        print(tmp_ans)

Submission status: Wrong Answer

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 = max(C)
for start in range(N):
    now = P[start]
    tmp = C[now]
    c = K-1
    k = 1
    kick = [tmp]
    step = None
    kick_tmp = None
    x = True
    if now == start:
        step = k
        kick_tmp = tmp
        x = False
    while c > 0 and k < N and x:
        now = P[now]
        tmp += C[now]
        ans = max(ans, tmp)
        c -= 1
        k += 1
        kick.append(tmp)
        if now == start:
            step = k
            kick_tmp = tmp
            break
    if step != None and K%step != 0:
        ans = max(ans, kick_tmp*(K//step)+max(kick[:K%step]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -10**10
#print(s)
for i in range(N):
    dp = [0 for _ in range(N+1)]
    res = 0
    num = i
    chk = [0 for _ in range(N)]
    f=0
    M= ans 
    inc = 0
    while(1):
        num = P[num]-1
        if chk[num]==1:
            break
        chk[num]=1
        inc+=1

        res += C[num]
        #print(i,res)
        #print(chk)
        dp[inc]=max(dp[inc-1],res)
        M = max(M,res)
    if K > N:
        if res>0:
    
            cnt=K//inc
            mod = K%inc
            val = res*cnt
            val = val + dp[mod]
            ans = max(val,ans)
        else:
            ans = max(ans,M)
    else:
        ans = max(ans,M)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
points=[[] for i in range(N)]
for i in range(N):
  tmpl=[0]
  loc=i
  for j in range(1,N+1):
    tmpl+=[tmpl[j-1]+C[loc]]
    loc=P[loc]-1
  points[i]=tmpl
repeat=K//N
left=K%N
maxlist=[]
for i in range(N):
  if left==0:
    leftsum=0
  else:
    leftsum=max(points[i][1:left+1])
  if points[i][N]<0:
    maxlist+=[max(points[i][1:max(N,left)+1])]
  else:
    tmp=repeat*points[i][N]+leftsum
    maxlist+=[tmp]
print(max(maxlist))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
points=[[] for i in range(N)]
for i in range(N):
  tmpl=[0]
  loc=i
  for j in range(1,N+1):
    tmpl+=[tmpl[j-1]+C[loc]]
    loc=P[loc]-1
  points[i]=tmpl
repeat=K//N
left=K%N
maxlist=[]
for i in range(N):
  if left==0:
    leftsum=0
  else:
    leftsum=max(points[i][1:left+1])
  if points[i][N]<0:
    maxlist+=[max(points[i][1:N+1])]
  else:
    tmp=repeat*points[i][N]+leftsum
    maxlist+=[tmp]
print(max(maxlist))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
s = sum(C)
ans = -10**10
#print(s)
for i in range(N):
    dp = [0 for _ in range(N+1)]
    res = 0
    num = i
    chk = [0 for _ in range(N)]
    f=0
    M= -10**10
    inc = 0
    while(1):
        num = P[num]-1
        if chk[num]==1:
            break
        chk[num]=1
        inc+=1

        res += C[num]
        #print(i,res)
        #print(chk)
        dp[inc]=max(dp[inc-1],res)
        M = max(M,res)
    if K > N:
        if res>0:
            #print(res)
            #print(i)
            #print(dp)
            cnt=K//inc
            mod = K%inc
            val = res*cnt
            val = val + dp[mod]
            ans = max(val,ans)
        else:
            ans = max(ans,M)
    else:
        ans = max(ans,M)

print(ans)

Submission status: Wrong Answer

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

LLONG_MIN = -9223372036854775807


# 一つのループの中で最大値を求める
def max_in_loop(loop, K):
    loop_sum = sum(loop)
    max_val = max(loop)

    # 繰り返し部分が正の場合、 最大回数繰り返したほうが大きい
    if loop_sum > 0:
        repeat_part = (K // len(loop)) * loop_sum
    else:
        repeat_part = 0

    # ループ部分が存在しえる場合、繰り返さない部分の
    # 長さの最短値は 0 それいがいだと 1
    if len(loop) >= K and loop_sum > 0:
        K0 = 0
    else:
        K0 = 1

    # 繰り返さない部分の長さ
    K_ONECE = K % len(loop)

    # インデックスを楽にするための loop を2つ連結
    loop2 = loop + loop

    # 繰り返さない部分と繰り返す部分の合計より
    # 最大値を求める
    for k in range(K0, K_ONECE + 1):
        for i in range(len(loop)):
            val = sum(loop2[i : i + k]) + repeat_part
            if val > max_val:
                max_val = val
    return max_val


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):
    # 簡単のためインデックスを 0 からにする
    # (使用済みは -1 を入れる)
    P = [i - 1 for i in P]
    answer = LLONG_MIN
    for i0 in range(N):
        if P[i0] == -1:
            continue
        loop = []
        i = i0
        while P[i] != -1:
            loop.append(C[i])
            i_next = P[i]
            P[i] = -1
            i = i_next
        val = max_in_loop(loop, K)
        if answer < val:
            answer = val

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, K, P, C)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
points=[[] for i in range(N)]
for i in range(N):
  tmpl=[0]
  loc=i
  for j in range(1,N+1):
    tmpl+=[tmpl[j-1]+C[loc]]
    loc=P[loc]-1
  points[i]=tmpl
repeat=K//N
left=K%N
maxlist=[]
for i in range(N):
  if points[i][N]<0:
    maxlist+=[max(points[i][1:left+2])]
  else:
    tmp=repeat*points[i][N]+max(points[i][1:left+2])
    maxlist+=[tmp]
print(max(maxlist))

Submission status: Wrong Answer

Solution code:
#D - Moving_piece
#TLE
N,K = map(int,input().split())
P =[]
C =[]
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ichi  = 0
score_max = -1000000010
score_full_max =  -1000000010
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = K
    while i != (P[ichi] -1):
        if step > 0:
            ichi = (P[ichi] -1)
            score += C[ichi]
            if score > score_max:
                score_max = score
            step -= 1
        else:
            break
    if step > 0:
        score += C[i]
        if score > 0 :
            loop = int((K) / (K -step +1))
            mod  = int((K) % (K -step +1))
            score_full_max = loop * score + score_max
        else:
            score_full_max = score_max
    else:
        score_full_max = score_max

# 出力
print(score_full_max)

Submission status: Wrong Answer

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

max_score = 0
for i in range(N):
  first = True
  score = 0
  step = 0
  path = {}
  cumulative_score = []
  current_p = i
  cycle_passed = False
  while step < K:
    # record current step
    cumulative_score.append(score)
    
    # check if cycle is found
    if (not cycle_passed) and (current_p in path.keys()):
      # found a cycle 
      # calculate score sum within the cycle
      # calculate steps with in the cycle
      cycle_start_step = path[current_p]
      cycle_steps = step - cycle_start_step
      cycle_sum = cumulative_score[step] - cumulative_score[cycle_start_step]
      if cycle_sum < 0:
        # negative cycle
        # finish 
        break
      else:
        #positive cycle
        remain_steps = K - step
        if remain_steps > cycle_steps:
          cycle_times = (K - step) // cycle_steps - 1
          step += (cycle_times * cycle_steps)
          score += (cycle_times * cycle_sum)
          cycle_passed = True
        else:
          cycle_passed = True    
        
    # record current step
    path[current_p] = step
    
    # go to next step
    next_p = p_list[current_p-1]
    score += c_list[next_p-1]
    if (first):
      max_score = score
      first = False
    else:
      max_score = max(max_score, score)
    
    current_p = next_p
    step += 1

print(max_score)

Submission status: Wrong Answer

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

max_score = 0
for i in range(N):
  first = True
  score = 0
  step = 0
  path = {}
  cumulative_score = []
  current_p = i
  cycle_passed = False
  while step < K:
    # record current step
    cumulative_score.append(score)
    
    # check if cycle is found
    if (not cycle_passed) and (current_p in path.keys()):
      # found a cycle 
      # calculate score sum within the cycle
      # calculate steps with in the cycle
      cycle_start_step = path[current_p]
      cycle_steps = step - cycle_start_step
      cycle_sum = cumulative_score[step] - cumulative_score[cycle_start_step]
      if cycle_sum < 0:
        # negative cycle
        # finish 
        break
      else:
        #positive cycle
        remain_steps = K - step
        if remain_steps > cycle_steps:
          cycle_times = (K - step) // cycle_steps - 1
          step += (cycle_times * cycle_steps)
          score += (cycle_times * cycle_sum)
          cycle_passed = True
        else:
          cycle_passed = True    
        
    # record current step
    path[current_p] = step
    
    # go to next step
    next_p = p_list[current_p-1]
    score += c_list[next_p-1]
    if (first):
      max_score = score
    else:
      max_score = max(max_score, score)
    
    current_p = next_p
    step += 1

print(max_score)

Submission status: Wrong Answer

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


cycle = {}
max_score = 0
for i in range(N):
  score = 0
  step = 0
  path = {}
  cumulative_score = []
  current_p = i
  cycle_passed = False
  while step < K:
    # record current step
    cumulative_score.append(score)
    
    # check if cycle is found
    if (not cycle_passed) and current_p in path.keys():
      # found a cycle 
      # calculate score sum within the cycle
      # calculate steps with in the cycle
      cycle_start_step = path[current_p]
      cycle_steps = step - cycle_start_step
      cycle_sum = cumulative_score[step] - cumulative_score[cycle_start_step]
      if cycle_sum < 0:
        # negative cycle
        # finish 
        break
      else:
        #positive cycle
        remain_steps = K - step
        if remain_steps > cycle_steps:
          cycle_times = (K - step) // cycle_steps - 1
          step += (cycle_times * cycle_steps)
          score += (cycle_times * cycle_sum)
          cycle_passed = True
        else:
          cycle_passed = True
       
        
        
    # record current step
    path[current_p] = step
    
    # go to next step
    next_p = p_list[current_p-1]
    score += c_list[next_p-1]
    max_score = max(max_score, score)
    
    current_p = next_p
    step += 1

print(max_score)

Submission status: Wrong Answer

Solution code:
#D - Moving_piece
#TLE
N,K = map(int,input().split())
P =[]
C =[]
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ichi  = 0
score_max      = -1000000010
score_full_max = -1000000010
score_output   = -1000000010
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = K
    loop = 0
    mod = 0
    score_list_max = 0
    score_list = []
    while step > 0:
        if i != (P[ichi] - 1):
            ichi = (P[ichi] - 1)
            score += C[ichi]
            score_list.append(score)
            if score > score_max:
                score_max = score
            step -= 1
        else:
            score += C[i]
            break
    if score < 0:
        score_output = score_max
    else:
        loop = int((K) / (K -step +1))

        mod  = int((K) % (K -step +1))
        score_list_max = max(score_list[0:mod+1])
        score_full_max = loop * score + score_list_max    
        if score_full_max > score_output :
            score_output = score_full_max            
    
# 出力
print(score_output)

Submission status: Wrong Answer

Solution code:
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())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
uf = UnionFind(N)
ans = -10**9
for i in range(N):
    uf.union(i,P[i]-1)
for group in uf.all_group_members().values():
    size = len(group)
    SUM = 0
    for i in group:
        SUM += C[i]
    if SUM < 0:
        SUM = 0
    for i in group:
        cur = i
        current_sum = 0
        remain = K
        for _ in range(size):
            cur = P[i]-1
            current_sum += C[cur]
            remain -= 1
            if remain < 0:
                break
            ans = max(ans,current_sum+SUM*(remain//size))
print(ans)

Submission status: Wrong Answer

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

tokuten = []
zan = p[:]
while len(zan) != 0:
    loop = []
    start = zan.pop()
    loop.append(c[start-1])
    next = p[start-1]
    zan.remove(next)
    while start != next:
        loop.append(c[next-1])
        next = p[next-1]
        if next in zan:
            zan.remove(next)
    tokuten.append(loop)


ans = -10e10
for loop in tokuten:
    tmp = 0
    le = len(loop)
    su = sum(loop)
    if le < k:
        if su > 0:
            tmp += (k//le)*su
            amari = k%le
            ma = -10e10
            lplp = loop + loop
            for i in range(1,amari+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            tmp += ma
            ans = max(ans,tmp)
        if su <= 0:
            ma = -10e10
            lplp = loop + loop + loop
            for i in range(1,2*le):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            ans = max(ans,ma)
    else:
        ma = -10e10
        lplp = loop + loop
        for i in range(1,k+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
        ans = max(ans,ma)
print(ans)

Submission status: Wrong Answer

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

tokuten = []
zan = p[:]
while len(zan) != 0:
    loop = []
    start = zan.pop()
    loop.append(c[start-1])
    next = p[start-1]
    zan.remove(next)
    while start != next:
        loop.append(c[next-1])
        next = p[next-1]
        if next in zan:
            zan.remove(next)
    tokuten.append(loop)


ans = -10e10
for loop in tokuten:
    tmp = 0
    le = len(loop)
    su = sum(loop)
    if le < k:
        if su > 0:
            tmp += (k//le)*su
            amari = k%le
            ma = -10e10
            lplp = loop + loop
            for i in range(1,amari+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            tmp += ma
            ans = max(ans,tmp)
        if su <= 0:
            ma = -10e10
            lplp = loop + loop
            for i in range(1,le+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            ans = max(ans,ma)
    else:
        ma = -10e10
        lplp = loop + loop
        for i in range(1,k+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
        ans = max(ans,ma)
print(ans)