Problem p02585 (python)

Fixed submission:
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 = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    t = 0
    for i in range(l):
        t += score[i]
        if i + 1 > k:
            break
        now = t
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
        ans = max(ans, now)
print(ans)

Buggy submission (verdict: Runtime Error):

def my_solve(n, k, p, c):

    p = [0] + p
    c = [0] + c
    score = [[0] * (n + 1) for _ in range(n + 1)]
    # score[i][j]: iからstartしてj回移動した時のスコア
    l_cycle = [0] * (n + 1)
    for i in range(1, n + 1):
        start = i
        move_cnt = 0
        nxt = i
        while move_cnt < n:
            nxt = p[nxt]
            score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
            move_cnt += 1
            if nxt == start:
                l_cycle[start] = move_cnt
                break
    # for i in range(1, n + 1):
    #     print(score[i])
    # print('l_cycle', l_cycle)
    ans = -float('inf')
    for s in range(1, n + 1):
        if k <= l_cycle[s]:
            # サイクルを回らないので
            temp = max(score[s][1:k + 1])
            ans = max(ans, temp)
            continue
        # 以降は一周以上出来る時

        # 一周以下でやめる場合を探索
        temp = max(score[s][1:l_cycle[s] + 1])
        ans = max(ans, temp)
        # if score[s][l_cycle[s]] <= 0:
        #     # 周回する意味がない
        #     continue
        sk = k // l_cycle[s]  # 何周出来るか
        remk = k % l_cycle[s]
        temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
        if remk != 0:
            temp += max(score[s][1:remk + 1])
        ans = max(ans, temp)
    return ans


def ac_solve(n, k, p, c):
    for i in range(n):
        p[i] -= 1
    ans = -float('inf')
    for st in range(n):
        x = st
        score = []
        tot = 0
        while True:
            x = p[x]
            score.append(c[x])
            tot += c[x]
            if x == st:
                break
        l = len(score)
        now = 0
        t = 0
        for i in range(l):
            t += score[i]
            if i + 1 > k:
                break
            now = t
            if tot > 0:
                cycle_num = (k - (i + 1)) // l
                now += tot * cycle_num
            ans = max(ans, now)
    return ans


def main():
    while True:
        n = random.randint(2, 5)
        k = random.randint(1, 10)
        p = list(range(1, n + 1))
        random.shuffle(p)
        c = [random.randint(-100, 100) for _ in range(n)]
        c2 = c[:]
        ans1 = my_solve(n, k, p, c)
        org_p = p[:]
        ans2 = ac_solve(n, k, org_p, c2)
        # assert org_p == p, f'{org_p}:{p}'
        if ans1 == ans2:
            continue
            print('ok')
        else:
            print('ng')
            print(n, k)
            print(f'my_ans:{ans1}')
            print(f'ac_ans:{ans2}')


def main2():
    n = int(input())
    k = int(input())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    print(my_solve(n, k, p, c))


if __name__ == '__main__':
    main2()

Buggy submission (verdict: Runtime Error):
import random


def my_solve(n, k, p, c):

    p = [0] + p
    c = [0] + c
    score = [[0] * (n + 1) for _ in range(n + 1)]
    # score[i][j]: iからstartしてj回移動した時のスコア
    l_cycle = [0] * (n + 1)
    for i in range(1, n + 1):
        start = i
        move_cnt = 0
        nxt = i
        while move_cnt < n:
            nxt = p[nxt]
            score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
            move_cnt += 1
            if nxt == start:
                l_cycle[start] = move_cnt
                break
    # for i in range(1, n + 1):
    #     print(score[i])
    # print('l_cycle', l_cycle)
    ans = -float('inf')
    for s in range(1, n + 1):
        if k <= l_cycle[s]:
            # サイクルを回らないので
            temp = max(score[s][1:k + 1])
            ans = max(ans, temp)
            continue
        # 以降は一周以上出来る時

        # 一周以下でやめる場合を探索
        temp = max(score[s][1:l_cycle[s] + 1])
        ans = max(ans, temp)
        # if score[s][l_cycle[s]] <= 0:
        #     # 周回する意味がない
        #     continue
        sk = k // l_cycle[s]  # 何周出来るか
        remk = k % l_cycle[s]
        temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
        if remk != 0:
            temp += max(score[s][1:remk + 1])
        ans = max(ans, temp)
    return ans


def ac_solve(n, k, p, c):
    for i in range(n):
        p[i] -= 1
    ans = -float('inf')
    for st in range(n):
        x = st
        score = []
        tot = 0
        while True:
            x = p[x]
            score.append(c[x])
            tot += c[x]
            if x == st:
                break
        l = len(score)
        now = 0
        t = 0
        for i in range(l):
            t += score[i]
            if i + 1 > k:
                break
            now = t
            if tot > 0:
                cycle_num = (k - (i + 1)) // l
                now += tot * cycle_num
            ans = max(ans, now)
    return ans


def main():
    while True:
        n = random.randint(2, 5)
        k = random.randint(1, 10)
        p = list(range(1, n + 1))
        random.shuffle(p)
        c = [random.randint(-100, 100) for _ in range(n)]
        c2 = c[:]
        ans1 = my_solve(n, k, p, c)
        org_p = p[:]
        ans2 = ac_solve(n, k, org_p, c2)
        # assert org_p == p, f'{org_p}:{p}'
        if ans1 == ans2:
            continue
            print('ok')
        else:
            print('ng')
            print(n, k)
            print(f'my_ans:{ans1}')
            print(f'ac_ans:{ans2}')


def main2():
    n = int(input())
    k = int(input())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    print(my_solve(n, k, p, c))


if __name__ == '__main__':
    main2()

Buggy submission (verdict: Runtime Error):
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 = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    for i in range(l):
        now += s[i]
        if i + 1 > k:
            break
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
            ans = max(ans, now)
            pass
        else:
            pass

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
c = list(map(int, input().split()))
c = [0] + c
score = [[0] * (n + 1) for _ in range(n + 1)]
# score[i][j]: iからstartしてj回移動した時のスコア
l_cycle = [0] * (n + 1)
for i in range(1, n + 1):
    start = i
    move_cnt = 0
    nxt = i
    while move_cnt < n:
        nxt = p[nxt]
        score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
        move_cnt += 1
        if nxt == start:
            l_cycle[start] = move_cnt
            break
# for i in range(1, n + 1):
#     print(score[i])
# print('l_cycle', l_cycle)
ans = -float('inf')
for s in range(1, n + 1):
    if k <= l_cycle[s]:
        # サイクルを回らないので
        temp = max(score[s][1:k + 1])
        ans = max(ans, temp)
        continue
    # 以降は一周以上出来る時

    # 一周以下でやめる場合を探索
    temp = max(score[s][1:l_cycle[s] + 1])
    ans = max(ans, temp)
    if score[s][l_cycle[s]] <= 0:
        # 周回する意味がない
        continue
    sk = k // l_cycle[s]  # 何周出来るか
    remk = k % l_cycle[s]
    temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
    temp += max(score[s][1:remk + 1])
    ans = max(ans, temp)

print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
c = list(map(int, input().split()))
c = [0] + c
score = [[0] * (n + 1) for _ in range(n + 1)]
# score[i][j]: iからstartしてj回移動した時のスコア
l_cycle = [0] * (n + 1)
for i in range(1, n + 1):
    start = i
    move_cnt = 0
    nxt = i
    while move_cnt < n:
        nxt = p[nxt]
        score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
        move_cnt += 1
        if nxt == start:
            l_cycle[start] = move_cnt
            break
# for i in range(1, n + 1):
#     print(score[i])
# print('l_cycle', l_cycle)
ans = -float('inf')
for s in range(1, n + 1):
    if k <= l_cycle[s]:
        # サイクルを回らないので
        temp = max(score[s][1:k + 1])
        ans = max(ans, temp)
        continue
    # 以降は一周以上出来る時

    # 一周以下でやめる場合を探索
    temp = max(score[s][1:l_cycle[s] + 1])
    ans = max(ans, temp)
    if score[s][l_cycle[s]] <= 0:
        # 周回する意味がない
        continue
    sk = k // l_cycle[s]  # 何周出来るか
    remk = k % l_cycle[s]
    temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
    temp += max(score[s][1:remk + 1])
    ans = max(ans, temp)

print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
c = list(map(int, input().split()))
c = [0] + c
score = [[0] * (n + 1) for _ in range(n + 1)]
# score[i][j]: iからstartしてj回移動した時のスコア
l_cycle = [0] * (n + 1)
for i in range(1, n + 1):
    start = i
    move_cnt = 0
    nxt = i
    while move_cnt < n:
        nxt = p[nxt]
        score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
        move_cnt += 1
        if nxt == start:
            l_cycle[start] = move_cnt
            break
# for i in range(1, n + 1):
#     print(score[i])
# print('l_cycle', l_cycle)
ans = -float('inf')
for s in range(1, n + 1):
    if k <= l_cycle[s]:
        # サイクルを回らないので
        temp = max(score[s][1:k + 1])
        ans = max(ans, temp)
        continue
    # 以降は一周以上出来る時

    # 一周以下でやめる場合を探索
    temp = max(score[s][1:l_cycle[s] + 1])
    ans = max(ans, temp)
    if score[s][l_cycle[s]] <= 0:
        # 周回する意味がない
        continue
    sk = k // l_cycle[s]  # 何周出来るか
    remk = k % l_cycle[s]
    temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
    temp += max(score[s][1:remk + 1])
    ans = max(ans, temp)

print(ans)