Problem p02585 (python)

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

seen = []
roots = []
candidates = []

for i in range(N):
    if i+1 in seen:
        continue
    root = [i+1]
    seen.append(i+1)
    to = P[i]
    while(root[0] != to):
        root.append(to)
        seen.append(to)
        to = P[to-1]
    roots.append(root)
for root in roots:
    length = len(root)
    eachMoveBests = [None] * length
    for i in range(length):
        score = 0
        to = P[root[i]-1]
        for j in range(len(root)):
            score += C[to-1]
            to = P[to-1]
            if eachMoveBests[j] == None or score > eachMoveBests[j]:
                eachMoveBests[j] = score
    # 周回スコア
    aroundScore = eachMoveBests[len(eachMoveBests)-1]
    if length < K and aroundScore > 0:
        for i in range(len(eachMoveBests)):
            if K-i-1 % length == 0:
                candidates.append(aroundScore * ((K-i-1) // length))
            else:
                candidates.append(aroundScore * ((K-i-1) // length) + eachMoveBests[i])
    else:
        candidates.append(max(eachMoveBests[:K]))

print(max(candidates))

Buggy submission (verdict: Runtime Error):
R, C, K = map(int, input().split())
L = 4
items = [[0 for c in range(C)] for r in range(R)]
for k in range(K):
    r, c, v = map(int, input().split())
    items[r-1][c-1] = v
dp = [[[0 for limit in range(L)] for c in range(C)] for r in range(R)]
for r in range(R):
    for c in range(C):
        upper = 0 if r == 0 else max(dp[r-1][c])
        left = [0]*L if c == 0 else dp[r][c-1]
        item = items[r][c]
        dp[r][c][0] = max(upper, left[0])
        dp[r][c][1] = max(upper+item, left[1])
        dp[r][c][2] = max(left[1] + item, left[2])
        dp[r][c][3] = max(left[2] + item, left[3])
print(max(dp[R-1][C-1]))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

seen = []
roots = []
candidates = []

for i in range(N):
    if i+1 in seen:
        continue
    root = [i+1]
    seen.append(i+1)
    to = P[i]
    while(root[0] != to):
        root.append(to)
        seen.append(to)
        to = P[to-1]
    roots.append(root)
for root in roots:
    eachMoveBests = [None] * (len(root))
    for i in range(len(root)):
        score = 0
        to = P[root[i]-1]
        for j in range(len(root)):
            score += C[to-1]
            to = P[to-1]
            if eachMoveBests[j] == None or score > eachMoveBests[j]:
                eachMoveBests[j] = score
    aroundTimes = K // len(root)
    surplus = K % len(root)
    sumRoot = 0
    for r in root:
        sumRoot += C[r-1]
    best = max(eachMoveBests)
    bestMoveTimes = eachMoveBests.index(best) + 1
    if surplus == 0:
        candidates.append(max(best,aroundTimes*sumRoot))
    elif bestMoveTimes <= surplus:
        candidates.append(max(best,aroundTimes*sumRoot+eachMoveBests[surplus-1]))
    else:
        candidates.append(max(best, aroundTimes*sumRoot+max(eachMoveBests[:surplus-1]), (aroundTimes-1)*sumRoot+best))
print(max(candidates))
# print(roots)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

seen = []
roots = []
candidates = []

for i in range(N):
    if i+1 in seen:
        continue
    root = [i+1]
    seen.append(i+1)
    to = P[i]
    while(root[0] != to):
        root.append(to)
        seen.append(to)
        to = P[to-1]
    roots.append(root)
for root in roots:
    eachMoveBests = [None] * (len(root))
    for i in range(len(root)):
        score = 0
        to = P[root[i]-1]
        for j in range(len(root)):
            score += C[to-1]
            to = P[to-1]
            if eachMoveBests[j] == None or score > eachMoveBests[j]:
                eachMoveBests[j] = score
    aroundTimes = K // len(root)
    surplus = K % len(root)
    sumRoot = 0
    for r in root:
        sumRoot += C[r-1]
    best = max(eachMoveBests)
    bestMoveTimes = eachMoveBests.index(best) + 1
    if surplus == 0:
        candidates.append(max(best,aroundTimes*sumRoot))
    elif bestMoveTimes <= surplus:
        candidates.append(max(best,aroundTimes*sumRoot+eachMoveBests[surplus-1]))
    else:
        candidates.append(max(best, aroundTimes*sumRoot+max(eachMoveBests[:surplus-1]), (aroundTimes-1)*sumRoot+best))
print(max(candidates))
# print(roots)






# # 各移動回数におけるベストなスコアを記録
# bests = [None] * N
# for i in range(N):
#     score = 0
#     to = P[i] - 1
#     for j in range(N):
#         score += C[to]
#         to = P[to] - 1
#         if bests[j] == None or score > bests[j]:
#             bests[j] = score
# print(bests)



# # if K <= N:
# #     best = None
# #     for i in range(N):
# #         score = 0
# #         to = P[i] - 1
# #         for j in range(K):
# #             score += C[to]
# #             to = P[to] - 1
# #             if best == None or score > best:
# #                 best = score
# #     print(best)
# # else:
# #     # 各移動回数におけるベストを記録しておく
# #     best = None
# #     bestMoveTime = None
# #     innerBests = [None] * N
# #     for i in range(N):
# #         score = 0
# #         to = P[i] - 1
# #         for j in range(N-1):
# #             score += C[to]
# #             to = P[to] - 1
# #             if best == None or score > best:
# #                 best = score
# #                 bestMoveTime = j+1
# #             if innerBests[j] == None or score > innerBests[j]:
# #                 innerBests[j] = score

# #     aroundTimes = K // N
# #     sumC = sum(C)
 
# #     if K % N >= bestMoveTime:
# #         print(K%N)
# #         print(bestMoveTime)
# #         print(max(best, aroundTimes*sumC+best))
# #     else:
# #         print(max(best, (aroundTimes-1)*sumC+best+max(innerBests[:N-bestMoveTime+1]), aroundTimes*sumC+max(innerBests[:K%N])))

# #         # print(max(best, aroundTimes*sumC+max(innerBests[:K % N]),(aroundTimes-1)*sumC+best))
    








# #     # noAroundBest = None
# #     # noAroundBestTimes = None
# #     # for i in range(N):
# #     #     score = 0
# #     #     to = P[i] - 1
# #     #     for j in range(N-1):
# #     #         score += C[to]
# #     #         to = P[to] - 1
# #     #         if noAroundBest == None or score > noAroundBest:
# #     #             noAroundBest = score
# #     #             noAroundBestTimes = j+1

# #     # aroundTimes = K // N
# #     # times = K % N
# #     # best = None
# #     # for i in range(N):
# #     #     score = 0
# #     #     to = P[i] - 1
# #     #     for j in range(times):
# #     #         score += C[to]
# #     #         to = P[to] - 1
# #     #         if best == None or score > best:
# #     #             best = score
# #     # sumC = sum(C)
# #     # print(aroundTimes)
# #     # print(sumC)
# #     # print(aroundTimes*sumC+)
# #     # # print(noAroundBestTimes)
# #     # # print(noAroundBest)
# #     # # print(aroundTimes)
# #     # # print(sumC)
# #     # if noAroundBestTimes <= times:
# #     #     print(max(noAroundBest, sumC*aroundTimes+noAroundBestTimes))
# #     # else:
# #     #     print(max(noAroundBest, sumC*aroundTimes+best, sumC*(aroundTimes-1)+noAroundBestTimes))