Problem p02585 (python)

Fixed submission:
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')

Buggy submission (verdict: Runtime Error):
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

def max_calc(costs, st, num):
    len_c = len(costs)
    max_c = -INF
    sum_c = 0
    for d in range(num):
        i = (st + d) % len_c
        x = costs[i]
        sum_c += x
        max_c = max(max_c, sum_c)
    return max_c

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    len_c = len(costs)
    cnt, remain = divmod(k, len_c)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = max_calc(costs, st, len_c)
            cost = max_c
            # print('1. cost',cost)
        else: # lp_c > 0:
            if cnt == 0:
                max_c = max_calc(costs, st, min(len_c, k))
                cost = max_c
                # print('2. cost',cost)
            else: # cnt > 0
                max_c = max_calc(costs, st, len_c + remain)
                if cnt > 1 :
                    cost = lp_c * (cnt-1)
                    cost = max({cost, cost + max_c, max_c})
                    # print('3. cost',cost)
                else: # cnt == 1
                    cost = max({lp_c, max_c})
                    # print('4. cost',cost)
        score = max({score, cost})
print(score)

Buggy submission (verdict: Runtime Error):
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

def max_calc(costs, st, num):
    len_c = len(costs)
    max_c = -INF
    sum_c = 0
    for d in range(num):
        i = (st + d) % len_c
        x = costs[i]
        sum_c += x
        max_c = max(max_c, sum_c)
    return max_c

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    len_c = len(costs)
    cnt, remain = divmod(k, len_c)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = max_calc(costs, st, len_c)
            cost = max_c
            # print('1. cost',cost)

        else: # lp_c > 0:
            if cnt == 0:
                max_c = max_calc(costs, st, min(len_c, k))
                cost = max_c
                # print('2. cost',cost)
            else: # cnt > 0
                max_c = max_calc(costs, st, len_c + remain)
                cost = lp_c * (cnt-1)
                cost = max(cost, cost + max_c)
                # print('3. cost',cost)
        score = max({score, cost})
print(score)

Buggy submission (verdict: Runtime Error):
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

def max_calc(costs, st, remain=0):
    len_c = len(costs)
    max_c = -INF
    sum_c = 0
    for d in range(len_c + remain):
    # for d in range(len_c):
        i = (st + d) % len_c
        x = costs[i]
        sum_c += x
        max_c = max(max_c, sum_c)
    return max_c

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    cnt, remain = divmod(k, len(costs))
    len_c = len(costs)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = max_calc(costs, st)
            cost = max_c
            # print('1. cost',cost)

        else: # lp_c > 0:
            if cnt == 0:
                max_c = max_calc(costs, st)
                cost = max_c
                # print('2. cost',cost)

            else: # cnt > 0
                cost = lp_c * (cnt-1)
                max_c = max_calc(costs, st, remain)
                cost = max(cost, cost + max_c)

        score = max({score, cost})
print(score)

Buggy submission (verdict: Runtime Error):
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

# print(*lst_costs,sep='\n',end='\n\n')

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    cnt, remain = divmod(k, len(costs))
    len_c = len(costs)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = -INF
            sum_c = 0
            for d in range(len_c):
                i = (st + d) % len_c
                x = costs[i]
                # print(st,d,i,x)
                sum_c += x
                max_c = max(max_c, sum_c)
            cost = max_c
            # print('1. cost',cost)
        else: # lp_c > 0:
            if cnt == 0:
                max_c = -INF
                sum_c = 0
                for d in range(len_c):
                    i = (st + d) % len_c
                    x = costs[i]
                    sum_c += x
                    max_c = max(max_c, sum_c)
                cost = max_c
                # print('2. cost',cost)

            else: # cnt > 0
                cost = lp_c * (cnt-1)
                max_c = -INF
                sum_c = 0
                # for d in range(remain):
                for d in range(len_c+remain):
                    i = (st + d) % len_c
                    x = costs[i]
                    sum_c += x
                    max_c = max(max_c, sum_c)
                cost = max_c + cost
                # print('3. cost',cost)

        score = max({score, cost})
print(score)

Buggy submission (verdict: Runtime Error):
INF = 1*((10**9)*5000 + 1)
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(P)
# print(C,end='\n\n')

vis = [False]*(n+1)
def dfs(i, c, sum_c=0):
    if vis[i]: return c, sum_c
    vis[i] = True
    c.append(C[i])
    sum_c += C[i]
    ret = dfs(P[i], c, sum_c)
    # vis[i] = False
    return ret

lst_costs = []
for i in range(n):
    costs, lp_c = dfs(i, [])
    if len(costs) == 0: continue
    lst_costs.append((costs,lp_c))

# print(*lst_costs,sep='\n',end='\n\n')

score = -INF
for costs, lp_c in lst_costs:
    # print(costs, lp_c)
    cnt, remain = divmod(k, len(costs))
    len_c = len(costs)
    for st in range(len_c):
        cost = -INF
        if lp_c <= 0:
            max_c = -INF
            sum_c = 0
            for d in range(len_c):
                i = (st + d) % len_c
                x = costs[i]
                # print(st,d,i,x)
                sum_c += x
                max_c = max(max_c, sum_c)
            cost = max_c
            # print('1. cost',cost)
        else: # lp_c > 0:
            if cnt == 0:
                max_c = -INF
                sum_c = 0
                for d in range(len_c):
                    i = (st + d) % len_c
                    x = costs[i]
                    sum_c += x
                    max_c = max(max_c, sum_c)
                cost = max_c
                # print('2. cost',cost)

            else: # cnt > 0
                cost = lp_c * cnt
                max_c = -INF
                sum_c = 0
                for d in range(remain):
                    i = (st + d) % len_c
                    x = costs[i]
                    sum_c += x
                    max_c = max(max_c, sum_c)
                cost = max_c + cost
                # print('3. cost',cost)

        score = max({score, cost})
print(score)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
TO = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(TO)
# print(C)

vis = [False]*(n+1)
def dfs(i, t):
    if vis[i]: return t
    vis[i] = True
    t.append(i)
    return dfs(TO[i], t)

INF = 1*((10**9)*5000 + 1)
score = -INF
for f in range(n):
    T = dfs(f, [])
    len_t = len(T)
    if len_t == 0: continue
    costs = [0] * (len_t)
    for i in range(len_t): costs[i] = C[T[i]]
    loops = k // len_t
    cost = sum(costs)
    # print(len_t, T, 'costs',costs, cost, loops)
    # if cost >= 0:
    #     k -= loops * len_t
    #     cost = cost * loops

    if cost >= 0:
        k -= loops * len_t
    else:
        pass

    peak_cost = -INF
    for i in range(len_t):
        sum_cost = 0
        for j in range(k):
            sum_cost += costs[(i+j)%len_t]
            peak_cost = max(peak_cost, sum_cost)
    # print(k,'peak_cost',peak_cost, cost)
    cost = max({cost, cost + peak_cost, cost*loops + peak_cost, peak_cost})
    # print('cost',cost)
    score = max(score, cost)
print(score)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
TO = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(TO)
# print(C)

vis = [False]*(n+1)
def dfs(i, t):
    if vis[i]: return t
    vis[i] = True
    t.append(i)
    return dfs(TO[i], t)

INF = 1*((10**9)*5000 + 1)
score = -INF
for f in range(n):
    T = dfs(f, [])
    len_t = len(T)
    if len_t == 0: continue
    costs = [0] * (len_t)
    for i in range(len_t): costs[i] = C[T[i]]
    loops = k // len_t
    cost = sum(costs)
    # print(len_t, T, 'costs',costs, cost, loops)
    if cost >= 0:
        k -= loops * len_t
        cost = cost * loops

    peak_cost = -INF
    for i in range(len_t):
        sum_cost = 0
        for j in range(k):
            sum_cost += costs[(i+j)%len_t]
            peak_cost = max(peak_cost, sum_cost)
    # print(k,'peak_cost',peak_cost, cost)
    cost = max({cost, cost + peak_cost, peak_cost})
    # print('cost',cost)
    score = max(score, cost)
print(score)