[GO] [Python] ABC175D

Since Pi! = I and P1, P2, ..., PN are all different, it is a loop that always returns to the starting point no matter where you start. From N ≤ 5000, even if the loop path is found for all the starting points, the worst is O (N ^ 2), and it seems that it will be somehow in time. Therefore, consider it as the starting point s below. For each s, follow the steps below.

Step1 1st point → 2nd point → ・・・ → For the loop of s (last point), find the cumulative sum S of points. Step2 The maximum value of the score is calculated by classifying the cases according to the magnitude of K and len (S). The cases are as follows.

Step2-Case A: When K ≤ len (S):

Since the loop is not done for one week, the maximum value of S at the reachable point is the answer.

Step2-Case B: When K> len (S):

When S [-1] ≤ 0, there is no merit for more than one week, so the maximum value up to one week, that is, the maximum value of S is the answer. When S [-1]> 0, you want to turn as much as you can, but in fact, the score may be higher if you turn one lap less, so calculate and compare the scores in both cases.

Reference: [Python] ABC175 Explanation

`Sample code`


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

ans = -float('inf')
for s in range(N):
    ### Step1
    S = []  #Cumulative sum list in loop S.However,The first term is not 0 but the score after the first move.
    #1st move
    i = P[s] - 1
    S.append(C[i])
    #Second and subsequent moves.Repeat until you return to the starting point.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2:Separate cases according to the length of K and S,Find the maximum score.
    #If you can move less than one lap:
    if K <= len(S):
        score = max(S[:K])
    #It can exceed one lap,When the score decreases when one lap of the loop:
    elif S[-1] <= 0:
        score = max(S)
    #Can exceed one week,And if the score increases every week in the loop:
    else:
        #Loop(K // len(S) - 1)When turning:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        #Loop(K // len(S))When turning:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        #The larger score1 and score2 is the maximum score in this case.
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)