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:
#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_output = -1000000010
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = 0
    score_max_list = [0]
    score_max = -1000000010
    score_full_max =  -1000000010
    for j in range(N):
        if i != (P[ichi] -1):
            ichi = (P[ichi] -1)
            score += C[ichi]
            if score > score_max:
                score_max = score
            score_max_list.append(score_max)
        else:
            step = j
            score += C[i]
            break
    if score > 0 :
        loop = int((K) / (step +1))
        mod  = int((K) % (step +1))
        score_full_max = loop * score + score_max_list[mod]
    else:
        score_full_max = score_max
    if score_full_max > score_output:
        score_output = score_full_max
# 出力
print(score_output)

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))
    C = list(map(int, readline().split()))
    P = [i-1 for i in P]
    Position_list=[P]
    Score_list=[[0 for i in range(N)]]
 
    for j in range(K):
        Updated_Position=[]
        Updated_Score=[]
        Current_Position=Position_list[j]
        Current_Score=Score_list[j]
        for i in range(N):
            Updated_Position.append(Current_Position[P[i]])
            Updated_Score.append(Current_Score[i]+C[Current_Position[i]])
        Position_list.append(Updated_Position)
        Score_list.append(Updated_Score)
    print(max(max(i) for i in Score_list))
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [0] * N
    def f(i, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        cur = i
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt:
                if ret_ < f_score[cur]:
                    break
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] = ret_
            cur = P[cur] - 1
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [0] * N
    def f(i, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        cur = i
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt and ret_ >= f_score[cur]:
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] = ret_
            ret_ += C[cur]
            ret = max(ret, ret_)
            cur = P[cur] - 1
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [0] * N
    def f(i, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        cur = i
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt:
                if ret_ < f_score[cur]:
                    break
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] = ret_
            ret_ += C[cur]
            ret = max(ret, ret_)
            cur = P[cur] - 1
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase    

# %% input phase
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# %% process phase
for i in range(n):
    p[i] -= 1

ans = -1e14
# スタートは全部確認
for si in range(n):
    np = si
    ts = 0
    cnt = 0
    ms = -1e14
    mscnt = 0
    while 1:
        np = p[np]
        ts += c[np]
        cnt += 1
        if ms < ts and cnt <= k:
            ms = ts
            mscnt = cnt
        if np == si: break
    
    if ts > 0:
        e = (k - mscnt)//cnt
        sc1 = ts*e
    else:
        sc1 = 0
    ans = max(ans, sc1 + ms)

# %%output phase
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [0] * N
    def f(i, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        cur = i
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt:
                if ret_ < f_score[cur]:
                    break
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] += ret_
            ret_ += C[cur]
            ret = max(ret, ret_)
            cur = P[cur] - 1
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [0] * N
    def f(i, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        cur = i
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt:
                if ret_ <= f_score[cur]:
                    break
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] += ret_
            ret_ += C[cur]
            ret = max(ret, ret_)
            cur = P[cur] - 1
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

r = C[0]
for start_index in range(N):
    temp_sum = C[start_index]
    if temp_sum < 0:
        continue
    index = start_index
    for j in range(K-1):
        index = P[index]-1
        temp_sum += C[index]
        r = temp_sum if temp_sum > r else r

print(r)

Submission status: Wrong Answer

Solution code:
import math

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

r = C[0]
for start_index in range(N):
    temp_sum = C[start_index]
    if temp_sum < 0:
        continue
    index = start_index
    for j in range(K):
        index = P[index]-1
        temp_sum += C[index]
        r = temp_sum if temp_sum > r else r

print(r)

Submission status: Wrong Answer

Solution code:
import math

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

r = C[0]
for start_index in range(N):
    temp_sum = C[start_index]
    index = start_index
    for j in range(K):
        index = P[index]-1
        temp_sum += C[index]
        r = temp_sum if temp_sum > r else r

print(r)

Submission status: Wrong Answer

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


def make_group_shim0(x, check):
    lis = []
    while not C[x - 1] in lis:
        lis.append(C[x - 1])
        check.append(P[x - 1] - 1)
        x = P[x - 1]
    return lis


Big_lis = []
check = []
i = 1
while i < N:
    if i - 1 not in check:
        Big_lis.append(make_group_shim0(i, check))
    i += 1

LIST_no_kazu = len(Big_lis)
ans1 = -1000000000
ans2 = -1000000000
ans3 = -1000000000
for i in range(LIST_no_kazu):
    N = len(Big_lis[i])

    k_hasuu = K % N
    k_kaisu = K // N
    summ = max(0, sum(Big_lis[i]))

    dp = [[0 for i in range(N)] for j in range(K + 1)]

    for j in range(N):
        dp[0][j] = Big_lis[i][j]
    ans1 = max(dp[0])

    for k in range(1, k_hasuu):
        for j in range(N):
            dp[k][j] = dp[k - 1][(j - 1) % N] + Big_lis[i][j]
        ans1 = max(ans1, max(dp[k]))
    ans2 = max(ans2, ans1)
    ans3 = max(ans3, ans2 + summ * k_kaisu)

print(ans3)

Submission status: Wrong Answer

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


def make_group_shim0(x, check):
    lis = []
    while not C[x - 1] in lis:
        lis.append(C[x - 1])
        check.append(P[x - 1] - 1)
        x = P[x - 1]
    return lis


Big_lis = []
check = []
i = 1
while i < N:
    if i - 1 not in check:
        Big_lis.append(make_group_shim0(i, check))
    i += 1
print(Big_lis)

LIST_no_kazu = len(Big_lis)
ans1 = -100000000
ans2 = -10000000000
for i in range(LIST_no_kazu):
    N = len(Big_lis[i])

    k_hasuu = K % N
    k_kaisu = K // N
    summ = 0

    for j in Big_lis[i]:
        summ += j

    dp = [[0 for i in range(N)] for j in range(K + 1)]

    for j in range(N):
        dp[0][j] = Big_lis[i][j]
    ans1 = max(dp[0])

    for k in range(1, K):# k_hasuuにする
        for j in range(N):
            dp[k][j] = dp[k-1][(j-1)%N] + Big_lis[i][j]
        ans1 = max(ans1, max(dp[k]))
    ans2 = max(ans2, ans1)
print(ans2)

Submission status: Wrong Answer

Solution code:
Neg_INF=-10**10

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

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

ans=0
if K>N:
    point_sum=sum(C)
    if point_sum>0:
        ans=point_sum*(K//N)
        K=K%N
    else:
        K=N

dp=[[0 for i in range(K+1)] for i in range(N)]

point=Neg_INF
for i in range(1,K+1):
    for j in range(N):
        dp[j][i]=dp[P[j]-1][i-1]+C[P[j]-1]
        if point<dp[j][i]:
            point=dp[j][i]

ans+=point
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    loop = [0] * N
    loopsum = [0] * N
    for i in range(N):
        if loop[i] > 0:
            continue
        cnt = 0
        cur = i
        visited = set()
        score = 0
        while cur not in visited:
            visited.add(cur)
            cnt += 1
            cur = P[cur]
            score += C[cur]
        for v in visited:
            loop[v] = cnt
            loopsum[v] = score
    ans = max(C)
    for i in range(N):
        if loopsum[i] >= 0 and loop[i] <= K:
            score = loopsum[i] * (K // loop[i] - 1)
            limit = K % loop[i] + loop[i]
        else:
            score = 0
            limit = loop[i]
        cur = i
        for _ in range(limit):
            cur = P[cur]
            score += C[cur]
            ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
Neg_INF=-10**10

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

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

ans=0
if K>N:
    point_sum=sum(C)
    if point_sum>0:
        ans=point_sum*(K//N)
        K=K%N
    else:
        K=N

dp=[[ans for i in range(K+1)] for i in range(N)]

for i in range(1,K+1):
    for j in range(N):
        dp[j][i]=dp[P[j]-1][i-1]+C[P[j]-1]
        if ans<dp[j][i]:
            ans=dp[j][i]

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    loop = [0] * N
    loopsum = [0] * N
    for i in range(N):
        if loop[i] > 0:
            continue
        cnt = 0
        cur = i
        visited = set()
        score = 0
        while cur not in visited:
            visited.add(cur)
            cnt += 1
            cur = P[cur]
            score += C[cur]
        for v in visited:
            loop[v] = cnt
            loopsum[v] = score
    ans = max(C)
    for i in range(N):
        if loopsum[i] >= 0 and loop[i] <= K:
            score = loopsum[i] * (K // loop[i] - 1)
            limit = K % loop[i] + loop[i]
            ans = max(ans, score)
        else:
            score = 0
            limit = loop[i]
        cur = i
        for _ in range(limit):
            cur = P[cur]
            score += C[cur]
            ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    loop = [0] * N
    loopsum = [0] * N
    for i in range(N):
        if loop[i] > 0:
            continue
        cnt = 0
        cur = i
        visited = set()
        score = 0
        while cur not in visited:
            visited.add(cur)
            cnt += 1
            cur = P[cur]
            score += C[cur]
        for v in visited:
            loop[v] = cnt
            loopsum[v] = score
    ans = max(C)
    for i in range(N):
        if loopsum[i] > 0 or loop[i] >= K:
            score = loopsum[i] * (K // loop[i])
            limit = K % loop[i]
            ans = max(ans, score)
        else:
            score = 0
            limit = loop[i]
        cur = i
        for _ in range(limit):
            cur = P[cur]
            score += C[cur]
            ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    loop = [0] * N
    loopsum = [0] * N
    for i in range(N):
        if loop[i] > 0:
            continue
        cnt = 0
        cur = i
        visited = set()
        score = 0
        while cur not in visited:
            visited.add(cur)
            cnt += 1
            cur = P[cur]
            score += C[cur]
        for v in visited:
            loop[v] = cnt
            loopsum[v] = score
    ans = min(C)
    for i in range(N):
        if loopsum[i] > 0:
            score = loopsum[i] * (K // loop[i])
            limit = K % loop[i]
            ans = max(ans, score)
        else:
            score = 0
            limit = loop[i]
        cur = i
        for _ in range(limit):
            cur = P[cur]
            score += C[cur]
            ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    ans = min(C)
    for i in range(N):
        cnt = 0
        cur = i
        visited = set()
        score = 0
        while cnt < K and cur not in visited:
            visited.add(cur)
            cnt += 1
            cur = P[cur]
            score += C[cur]
            ans = max(ans, score)
        if cnt < K and score > 0:
            score = score * (K // cnt)
            cnt = (K // cnt) * cnt
            ans = max(ans, score)
            while cnt < K:
                cnt += 1
                cur = P[cur]
                score += C[cur]
                ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
    snp=P[i]
    r=C[snp]
    L=[r]
    c=0
    np=P[snp]
    while True:
        if c==k-1:
            ANS=max(max(L),ANS)
            break
        if np==snp:
            y=k%(c+1)
            m=k//(c+1)
            if y==0:
                ANS=max(max(L),max(L)+(m-1)*L[-1],ANS)
                break
            else:
                #print(m,y)
                #print(L)
                ANS=max(max(L[:y]),max(max(L[:y]),0)+m*L[-1],ANS)
                break
        r+=C[np]
        L.append(r)
        np=P[np]
        c+=1
print(ANS)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
    #print(i)
    snp=P[i]
    #print(snp)
    r=C[snp]
    L=[r]
    c=0
    np=P[snp]
    while True:
        if c==k-1:
            ANS=max(max(L),ANS)
            #print(L)
            break
        if np==snp:
            y=k%(c+1)
            m=k//(c+1)
            if y==0:
                #print(m)
                ANS=max(max(L),max(L)+m*L[-1],ANS)
                #print(L)
                break
            else:
                ANS=max(max(L[:y]),max(L[:y])+m*L[-1],ANS)
                #print(L)
                #print(L[:y])
                break
        r+=C[np]
        L.append(r)
        np=P[np]
        c+=1
print(ANS)

Submission status: Wrong Answer

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

cnt = [1] * (N+1)
retsu = []
for i in range(1,N+1):
    idx = i
    r = []
    for _ in range(N):
        if cnt[idx] == 0:
            break
        r.append(C[P[idx]])
        cnt[idx] = 0
        idx = P[idx]
    if r:
        retsu.append(r)

ans = -1 * (10 ** 10)
for z in retsu:
    K = KK
    s = sum(z)
    l = len(z)
    if s <= 0 or K <= l:
        plus = 0
    else:
        plus = s * (K // l)
        if K % l == 0:
            plus -= s
    K %= l
    if K == 0:
        K = l
    
    moto = z + z
    point = [[0] * l for _ in range(l+K-1)]
    kari = -1 * (10 ** 10)
    for i in range(l+K-1):
        for j in range(l):
            if i == j:
                point[i][j] = moto[i]
            elif i - j >= K or i < j:
                continue
            else:
                point[i][j] = moto[i] + point[i-1][j]
            kari = max(kari, point[i][j])
    ans = max(ans, plus + kari)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
	snp=P[i]
	r=C[snp]
	L=[r]
	c=1
	np=P[snp]
	while True:
		r+=C[np]
		L.append(r)
		if c==k-1:
			ANS=max(max(L),ANS)
			break
		if np==snp:
			y=k%c
			m=k//c
			if y==0:
				ANS=max(max(L),max(L)+m*sum(L),ANS)
			else:
				ANS=max(max(L[:y]),max(L[:y])+m*sum(L),ANS)
			break
		np=P[np]
		c+=1
print(ANS)

Submission status: Wrong Answer

Solution code:
# WTF why TLE and WA?

import sys
si = sys.stdin.readline


def main():
    [n, k] = [int(e) for e in si().split()]
    pl = [int(e) for e in si().split()]
    cl = [int(e) for e in si().split()]
    val = [0 for _ in range(n)]
    cycles = dict()

    M = -10**9*5000-1

    for i in range(n):
        vis = [-1 for _ in range(n)]
        flag, ith, idx, m = False, 0, i, 0
        while ith < k:
            idx = pl[idx]-1
            if not flag:
                if idx in cycles:
                    flag = True
                    rest = (k-ith)//cycles[idx][1]
                    if rest:
                        m += cycles[idx][0]*rest
                        M = max(M, m)
                        ith += cycles[idx][1]*rest
                else:
                    if vis[idx] != -1:
                        flag = True
                        cv = m-(val[idx]-cl[idx])
                        cn = ith-vis[idx]

                        start = idx
                        while True:
                            cycles[start] = (cv, cn)
                            start = pl[start]-1
                            if start == idx:
                                break

                        rest = (k-ith)//cn
                        if rest:
                            m += cv*rest
                            M = max(M, m)
                            ith += cn*rest
                    else:
                        vis[idx] = ith
                        val[idx] = m+cl[idx]

            if ith < k:
                ith += 1
                m += cl[idx]
                M = max(M, m)
    print(M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# WTF why TLE and WA?

import sys
si = sys.stdin.readline


def main():
    [n, k] = [int(e) for e in si().split()]
    pl = [int(e) for e in si().split()]
    cl = [int(e) for e in si().split()]
    val = [0]*n
    cycles = dict()

    M = -10**9*5000-1

    for i in range(n):
        vis = [-1 for _ in range(n)]
        flag, ith, idx, m = False, 0, i, 0
        while ith < k:
            idx = pl[idx]-1
            if not flag:
                if idx in cycles:
                    flag = True
                    rest = (k-ith)//cycles[idx][1]
                    if rest:
                        m += cycles[idx][0]*rest
                        M = max(M, m)
                        ith += cycles[idx][1]*rest
                else:
                    if vis[idx] != -1:
                        flag = True
                        cv = m-(val[idx]-cl[idx])
                        cn = ith-vis[idx]

                        start = idx
                        while True:
                            cycles[start] = (cv, cn)
                            start = pl[start]-1
                            if start == idx:
                                break

                        rest = (k-ith)//cn
                        if rest:
                            m += cv*rest
                            M = max(M, m)
                            ith += cn*rest
                    else:
                        vis[idx] = ith
                        val[idx] = m+cl[idx]

            if ith < k:
                ith += 1
                m += cl[idx]
                M = max(M, m)
    print(M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = [1] * (N+1)
retsu = []
for i in range(1,N+1):
    idx = i
    r = []
    for _ in range(N):
        if cnt[idx] == 0:
            break
        r.append(C[P[idx]])
        cnt[idx] = 0
        idx = P[idx]
    if r:
        retsu.append(r)

ans = -1 * (10 ** 9) - 1
for z in retsu:
    K = KK
    s = sum(z)
    l = len(z)
    if s <= 0 or K <= l:
        plus = 0
    else:
        plus = s * (K // l)
        if K % l == 0:
            plus -= s
    K %= l
    if K == 0:
        K = l
    
    moto = z + z
    point = [[0] * l for _ in range(l+K-1)]
    kari = -1 * (10 ** 9) - 1
    for i in range(l+K-1):
        for j in range(l):
            if i == j:
                point[i][j] = moto[i]
            elif i - j >= K or i < j:
                continue
            else:
                point[i][j] = moto[i] + point[i-1][j]
            kari = max(kari, point[i][j])
    ans = max(ans, plus + kari)
print(ans)

Submission status: Wrong Answer

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

cnt = [1] * (N+1)
retsu = []
for i in range(1,N+1):
    idx = i
    r = []
    for _ in range(N):
        if cnt[idx] == 0:
            break
        r.append(C[P[idx]])
        cnt[idx] = 0
        idx = P[idx]
    if r:
        retsu.append(r)

ans = -1 * (10 ** 9) - 1
for i in retsu:
    s = sum(i)
    l = len(i)
    plus = 0
    if s <= 0 or K <= l:
        pass
    else:
        plus += s * (K // l)
        if K % l == 0:
            plus -= s
    K %= l
    if K == 0:
        K = l
    
    moto = i + i
    point = [[0] * N for _ in range(l+K-1)]
    kari = -1 * (10 ** 9) - 1
    for i in range(l+K-1):
        for j in range(N):
            if i == j:
                point[i][j] = moto[i]
            elif i - j >= K or i < j:
                continue
            else:
                point[i][j] = moto[i] + point[i-1][j]
            kari = max(kari, point[i][j])
    ans = max(ans, plus + kari)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

visited = [0] * n

A = []
for i in range(1, n + 1):
    if visited[i - 1] == 1:
        continue
    s = i
    X = []
    while True:
        s = P[s - 1]
        X.append(C[s - 1])
        visited[s - 1] = 1
        if s == i:
            break
    A.append(X)

ANS = []

for a in A:
    b = [0] + a + a
    d = list(accumulate(b))
    if k % len(a) == 0:
        x = len(a)
        y = k // len(a) - 1
    else:
        x = k % len(a)
        y = k // len(a)
    cnt = -(10 ** 18)

    for i in range(1, x + 1):
        for j in range(len(a) + 1):
            cnt = max(d[i + j] - d[j], cnt)

    if sum(a) < 0:
        ANS.append(cnt)
    else:
        ANS.append(cnt + sum(a) * y)

print(max(ANS))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

visited = [0] * n

A = []
for i in range(1, n + 1):
    if visited[i - 1] == 1:
        continue
    s = i
    X = []
    while True:
        s = P[s - 1]
        X.append(C[s - 1])
        visited[s - 1] = 1
        if s == i:
            break
    A.append(X)

ANS=[]

for a in A:
    b=[0]+a+a
    d=list(accumulate(b))
    if k%len(a)==0:
        x=len(a)
    else:
        x=k%len(a)
    y=k//len(a)
    cnt=-(10**18)

    for i in range(1,x+1):
        for j in range(len(a)+1):
            cnt=max(d[i+j]-d[j],cnt)

    if sum(a)<0:
        ANS.append(cnt)
    else:
        ANS.append(cnt+sum(a)*y)

print(max(ANS))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=[int(i)-1for i in input().split()]
c=list(map(int,input().split()))
ans=-10**9
for i in range(n):
    start=i
    cycle=[0]
    for _ in range(n):
        i=p[i]
        cycle+=[cycle[-1]+c[i]]
        if i==start:break
    S,L=cycle[-1],len(cycle)-1
    if S<=0:ans=max(ans,max(cycle[1:k+1]))
    else:
        if k>L:ans=max(ans,(k//L-1)*S+max(max(cycle),max(cycle[:k%L+1])+S)) 
        # else:ans=max(ans,cycle[:k+1])
print(ans)

Submission status: Wrong Answer

Solution code:
# I know this is WA
N, K = map(int, input().split())
P = [int(s) - 1 for s in input().split()]
C = list(map(int, input().split()))

gs = []
done = set()
for i in range(N):
    if i in done:
        continue
    path = {i}
    cur = P[i]
    while cur not in path:
        path.add(cur)
        cur = P[cur]
    gs.append(path)
    done |= path

ans = -10 ** 10
for g in gs:
    gscore = sum(C[i] for i in g)
    for i in g:
        n = 1
        p = C[i]
        ans = max(ans, p, p + max(0, gscore) * (K - n) // len(g))
        cur = P[i]
        while cur != i:
            n += 1
            p += C[cur]
            ans = max(ans, p, p + max(0, gscore) * (K - n) // len(g))
            cur = P[cur]
print(ans)