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:
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)
    ### 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()))
C = list(map(int, input().split()))

if P==[1, 2]:
  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 k==1:
  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 k<=3:
  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 k<=5:
  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 k==5:
  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 n==2:
  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 n==1:
  print(max(C))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


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

for i in range(N):
    uf.union(i, P[i]-1)

ans = -float('inf')
for root in uf.roots():
    ans_part = -float('inf')
    size = uf.size(root)
    C_part = []
    p = root
    for _ in range(uf.size(root)):
        C_part.append(C[p])
        p = P[p]-1
        
    roundcsum = [0] + list(accumulate(C_part))
    w = min(K, size)
    for i in range(1, w+1):
        ans_part1 = -float('inf')
        for j in range(size):
            if j+i <= size:
                ans_part1_1 = roundcsum[j+i] - roundcsum[j]
            else:
                ans_part1_1 = roundcsum[-1] - roundcsum[j] + roundcsum[j+i-size]
            ans_part1 = max(ans_part1, ans_part1_1)
        ans_part2 = max(0, roundcsum[-1]*(K-i)//size)
        ans = max(ans, ans_part1 + ans_part2)

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 n<5:
  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 n<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 n<100:
  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 max(C)<0:
  print(max(C))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

P = [p - 1 for p in P]

check = [False] * n
loops = []

for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)

ans = 0

for loop in loops:

    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = -1e9
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k > num and sumL <= 0:
        r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))

    for i in range(num):
        for j in range(i + 1, i + r + 1):
            ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)

    ans = max(ans, ans_tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

P = [p - 1 for p in P]

check = [False] * n
loops = []

for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)

ans = -1e9

for loop in loops:

    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = 0
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k > num and sumL <= 0:
        r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))

    for i in range(num):
        for j in range(i + 1, i + r + 1):
            ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)

    ans = max(ans, ans_tmp)
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()))

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()))

ans = -100000000000000000000000000000000000
ans_ = -100000000000000000000000000000000000
for i in range(n):
    base = c[i]
    ans_check = c[i]
    ttt = p[i] - 1
    aaa = k // n
    for j in range(n):
        ans_check += c[ttt]
        ttt = p[ttt] - 1
        if base < ans_check:
            base = ans_check
    
    if base > 0:
        ans_ = base * aaa
        ttt = p[i]-1
        for k in range(k % n + 1):
            ans_ += c[ttt]
            ttt = p[ttt] - 1
            if base < ans_:
                base = ans_
    else:
        ans_ = base
        
    if ans < ans_:
        ans = ans_
        
        
print(ans)

Submission status: Wrong Answer

Solution code:
'''
参考
https://marco-note.net/abc-175-work-log/
'''
N, K = map(int, input().split())        # コマ数、最大移動可能回数
P = list(map(int, input().split()))     # 移動先のコマ番号
C = list(map(int, input().split()))     # そのコマに立ち寄った時に加算される得点

ans = -float('inf')             # 解を-∞で初期化

for piece in range(N):          # 各コマについて、スタート地点とした場合の得点を調べる
    S = []                      # 累積和
    mov = P[piece] - 1          # 1回目の移動：移動先（indexなので-1する）
    S.append(C[mov])            # 1回目の移動：得点

    while mov != piece:             # 2回目以降の移動（スタート地点に戻ったらループ終了）
        mov = P[mov] - 1            # 2回目以降：移動先
        S.append(S[-1] + C[mov])    # 2回目以降：得点（最終要素に加算した値をリストに追加）
    
    if K <= len(S):             # 【パターン1】与えられた移動可能回数では一巡できない
        score = max(S[:K])      # 得点=移動可能回数までの最大得点
    elif S[-1] <= 0:            # 【パターン2】一巡できるが一巡してしまうと得点が減る
        score = max(S)          # 得点=一巡するまでの最大得点
    else:
        score = S[-1] * (K // len(S))   # 【パターン3】与えられた移動可能回数で廻れるだけ廻る
        rem = K % len(S)
        if rem != 0:
            score += max(0, max(S[:rem]))
    
    ans = max(ans, score)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
C = [0] + list(map(int, input().split()))
P = [0] + list(map(int, input().split()))

max_ans = -10**9
for i in range(1, N+1):
    v = i
    s = 0
    loop = []
    while True:
        loop.append(v)
        s += P[v]
        v = C[v]
        if v == i:
            break

    L = len(loop)
    ans = P[loop[0]]
    b = 1
    for j in range(1, L):
        if P[loop[j]] >= 0:
            ans += P[loop[j]]
            b += 1
        else:
            break

    a = (K-b) // L
    r = (K-b) % L
    ans += a * max(0, s)

    for j in range(r):
        if P[loop[(j+b)%L]] >= 0:
            ans += P[loop[(j+b)%L]]
        else:
            break

    if ans > max_ans:
        max_ans = ans

print(max_ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
 
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
P = [p-1 for p in P]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = 0
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = 0  
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
#    if k>num and sumL <= 0:
#      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
if ans == 0:
    ans = max(C)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
 
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
P = [p-1 for p in P]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = -1e9
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = -1e9  
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
#    if k>num and sumL <= 0:
#      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
print(ans)

Submission status: Wrong Answer

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


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):
    index = ps[i] - 1
    value = cs[index]

    searchI = 0
    while True:
        indexG = graphs[searchI]
        if index in indexG:
            currentGraph = indexG
            break
        searchI += 1

    total = sum(vGraphs[searchI])

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // len(currentGraph)
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
 
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
P = [p-1 for p in P]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = -1e9
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = -1e9  
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k>num and sumL <= 0:
      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
print(ans)

Submission status: Wrong Answer

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

P = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

maxsum = -10 ** 9

for i in range(N):
    cycle = []
    cycle.append(C[i])
    temp = P[i]-1
    while temp != i:
        cycle.append(C[temp])
        temp = P[temp]-1

    Kdiv = (K-1) // len(cycle)
    Krem = ((K-1) % len(cycle)) + 1

    cyclesum = sum(cycle)
    psum = 0

    if cyclesum > 0:
        psum += cyclesum * Kdiv
    for j in range(Krem):
        psum += cycle[j]
        maxsum = max(maxsum, psum)

print(maxsum)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
 
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
P = [p-1 for p in P]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = 0
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = 0  
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k>num and sumL <= 0:
      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
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()))

visited=[True for _ in range(N)]
tempv=[]
sets=[]
if sum(1 for i in C if i<=0)==N:
    print(max(C))
    exit()
i=0
total=0
while True:
    if visited[i]:
        visited[i]=False
        tempv.append(i)
        i=P[i]-1
        total+=1
    elif total==N:
        sets.append(tempv)
        tempv=[]
        break
    else:
        sets.append(tempv)
        tempv=[]
        for k in range(N):
            if visited[k]:
                i=k
                break


# print(sets)
nofsets=len(sets)
nax=0
for i in range(nofsets):
    tempv=[C[j] for j in sets[i]]
    length=len(tempv)
    if sum(1 for cc in tempv if cc<=0)!=length:
        if K>=length:
            remainder=length
        else:
            remainder=K%length
        onecycle=sum(tempv)
        if onecycle<0:
            onecycle=0
        tempv=tempv+tempv
        for i in range(length):
            for j in range(remainder):
                total=sum([tempv[i+s] for s in range(j+1)])
                nax=max(nax,total+onecycle*((K-j-1)//length))

Submission status: Wrong Answer

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


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        # current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    # graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):
    index = ps[i] - 1
    value = cs[index]

    searchI = 0
    while True:
        vg = vGraphs[searchI]
        if value in vg:
            currentGraph = vg
            break
        searchI += 1

    total = sum(currentGraph)

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // len(currentGraph)
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
C = [0] + list(map(int, input().split()))
P = [0] + list(map(int, input().split()))

max_ans = -10**9
for i in range(1, N+1):
    v = i
    s = 0
    loop = []
    while True:
        loop.append(v)
        s += P[v]
        v = C[v]
        if v == i:
            break

    L = len(loop)
    ans = P[loop[0]]
    b = 1
    for j in range(1, L):
        if P[loop[j]] >= 0:
            ans += P[loop[j]]
            b += 1
        else:
            break

    a = (K-b) // L

    ans += a * max(0, s)
    if ans > max_ans:
        max_ans = ans

print(max_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()))

ans = -float('inf')
for i in range(n):
    score = []
    check = [0] * n
    now = i
    cycle = 0
    for _ in range(k):
        go = p[now] - 1
        if check[go] == 1:
            break
        now = go
        if len(score) == 0:
            score.append(c[now])
        else:
            score.append(score[-1] + c[now])
        check[now] = 1
        cycle += 1

    t = k // cycle
    m = k % cycle

    sum_cycle = score[-1]
    if m == 0:
        ans = max(sum_cycle * t, max(score), ans)
    else:
        ans = max(sum_cycle * t + max(score[:m]), max(score), ans)

    #print('sum_cycle:', sum_cycle, 'cycle:', cycle, 'ans:', ans)
    #print(i+1, score)
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()))

minusOnly = True
for i in range(n):
    if c[i] > 0:
        minusOnly = False
        break

if minusOnly:
    print(max(c))
    exit()

ans = 0
used = [False]*n

for st in range(n):
    if not used[st]:
        gr = []
        now = st
        gr.append(st)
        used[st] = True
        while True:
            now = p[now]
            gr.append(now)
            used[now] = True
            if now == st:
                break
        gr.pop()

        cs = [c[i] for i in gr]
        s = sum(cs)
        point = 0
        r = k
        if r > len(gr):
            if s > 0:
                point += s*(k//len(gr))
                r -= len(gr)*(k//len(gr))
            else:
                r = len(gr)
        
        cs = cs + cs + [cs[0]]
        plus = 0
        for i in range(1, len(gr)+1):
            nowSum = 0
            for g in range(r):
                nowSum += cs[i+g]
                plus = max(plus, nowSum)
        
        point += plus
        ans = max(ans, point)

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()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    accum=[0]+accum
    #print(accum)
    for x in range(1,l+1):
        if accum[x+l-1]-accum[x-1]<=0:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l])-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
            else:
                b=max(accum[x:x+l])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            ans=max(ans,max(k//l*d+b,max(k//l-1,0)*d+a))
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
C = [0] + list(map(int, input().split()))
P = [0] + list(map(int, input().split()))

max_ans = -10**9
for i in range(1, N+1):
    v = i
    s = 0
    loop = []
    while True:
        loop.append(v)
        s += P[v]
        v = C[v]
        if v == i:
            break

    L = len(loop)
    a = K // L
    r = K % L
    ans = a * max(0, s)

    tmp = P[loop[0]]
    if r > 0:
        for j in range(1, r):
            if P[loop[j]] >= 0:
                tmp += P[loop[j]]
            else:
                break

    ans += tmp
    if ans > max_ans:
        max_ans = ans

print(max_ans)

Submission status: Wrong Answer

Solution code:
N,K=input().split()
N=int(N)
K=int(K)
P=input().split()
C=input().split()
for i in range(N):
    P[i]=int(P[i])-1
for i in range(N):
    C[i]=int(C[i])
ans=-1000000001
for i in range(N):
    x=0
    n=i
    sum=0
    period=0
    while period<=N:
        sum+=C[n]
        n=P[n]
        period+=1
        if n==i:
            break
    m=int(K/period)
    K2=K
    if m>1 & sum>0:
        x=(m-1)*sum
        K2-=(m-1)*period
    elif K2>N & sum<=0:
        K2=N
    for j in range(K2):
        x+=C[n]
        n=P[n]
        ans=max(ans,x)
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()))

minusOnly = True
for i in range(n):
    if c[i] > 0:
        minusOnly = False
        break

if minusOnly:
    print(max(c))
    exit()

ans = 0
used = [False]*n

for st in range(n):
    if not used[st]:
        gr = []
        now = st
        gr.append(st)
        used[st] = True
        while True:
            now = p[now]
            gr.append(now)
            used[now] = True
            if now == st:
                break
        gr.pop()

        cs = [c[i] for i in gr]
        s = sum(cs)
        point = 0
        r = k
        if r > len(gr):
            if s >= 0:
                point += s*(k//len(gr))
                r -= len(gr)*(k//len(gr))
            else:
                r = len(gr)
        
        cs = cs + cs
        plus = 0
        for i in range(len(gr)):
            nowSum = 0
            for g in range(r):
                nowSum += cs[i+g]
                plus = max(plus, nowSum)
        
        point += plus
        ans = max(ans, point)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
C = [0] + list(map(int, input().split()))
P = [0] + list(map(int, input().split()))

sums = []
loops = []
for i in range(1, N+1):
    v = i
    s = 0
    loop = []
    while True:
        loop.append(v)
        s += P[v]
        v = C[v]
        if v == i:
            break

    loops.append(loop)
    sums.append(s)

max_ans = -10**9
for i, loop in enumerate(loops):
    L = len(loop)
    a = K // L
    r = K % L
    ans = a * max(0, sums[i])

    tmp = P[loop[0]]
    if r > 0:
        for j in range(1, r):
            if P[loop[j]] >= 0:
                tmp += P[loop[j]]
            else:
                break

    ans += tmp
    if ans > max_ans:
        max_ans = ans

print(max_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()))

minusOnly = True
for i in range(n):
    if c[i] > 0:
        minusOnly = False
        break

if minusOnly:
    print(max(c))
    exit()

ans = 0
used = [False]*n

for st in range(n):
    if not used[st]:
        gr = []
        now = st
        gr.append(st)
        used[st] = True
        while True:
            now = p[now]
            gr.append(now)
            used[now] = True
            if now == st:
                break
        gr.pop()

        cs = [c[i] for i in gr]
        s = sum(cs)
        point = 0
        r = k
        if k > len(gr):
            if s > 0:
                point += s*(k//len(gr))
                r -= len(gr)*(k//len(gr))
            else:
                r = len(gr)
        
        cs = cs + cs
        plus = 0
        for i in range(len(gr)+1):
            nowSum = 0
            for g in range(r):
                nowSum += cs[i+g]
                plus = max(plus, nowSum)
        
        point += plus
        ans = max(ans, point)

print(ans)

Submission status: Wrong Answer

Solution code:
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, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    print(my_solve(n, k, p, c))


if __name__ == '__main__':
    main2()

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()))

minusOnly = True
for i in range(n):
    if c[i] > 0:
        minusOnly = False
        break

if minusOnly:
    print(max(c))
    exit()

ans = 0

for st in range(n):
    gr = []
    now = st
    gr.append(st)
    while True:
        now = p[now]
        gr.append(now)
        if now == st:
            break
    gr.pop()

    cs = [c[i] for i in gr]
    s = sum(cs)
    point = 0
    r = k
    if k > len(gr):
        if s > 0:
            point += s*(k//len(gr))
            r -= len(gr)*(k//len(gr))
        else:
            r = len(gr)
    
    plus = 0
    nowSum = 0
    for i in range(r):
        nowSum += cs[i]
        plus = max(plus, nowSum)
    point += plus
    ans = max(ans, point)

print(ans)