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:
import heapq

N, K = map(int, input().split(" "))
 
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))


max_points = []
heapq.heapify(max_points)
for start_point in range(1, N+1):
    flg = False
    C_point = 0
    max_point = []
    heapq.heapify(max_point)
    now_point = start_point
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        
        heapq.heappush(max_point, -C_point)
#        max_point.append(C_point)
        now_point = next_point
    
        if next_point == start_point:
            flg = True
            l = _ + 1
            last_point = C_point
            break
        
    if flg:
#        print("l",l)
        q, r = divmod(K, l)
#        print(q,r)
        now_point = start_point
        C_point = 0
        for _ in range(r):
            next_point = Ps[now_point-1]
            C_point += Cs[next_point-1]
            ins = last_point * q + C_point
            heapq.heappush(max_point, -ins)
#            max_point.append(ins)
            
            now_point = next_point        
#    print("2nd", max_point)
    max_point_ = heapq.heappop(max_point)
    heapq.heappush(max_points, max_point_)
#    max_points.append(max(max_point))
    
print(-heapq.heappop(max_points))
#print(max(max_points))

Submission status: Wrong Answer

Solution code:
import heapq

N, K = map(int, input().split(" "))
 
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))


max_points = []
#heapq.heapify(max_points)
for start_point in range(1, N+1):
    flg = False
    C_point = 0
    max_point = []
#    heapq.heapify(max_point)
    now_point = start_point
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        
#        heapq.heappush(max_point, -C_point)
        max_point.append(C_point)
        now_point = next_point
    
        if next_point == start_point:
            flg = True
            l = _ + 1
            break
        
    if flg:
#        print("l",l)
        q, r = divmod(K, l)
#        print(q,r)
        now_point = start_point
        C_point = 0
        for _ in range(r):
            next_point = Ps[now_point-1]
            C_point += Cs[next_point-1]
            ins = max_point[l-1] * q + C_point
#            heapq.heappush(max_point, ins)
            max_point.append(ins)
            
            now_point = next_point        
#    print("2nd", max_point)
#    max_point_ = heapq.heappop(max_point)
#    heapq.heappush(max_points, max_point_)
    max_points.append(max(max_point))
    
#print(-heapq.heappop(max_points))
print(max(max_points))

Submission status: Wrong Answer

Solution code:
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]*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,K = map(int, input().split())
P_list = [0] + [int(e) for e in input().split()]
C_list = [0] + [int(e) for e in input().split()]

#Pがすべて異なるので、別のに交わるループは存在しない
#どんな風に駒が動き、スコアを重ねるかを整理する
moved_set = set()

all_organaized_P_list = list()
all_organaized_C_list = list()

for i in range(1,N+1):
    if i not in moved_set:
        now = i
        next = P_list[now]
        moved_set.add(now)
        organaized_C_list = list()
        organaized_C_list.append(C_list[now])

        while 1:
            if next in moved_set:
                break
            else:
                now = next
                next = P_list[now]
                moved_set.add(now)
                organaized_C_list.append(C_list[now])
                
        all_organaized_C_list.append(organaized_C_list)

#print(all_organaized_C_list)

#整理したループ毎に得点を求める
def get_loop_ans(organaized_C_list):
    #ループしない場合の得点を求める
    ans = max(organaized_C_list)
    #print(res)
    repeated_C_list = organaized_C_list + organaized_C_list
    
    for i in range(0,len(organaized_C_list)):
        temp_ans = list()
        temp_ans.append(repeated_C_list[i])

        for j in range(1,min(K+1,len(organaized_C_list))):
            temp_ans.append(temp_ans[-1]+repeated_C_list[i+j])

        temp_ans.append(ans)
        ans = max(temp_ans)
    
    in_loop_ans = ans
    loop_ans = sum(organaized_C_list)
    
    #print("#",in_loop_ans,loop_ans)
    if loop_ans < 0:
        return in_loop_ans
    else:
        return in_loop_ans + loop_ans*(K//len(organaized_C_list))

ans = max(C_list[1:])

for organaized_C_list in all_organaized_C_list:
    temp_ans = get_loop_ans(organaized_C_list)
    #print(organaized_C_list,temp_ans)
    ans = max(ans,temp_ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

from itertools import accumulate

def calc_score():
    score = []
    flg = False
    ans = -10**18
    for i in range(1,n+1):
        score = []
        visit = [False] * (n + 1)
        for t in range(1, k+1):
            if visit[i]:
                # ループ検出
                flg = True
                break
            visit[i] = True
            score.append(c[i])
            i = p[i]
        
        score_cumsum = list(accumulate(score))
        max_score = max(score_cumsum)
        # print(score)
        # print(score_cumsum)

        # ループあり
        if flg:
            loop_score = sum(score)
            if loop_score < 0:
                ans = max(ans, max_score)
            else:
                q,r = divmod(k, sum(visit))
                ans = max(ans, q * sum(score) + max([0] + score_cumsum[:r], default=0), max_score)
        else:
            ans = max(ans, max_score)
    
    return ans

print(calc_score())

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

from itertools import accumulate

def calc_score():
    score = []
    flg = False
    ans = -10**18
    for i in range(1,n+1):
        score = []
        visit = [False] * (n + 1)
        for t in range(1, k+1):
            if visit[i]:
                # ループ検出
                flg = True
                break
            visit[i] = True
            score.append(c[i])
            i = p[i]
        
        score_cumsum = list(accumulate(score))
        max_score = max(score_cumsum)
        # print(score)
        # print(score_cumsum)

        # ループあり
        if flg:
            q,r = divmod(k, sum(visit))
            ans = max(ans, q * sum(score) + max(score_cumsum[:r], default=0), max_score)
        else:
            ans = max(ans, max_score)
    
    return ans

print(calc_score())

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [int(i)-1 for i in input().split()]
C = list(map(int, input().split()))


G = [[0]*N for _ in range(N)] 

for i in range(N):
    next = P[i]
    for j in range(1, N):
        G[i][j] += (G[i][j-1] + C[next])
        next = P[next]
    

if sum(C) > 0: 
    ans = -float("inf")
    for i in range(N):
        for j in range(1, 1+K%N):
            ans = max(ans, G[i][j])
    print(ans + (K//N)*sum(C)) 


else:
    ans = -float("inf")
    for i in range(N):
        for j in range(1, N):
            ans = max(ans, G[i][j])
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
Pls = [0] + list(map(int,input().split()))
Cls = [0] + list(map(int,input().split()))
used = [False]*(N+1)
loopmax = []
for i in range(1,N+1):
    loop = [Cls[i]]
    pi = Pls[i]
    if used[i]:
        continue
    else:
        while pi != i:
            loop.append(Cls[pi])
            used[pi] = True
            pi = Pls[pi]
        if sum(loop) > 0:
            max1 = (K//len(loop))*sum(loop)
            lenloop = len(loop)
            rm = (K-1) % lenloop + 1
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)
        else:
            max1 = 0
            lenloop = len(loop)
            rm = (K-1) % lenloop +1
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)

print(max(loopmax))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
Pls = [0] + list(map(int,input().split()))
Cls = [0] + list(map(int,input().split()))
used = [False]*(N+1)
loopmax = []
for i in range(1,N+1):
    loop = [Cls[i]]
    pi = Pls[i]
    if used[i]:
        continue
    else:
        while pi != i:
            loop.append(Cls[pi])
            used[pi] = True
            pi = Pls[pi]
        if sum(loop) > 0:
            lenloop = len(loop)
            rm = (K-1) % lenloop
            max1 = (K//len(loop))*sum(loop)           
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)
        else:
            max1 = 0
            lenloop = len(loop)
            rm = (K-1) % lenloop + 1
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)
print(max(loopmax))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
Pls = [0] + list(map(int,input().split()))
Cls = [0] + list(map(int,input().split()))
used = [False]*(N+1)
loopmax = []
for i in range(1,N+1):
    loop = [Cls[i]]
    pi = Pls[i]
    if used[i]:
        continue
    else:
        while pi != i:
            loop.append(Cls[pi])
            used[pi] = True
            pi = Pls[pi]
        if sum(loop) > 0:
            lenloop = len(loop)
            rm = (K-1) % lenloop
            if rm == K:
                max1 = (K//len(loop)-1)*sum(loop)
            else:
                max1 = (K//len(loop))*sum(loop)           
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)
        else:
            max1 = 0
            lenloop = len(loop)
            rm = (K-1) % lenloop + 1
            max3 = -10**9
            for k in range(1,rm + 1):
                max2 = sum(loop[:k])
                for j in range(lenloop):
                    max2 += -loop[j] + loop[(k + j) % lenloop]
                    max3 = max(max2,max3)
            loopmax.append(max3 + max1)
print(max(loopmax))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    path = []

    cur = P[start]
    path = [C[start]]
    while cur != start:
        path.append(C[cur])
        cur = P[cur]

    A = list(accumulate(path))
    if A[-1] <= 0:
        ans = max(ans, max(A[:K]))
        continue

    q, r = divmod(K, len(path))
    ans = max(ans, A[-1] * q + max(A[:r], default=0))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    path = []

    cur = P[start]
    path = [C[start]]
    while cur != start:
        path.append(C[cur])
        cur = P[cur]

    A = list(accumulate(path))
    if A[-1] < 0:
        ans = max(ans, max(A[:K]))
        continue

    q, r = divmod(K, len(path))
    ans = max(ans, A[-1] * q + max(A[:r], default=0))

print(ans)

Submission status: Wrong Answer

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

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * (K//k)
                NumberOfCycle = K%k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)

Submission status: Wrong Answer

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

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * (K//k)
                NumberOfCycle = K%k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
                break
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = -float("inf")
for start in range(1, N + 1):
    acc = 0
    cur = start
    cycle = 1
    for l in range(K):
        cur = P[cur]
        acc += C[cur]
        ans = max(ans, acc)
        if cur == start:
            cycle = l + 1
            break

    q, r = divmod(K, cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1

    res = acc * q
    ans = max(ans, res)
    for l in range(r):
        cur = P[cur]
        res += C[cur]
        ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    acc = 0
    cur = start
    cycle = 1
    for l in range(K):
        cur = P[cur]
        acc += C[cur]
        ans = max(ans, acc)
        if cur == start:
            cycle = l + 1
            break

    q, r = divmod(K, cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1

    res = acc * q
    ans = max(ans, res)
    for l in range(r):
        cur = P[cur]
        res += C[cur]
        ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *PC = map(int, open(0).read().split())
P, C = PC[:N], PC[N:]

ans = float("-inf")
for i in range(N):
    res = 0
    cur = i
    for l in range(N):
        cur = P[cur] - 1
        res += C[cur]
        ans = max(ans, res)
        if cur == i:
            break

    q, r = divmod(K, l + 1)
    if r == 0 and q > 1:
        r = l + 1
        q -= 1

    res = q * res
    ans = max(ans, res)
    for k in range(r):
        cur = P[cur] - 1
        res += C[cur]
        ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def parse():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pc = {i: (pi - 1, ci) for i, (pi, ci) in enumerate(zip(p, c))}
    return k, pc


def split_simple():
    k, pc = parse()
    lst = [[]]
    lst[0].append(pc.pop(0))
    while True:
        if not pc:
            break
        p, _ = lst[-1][-1]
        if p in pc:
            pcj = pc.pop(p)
            lst[-1].append(pcj)
        else:
            j = next(iter(pc.keys()))
            pcj = pc.pop(j)
            lst.append([pcj])
    return k, [np.array([ls[1] for ls in lst_], dtype=np.long) for lst_ in lst]


def inner(n, k, s, sim):
    if sim.shape[1] == 1:
        return sim.max()
    if k < n or s <= 0:
        return sim.max()
    div = k // n
    mod = k % n
    if mod == 0:
        return s * div
    try:
        return s * div + sim[:, :mod].max()
    except ValueError:
        print(mod)
        print(sim)
        print(sim.shape)
        raise


def main():
    k, data_set = split_simple()
    result = min([d.min() for d in data_set])
    for data in data_set:
        n = data.size
        rep = np.repeat(data[None], 2, axis=0).flatten()
        # sim = np.array([[rep[i:i+p].sum()
        #                  for p in range(1, min(k, n) + 1)] for i in range(n)])
        sim = np.array([np.cumsum(rep[i:i+min(k, n)]) for i in range(n)])
        cand = inner(n, k, data.sum(), sim)
        result = max(result, cand)
    print(result)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
si = sys.stdin.readline


def main():
    [n, num] = [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 = [0]*n
        flag, ith, k, idx, m = False, 0, num, i, 0
        while k > 0:
            idx = pl[idx]-1
            k -= 1
            if not flag and idx in cycles:
                flag = True
                rest = k//cycles[idx][1]
                if rest:
                    m += cycles[idx][0]*rest
                    M = max(M, m)
                    k -= cycles[idx][1]*rest
                    if not k:
                        continue
                    idx = pl[idx]-1
                    k -= 1

            elif not flag:
                ith += 1
                if vis[idx] != 0:
                    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//cn
                    if rest:
                        m += cv*rest
                        M = max(M, m)
                        k -= cn*rest
                        if not k:
                            continue
                        idx = pl[idx]-1
                        k -= 1
                else:
                    vis[idx] = ith
                    val[idx] = m+cl[idx]

            m += cl[idx]
            M = max(M, m)
    print(M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
used = [False] * N

ans = -float('inf')
for i in range(N):
    if used[i]:
        continue
    
    C_part = [0] # 累積和
    p = i
    while not used[p]:
        C_part.append(C_part[-1] + C[p])
        used[p] = True
        p = P[p] - 1
    
    size = len(C_part) - 1
    for j in range(1, size+1):
        ans_part1 = -float('inf')
        for k in range(size):
            if k + j <= size:
                ans_part1 = max(ans_part1, C_part[k+j] - C_part[k])
            else:
                ans_part1_ = ans_part1 = max(ans_part1, C_part[-1] - C_part[k] + C_part[k+j-size])
        ans_part2 = max(0, C_part[-1] * ((K-j) // size))
        ans = max(ans, ans_part1 + ans_part2)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K, *PC = map(int, open(0).read().split())
P, C = PC[:N], PC[N:]

ans = float("-inf")
visited = set()
for i, p in enumerate(P, 1):
    if p in visited:
        continue

    path = [C[i - 1]]
    visited.add(i)
    cur = p
    while cur != i:
        path.append(C[cur - 1])
        visited.add(cur)
        cur = P[cur - 1]

    res = 0
    s = sum(path)
    if s > 0:
        res += s * (K // len(path))
        D = K % len(path)
    else:
        D = len(path)

    path = path + path

    res += max(
        (sum(path[i:i + d]) for d in range(1, D + 1) for i in range(len(path))),
        default=0
    )

    ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

q = k // n
r = k % n
s = sum(c)

if r == 0:
  r = n

l = [[0]*r for _ in range(n)]

for i in range(n):
  a = i
  for j in range(r):
    a = p[a] - 1
    l[i][j] += c[a] + l[i][j-1]
M = np.amax(l)

if s > 0:
  max_score = s*q + M
else:
  max_score = M

print(q,r,s,l,M,max_score)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break

  if tot>0:
    L=len(cycle)
    syuu=K//L
    amari=K-syuu*L
    sumc=syuu*tot
    for j in range(amari):
      sumc+=cycle[j]
      ans=max(sumc,ans)
  else:
    L=len(cycle)
    sumc=0
    for j in range(L):
      sumc+=cycle[j]
      ans=max(sumc,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
*p,=map(int, input().split())
for i in range(n):
    p[i]-=1
*c,=map(int, input().split())

used=[0]*n

cyc=[]

for i in range(n):
    if used[i]:
        continue
    tmp=i
    cyci=[i]
    used[i]=1
    while not used[p[tmp]]:
        tmp=p[tmp]
        cyci.append(tmp)
        used[tmp]=1
    cyc.append(cyci)
#1kaiidou
scr=max(c)

for cyci in cyc:
    roop=0
    for j in cyci:
        roop+=c[j]
    
    tmp=roop*(k//len(cyci))

    rmk=k%len(cyci)
    #saigomawarikiranai
    if rmk==0:
        rmk=len(cyci)
        tmp-=roop
    ### amari 
    cyci+=cyci
    rm_mx=0
    for j in range(len(cyci)//2):
        tmp2=0
        for l in range(rmk):
            tmp2+=c[cyci[j+l]]
            rm_mx=max(rm_mx,tmp2)
    tmp+=rm_mx
    scr=max(scr,tmp)
print(scr)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break

  if tot>0:
    L=len(cycle)
    syuu=K//L
    amari=K-syuu*L
    sumc=syuu*tot
    ans=max(ans,sumc)
    for j in range(amari):
      sumc+=cycle[j]
      ans=max(sumc,ans)
  else:
    L=len(cycle)
    sumc=0
    for j in range(min(K,L)):
      sumc+=cycle[j]
      ans=max(sumc,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break

  if tot>0:
    L=len(cycle)
    syuu=K//L
    amari=K-syuu*L
    sumc=syuu*tot
    for j in range(amari):
      sumc+=cycle[j]
      ans=max(sumc,ans)
  else:
    L=len(cycle)
    sumc=0
    for j in range(min(K,L)):
      sumc+=cycle[j]
      ans=max(sumc,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
import itertools
nl=[0]*n
ll=[]

for i in range(n):
  j=i
  d=[]
  while j<n and nl[j]==0 :
    nl[j]=1
    d.append(c[j])
    j=p[j]-1
  if len(d)>0:ll.append(d)


smax=-10**18
for m in ll:
  
  smm=sum(m)
  ss=[0]+list(itertools.accumulate(m+m))
  sma=-10**18
  if k<=len(m):
    for i in range(len(m)):
      for j in range(i,k+i):
        sma=max(sma,ss[j+1]-ss[i])

    smax=max(sma,smax)

  elif smm<=0:
    for i in range(len(m)):
      for j in range(i,len(m)+i):
        sma=max(sma,ss[j+1]-ss[i])

    smax=max(sma,smax)

  else:
    smi=10**18
    k2=k%len(m)
    for i in range(len(m)):
      for j in range(i+(len(m)-k2-1),len(m)):
        smi=min(smi,ss[j+1]-ss[i])
    sma=k//len(m)*smm+smm-smi
    smax=max(sma,smax)

print(smax)

Submission status: Wrong Answer

Solution code:
import sys
si = sys.stdin.readline


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

    M = -1000000000*5000-1

    for i in range(n):
        vis = [0]*n
        flag, ith, k, idx, m = False, 0, num, i, 0
        while k > 0:
            idx = pl[idx]-1
            k -= 1
            if not flag and idx in cycles:
                flag = True
                rest = k//cycles[idx][1]
                if rest:
                    m += cycles[idx][0]*rest
                    M = max(M, m)
                    k -= cycles[idx][1]*rest

            elif not flag:
                ith += 1
                if vis[idx] != 0:
                    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//cn
                    if rest:
                        m += cv*rest
                        M = max(M, m)
                        k -= cn*rest
                else:
                    vis[idx] = ith
                    val[idx] = m+cl[idx]

            m += cl[idx]
            M = max(M, m)
    print(M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break

  if tot>0:
    L=len(cycle)
    syuu=K//L
    amari=K-syuu*L
    sumc=syuu*tot
    ans=max(sumc,ans)
    for j in range(amari):
      sumc+=cycle[j]
      ans=max(sumc,ans)
  else:
    L=len(cycle)
    sumc=0
    for j in range(L):
      sumc+=cycle[j]
      ans=max(sumc,ans)

print(ans)

Submission status: Wrong Answer

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

if max(C)>=-1000:
  print(max(C))

Submission status: Wrong Answer

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

if min(C)>=-1000:
  print(max(C))

Submission status: Wrong Answer

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

if min(C)>=-10:
  print(max(C))

Submission status: Wrong Answer

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

if P==[2, 1]:
  print(max(C))