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:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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]

d = [defaultdict(int) for _ in range(N)]
gdict = defaultdict(int)

ans = - float('inf')

for idx, p in enumerate(P):
    cnt = 1
    next = p
    if gdict[next] > 0:
        continue
    while True:
        if d[idx][next] > 0:
            break
        d[idx][next] = cnt
        gdict[next] = 1
        next = P[next]
        cnt += 1

for d_ in d:
    if len(d_) > 0:
        if len(d_) >= K:
            num = len(d_)
        else:
            num = K % len(d_)
        l = [C[val] for val in list(d_.keys())]
        # print(d_, l)

        ans_temp = - float('inf')
        for i in range(len(l)):
            val = 0
            for k in range(num):
                val += l[(i+k) % len(l)]
                ans_temp = max(ans_temp, val)

        d_sum = sum(l)
        if d_sum > 0:
            num = K // len(d_)
            ans_temp += num * d_sum
            # print(ans_temp, K, len(d_), K // len(d_), num, d_sum, d_sum * num)

    ans = max(ans, ans_temp)

print(ans)

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())
#    n = 5000
#    k = 1
    p = [int(i)-1 for i in ipt().split()]
#    p = [(i-1)%n for i in range(n)]
#    c = [10**9 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    ma = -10**18
    al = [False]*n
    for i in range(n):
        if al[i]:
            continue
        pts = []
        np = i
        for j in range(n):
            np = p[np]
            pts.append(c[np])
            al[np] = True
            if np == i:
                break
        ln = len(pts)
        jt = (k-1)%ln
        jt += 1
        sma = 0
        for jp in pts:
            sma += jp
        if sma > 0:
            nm = ((k-1)//ln)*sma
        else:
            nm = 0
        ma1 = -10**18
#        print(pts,al)
        for ji in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[ji-jj]
#                print(i,j,j-jj,sm)
                if ma1 < sm:
                    ma1 = sm
        ma1 += nm
        if ma < ma1:
            ma = ma1
#        print(ma)

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
arr = list(range(1, n+1))
res = max(c[1:])
if k <= n:
    for i in arr:
        tmp = []
        tmp_res = 0
        cnt = 0
        while cnt < k:
            i = p[i]
            tmp_res += c[i]
            cnt += 1
            res = max(res, tmp_res)
            if i in tmp:
                break
            tmp.append(i)
else:
    tmp_ = []
    for i in arr:
        if i in tmp_:
            continue
        tmp_.append(i)
        tmp = []
        tmp_res = 0
        cnt = 0
        while cnt < k:
            i = p[i]
            tmp_.append(i)
            tmp_res += c[i]
            cnt += 1
            res = max(res, tmp_res)
            if i in tmp:
                break
            tmp.append(i)

print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# ループを見つける(5000), 一周のスコアを確認
is_visit = [0 for _ in range(n)]
loop = []

def search(i, j):
    if is_visit[i] == 0:
        is_visit[i] = j
        l.append(i)
        search(p[i]-1, j)
    else:
        pass

loop_id = 1
for i in range(n):
    l = []
    search(i, loop_id)
    if len(l) != 0:
        loop.append(l)
        loop_id += 1
# print(loop)
# print(is_visit)
s_list = [0 for _ in range(len(loop))]
for i in range(len(s_list)):
    l = loop[i]
    s = 0
    for j in range(len(l)):
        s += c[l[j]]
    s_list[i] = s

ans = [0 for _ in range(n)]
for i in range(n):
    # i からはじめて最大スコア
    l = loop[is_visit[i]-1] # 所属するループ
    tmp1 = 0 # ループによるスコア
    tmp_k = k
    s = s_list[is_visit[i]-1]
    if s > 0 and k > 2*len(l):
        # 回るほどお得で一周より回れる
        tmp1 += s*(tmp_k//len(l)-1)
        tmp_k -= (tmp_k//len(l)-1)*len(l)
    elif s <= 0:
        tmp_k -= (tmp_k//len(l))*len(l)
        if tmp_k == 0:
            tmp_k = len(l)
    pointer = p[i]
    tmp2 = [c[pointer-1] for _ in range(tmp_k)] # 愚直に進んだ点数
    if tmp_k != 0:
        for j in range(1, tmp_k):
            # k回目までの累積和で最大を求める
            pointer = p[pointer-1]
            tmp2[j] = tmp2[j-1] + c[pointer-1]
    # print(i, l, s, tmp_k, tmp1, tmp2)
    if len(tmp2) != 0:
        ans[i] = tmp1 + max(tmp2)
    else:
        ans[i] = tmp1
# print(ans)
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
pp = (0,) + tuple(map(int, input().split()))
cc = (0,) + tuple(map(int, input().split()))

xpp = []
xcc = []
for i in range(1, n + 1):
    f = False
    for j in range(len(xpp)):
        if i in xpp[j]:
            f = True
            break
    if f:
        continue

    xp = []
    xc = []
    x = i
    while x not in xp:
        xp.append(x)
        xc.append(cc[x])
        x = pp[x]
    xpp.append(xp)
    xcc.append(xc)

ans = float('-inf')
for i in range(len(xpp)):
    pk = k
    a = sum(xcc[i])
    if a > 0:
        pf = pk // len(xpp[i])
        a *= pf
        pk -= pf * len(xpp[i])
    else:
        a = 0
    
    maxxcc = max(xcc[i])
    if maxxcc < 0:
        ans = max(ans, maxxcc)
    else:
        nxcc = len(xcc[i])
        xcc[i] += xcc[i]
        ma = 0
        for y in range(nxcc):
            t = 0
            for x in range(min(pk, nxcc)):
                t += xcc[i][x + y]
                ma = max(ma, t)
        ans = max(ans, a + ma)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=[int(_) - 1  for _ in input().split()]
C=list(map(int,input().split()))
end_flag=[0]*N
def calc(pos):
  X = [-1 for _ in range(N)]
  X2 = [-1 for _ in range(N)]
  k=0
  p=pos
  score=0
  ans=-1000000000
  X[p]=0
  X2[p]=0
  while k<K:
    p=P[p]
    score+=C[p]
    k+=1
    if X[p]!=-1:
      move_skip=max((K-k)//(k-X[p])-1,0)
      score+=(score-X2[p])*move_skip
      k+=move_skip*(k-X[p])
      
    X[p]=k
    X2[p]=score
    ans=max(score,ans)
  last_p=p
  p=i
  end_flag[i]=1
  while end_flag[p]==0:
    p=P[p]
    score-=C[p]
    last_p=P[last_p]
    score+=C[p]
    ans=max(score,ans)
    end_flag[p]=1
    

  return ans
final_ans=-10000000


for i in range(N):
  if end_flag[i]:continue
  final_ans=max(calc(i),final_ans)
  p=i
  
print(final_ans)

Submission status: Wrong Answer

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

ans = - 10 ** 10
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt > k:
        continue
    if k - cnt < cnt:
        score_tmp = score
        for j in range(1, k - cnt + 1):
            score_tmp += c[nxt]
            ans = max(ans, score_tmp)
            #print("ans = ", ans, "score_tmp = ", score_tmp, "nxt = ", nxt, "c[nxt] = ", c[nxt])
            nxt = p[nxt]
    else:
        a = (k - cnt) // cnt
        score_tmp = score + score * a
        ans = max(ans, score_tmp)
        for j in range(1, (k - cnt) - a * cnt + 1):
            score_tmp += c[nxt]
            ans = max(ans, score_tmp)
            nxt = p[nxt]


#print("score:", score)

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

unvisited = set(range(N))
cycles = []
while unvisited:
    cycles.append([])
    start = unvisited.pop()
    cycles[-1].append(C[start])
    temp = P[start]-1
    while temp in unvisited:
        unvisited.remove(temp)
        cycles[-1].append(C[temp])
        temp = P[temp]-1

maxsum = -10 ** 9
for cycle in cycles:
    doublecycle = cycle*2
    Kdiv = (K-1) // len(cycle)
    Krem = (K-1) % len(cycle) + 1
    for i in range(Krem):
        for j in range(len(cycle)):
            if i and cycle[j] < 0: continue
            maxsum = max(maxsum,sum(doublecycle[j:j+i+1]))
    cyclesum = sum(cycle)
    if cyclesum > 0:
        maxsum = cyclesum * Kdiv + maxsum

print(maxsum)

Submission status: Wrong Answer

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


def solve(x):

    cnt = 0
    arr = [c[x]]
    start = p[x]
    nxt = p[x]
    flg = 0
    while cnt < n * 2 - 1:
        arr.append(c[nxt])
        nxt = p[nxt]
        cnt += 1
        if nxt == start and flg == 0:
            cycle = cnt
            flg = 1

    div, mod = divmod(k, cycle)

    ans = max(sum(arr[:cycle]) * div, 0)

    tmp = max(arr)

    for i in range(cycle * 2 - mod):
        for j in range(1, mod):
            tmp = max(tmp, sum(arr[i: j + 1]))

    return ans + tmp


q = list(range(n))

ans = -10000000000000
for i in range(n):
    ans = max(ans, solve(i))

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

LOOP=[]
checked=[False]*N
tmp=[0]
NEXT=P[0]-1
checked[0]=True
while False in checked:
    if checked[NEXT]:
        LOOP.append(tmp)
        tmp=[]
        NEXT=checked.index(False)
    else:
        tmp.append(NEXT)
        checked[NEXT]=True
        NEXT=P[NEXT]-1
LOOP.append(tmp)

ans=-float("inf")
for loop in LOOP:
    n=len(loop)
    score=[]
    for i in range(n):
        score.append(C[loop[i]])
    
    SUM=sum(score)
    score=score+score
    acc=[0]+list(accumulate(score))
    if SUM>0:
        m=K//n
        l=K-n*m
        tmp=SUM*m
        add=0
        for i in range(n+1):
            val=acc[i+l]-acc[i]
            add=max(add,val)
        tmp+=add
    else:
        tmp=-float("inf")
        for i in range(n):
            for j in range(1,min(n+1,K+1)):
                tmp=max(tmp,acc[i+j]-acc[i])
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):

    if K > N-1:
        temp_max = C[0]
        for i in range(N):
            score_i = ["er"]*N 
            score_i_max = [0]*N
            h = P[i]-1
            score_i[0] = C[h]
            score_i_max[0] = C[h]
            if h == i:
                j = 0
                break
            for j in range(1, N):
                h = P[h]-1
                score_i[j] = score_i[j-1] + C[h]
                score_i_max[j] = max(score_i[j-1], score_i[j])
                if h == i: break

            # print(score_i)
            mod_k = K % (j+1)
            rat_k = K //(j+1)
            if score_i[j] > 0:
                t = rat_k * score_i[j] + max(0,(score_i_max[mod_k-1]))
                temp_max = max(t, temp_max)
            else:
                temp_max = max(score_i_max[j], temp_max)

        print(temp_max)
    
    elif K <= N:
        score = [[0]*N for i in range(N)]
        temp_max = C[0]
        for i in range(N):
            h = i
            for j in range(1, K):
                h = P[h]-1
                score[i][j] = score[i][j-1] + C[h]
                temp_max = max(score[i][j], temp_max)
        print(temp_max)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -10**18
P = list(map(lambda x: x-1, P))

for i in range(N):
    visit = [False]*N
    now = i
    l = []
    visit[now] = True
    
    for j in range(N+10):
        nex = P[now]
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    su = sum(l)
    
    if su>0:
        if K>len(l):
            now = su*(K//len(l))
            rem = K-(K//len(l))*len(l)
            ans = max(ans, now)
        
            for j in range(rem):
                now += l[j]
                ans = max(ans, now)
        else:
            now = l[0]
            ans = max(ans, now)
            
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
    else:
        now = l[0]
        ans = max(ans, now)
        
        if K<len(l):
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
        else:
            for j in range(1, len(l)):
                now += l[j];
                ans = max(ans, now)

print(ans)

Submission status: Wrong Answer

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

loopcheck = [0]*N
As = []
for i in range(N):
    if loopcheck[i]==0:
        now = i
        A = []
        while loopcheck[now]==0:
            loopcheck[now]=1
            A.append(C[P[now]-1])
            now = P[now]-1
        As.append(A)
out = -1*10**10
for A in As:
    SA = sum(A)
    NA = len(A)
    B = A + A
    T = min(NA,K)
    outtmp = max(A)
    S = [0]
    kosu = 1
    for i in range(0,len(B)):
        S.append(S[-1]+B[i])
    for i in range(NA-1):
        for j in range(i+1,i+T):
            outtmp = max(outtmp,S[j]-S[i])
            if outtmp==S[j]-S[i]:
                kosu = j+1-i
    if SA>0:
        if kosu==NA:
            Y = K - (K//NA)*NA
            outtmpex = -10**10
            for i in range(NA-1):
                for j in range(i+1,i+Y+1):
                    outtmpex = max(outtmpex,S[j]-S[i])
            outtmp = SA*(K//NA)+outtmpex
        else:
            outtmp = outtmp+SA*((K-kosu)//NA)
    out = max(outtmp,out)
print(out)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
P = tuple(map(int, input().split()))
C = tuple(map(int, input().split()))

G = [{} for _ in range(N)]
for i, p in enumerate(P):
    G[i][p-1] = C[p-1]

K = min(10 ** 4, K)
ans = -(10 ** 9 + 1)
todo = deque()
for s in range(N):
    todo.clear()
    todo.extend((p, 1, c) for p, c in G[s].items())
    while todo:
        p, count, point = todo.popleft()
        ans = max(ans, point)
        if count == K:
            break
        for np, c in G[p].items():
            todo.append((np, count + 1, point + c))
print(ans)

Submission status: Wrong Answer

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

def li():
    return [int(x) for x in input().split()]


N, K = li()
P = [0] + li()
C = [0] + li()
max_scores = [-10**12] * (N+10)
for init_i in range(1, N+1):
    i = init_i
    # scores = [-10**12] * (K+10)
    # scores[0] = 0
    # for l in range(1, K+1):
    #     i = P[i]
    #     scores[l] = scores[l-1] + C[i]
    # scores[0] = -10**12
    # max_scores[i] = max(scores)
print(max(max_scores))

Submission status: Wrong Answer

Solution code:
def max_score(_l, n):
  _l = _l + _l
  if n == 0:
    return 0
  ans = -(10 ** 100)
  for i in range(1, len(_l) - 1):
    _l[i] += _l[i - 1]
  for i in range(1, len(_l) - 1):
    for j in range(1, min(n + 1, len(_l) - i)):
      ans = max(ans, _l[i + j] - _l[i])
  return ans

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
check = [False for i in range(n)]

ans = -(10 ** 100)
for i in range(n):
  if check[i]:
    continue
  _i = i
  l = []
  while not check[_i]:
    check[_i] = True
    _i = p[_i] - 1
    l.append(c[_i])
  if k % len(l) != 0:
    _ans = k // len(l) * max(0, sum(l))
    _ans += max_score(l, k % len(l))
  else:
    _ans = (k // len(l) - 1) * max(0, sum(l))
    _ans += max_score(l, len(l))
  ans = max(ans, _ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    P = LI()
    C = LI()

    if K<N:
        ans_max = 0
        for i in range(N):
            NP = i
            sumN = 0
            j = 0
            while True:
                        
                NP = P[NP-1]
                a = P[NP-1]
                sumN += C[a-1]

                ans_max = max([ans_max, sumN])

                j += 1
                if j >= K:
                    break
        ans = ans_max

    elif K>=N:
        j = 0
        NP = 1
        sumN = 0
        maxN = 0
        while True:
            NP = P[NP-1]
            a = P[NP-1]
            sumN += C[a-1]
            maxN = max([maxN, sumN])

            j += 1
            if j >= N:
                break               

        if sumN > 0:
            KNmax = 0
            for i in range(N):
                NP = i
                KNsum = 0
                j = 0
                while True:
                    NP = P[NP-1]
                    a = P[NP-1]
                    KNsum += C[a-1]
                    KNmax = max([KNmax, KNsum])

                    j += 1
                    if j >= K//N:
                        break
            ans = sumN*(K//N) + KNmax
        else:
            ans = maxN
        
    if ans == 0:
        ans = max(C)
    print(ans)


"""
    ans_max = 0
    for i in range(N):
        NP = i
        sumN = 0
        j = 0
        while True:
                    
            NP = P[NP-1]
            a = P[NP-1]
            sumN += C[a-1]

            ans_max = max([ans_max, sumN])

            j += 1
            if j >= K:
                break
"""
     

    
    

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def roop(i,K):
    isroop=False
    last=[-1]*N
    lastcnt=[-1]*N
    n=i
    last[n]=0
    lastcnt[n]=0
    roopp=-1#ループ1回のポイント
    cnt=0
    rs=-1#ループ開始
    maxp=-10**30
    point=0
    while(True):
        cnt+=1
        n=P[n]
        point+=C[n]
        maxp=max(maxp,point)
        if last[n]!=-1:
            roopp=point-last[n]
            syuki=cnt-last[n]#ループ周期
            isroop=True
            rs=n
            start=last[n]
            break
        last[n]=point
        lastcnt[n]=cnt
        if cnt==K:
            break
    if not isroop:
        return  maxp
    if roopp<0:
        return maxp
    K-=lastcnt[rs]
    roopcnt=K//syuki
    allpoint=(K//syuki)*roopp
    K%=syuki
    j=0
    n=rs
    point=0
    maxpp=0
    while(j<K):
        j+=1
        n=P[n]
        point+=C[n]
        maxpp=max(maxpp,point)
    stopp=0
    n,j=rs,0
    while(j<syuki):
        j+=1
        n=P[n]
        point+=C[n]
        stopp=max(stopp,point)
    
    if rs!=i:
        return max([start,start+allpoint,start+allpoint+maxpp,start+allpoint-roopp+stopp])
    else:
        if roopcnt>1:
            return max([allpoint,allpoint+maxpp,maxp])
        else:
            return max([allpoint,allpoint+maxpp,maxp])
        
        
        

N,K=map(int,input().split())
P=list(map(lambda x:int(x)-1,input().split()))
C=list(map(int,input().split()))

ans=-10**30
for i in range(N):
    r=roop(i,K)
    ans=max(ans,r)
print(ans)

Submission status: Wrong Answer

Solution code:
def loop(i, N, K, P, C):
  m = 1
  l = P[i]-1
  score = [C[i]]
  while l != i:
    score.append(C[l] + score[m-1]) 
    m += 1
    l = P[l]-1 
  return score

    
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = []
for i in range(N):
  score = loop(i, N, K, P, C)
  m = len(score)
  tmp = max(score)
  a = K // m 
  b = K - a*m
  tmp1 = score[m-1]*a 
  if b != 0:
    tmp2 = max(score[:b])
    if tmp2 > 0:
      tmp1 += tmp2
  tmp3 = max(tmp,tmp1)
  ans.append(tmp3)
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()))

max_score = -10**22
for i in range(N):
  score = 0
  count = 0
  index = []
  j = i
  n = 0
  for _ in range(N):
    j = P[j]-1
    index.append(i)
    count += C[j]
    n += 1
    if j == i:
      break
  k = K%n
  score = (K//n)*count
  if score < 0:
    score = 0
    if k == 0:
      k = 1
  max_v = -10**22
  v = 0
  for _ in range(k):
    j = P[j]-1
    v += C[j]
    max_v = max(max_v, v)
  max_score = max(max_score, score+max_v)

print(max_score)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
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))
    exit()

ans = 0
if k <= n:
    for i in range(n):
        score = 0
        prev = i
        for j in range(k):
            score += c[p[prev]-1]
            prev = p[prev]-1
            ans = max(ans, score)
else:
    s = deepcopy(c)
    shuuki = [1]*n
    for i in range(n):
        score = 0
        prev = i
        for j in range(n):
            if p[prev]-1 == i:
                break
            s[i] += c[p[prev]-1]
            prev = p[prev]-1
            shuuki[i] += 1
    for i in range(n):
        score = 0
        prev = i
        num = k//shuuki[i]
        for j in range(k%shuuki[i]):
            score += c[p[prev]-1]
            prev = p[prev]-1
        ans = max(ans, s[i]*num+score)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
input = sys.stdin.readline


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

ans=-1*(10**10)
for i in range(N):
    tmp=0
    pos=i
    gpos=i
    count=0
    while count<K:    
        #print(pos,P[pos])
        tmp+=C[P[pos]-1]
        if tmp>ans:
            ans=tmp
        
        
        pos=P[pos]-1
        count+=1
        if pos==gpos:
            divide=K//count-1
            tmp+=tmp*divide
            count+=count*divide
        
        

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

datas = [int(i) for i in input().split(" ")]
N = datas[0]
K = datas[1]

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

sumData = []
nextData = copy.deepcopy(P)
tempData = []
total = [0] * N
cnt = 0
maxData = -1000000000

while cnt < K:
    cnt += 1
    for i in range(N):
        sumData.append(C[nextData[i] - 1])
        tempData.append(nextData[nextData[i] - 1])
        total[i] += sumData[i]

    nextData = copy.deepcopy(tempData)
    sumData = []
    tempData = []
    print(nextData)
    print(total)
    print("max:" + str(cnt) + " is " + str(max(total)))
    if maxData < max(total):
        maxData = max(total)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline

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

kouho = []

used = [False] * (n)
for i in range(n):
    if used[i]:
        continue
    now = i
    cnt = 0
    res = 0
    route = []
    while True:
        if used[now]:
            break
        route.append(C[P[now] - 1])
        used[now] = True
        nex = P[now] - 1
        cnt += 1
        res += C[nex]
        now = nex
    kouho.append((res / cnt, res, cnt, route))
kouho.sort(reverse=True)

ans = -(10 ** 20)
for _, res, cnt, route in kouho:
    temp1 = 0
    num = len(route)
    if k >= cnt:
        if res > 0:
            temp1 += res * (k // cnt)
            cnt = k % cnt
        else:
            cnt = num
    temp2 = -(10 ** 20)
    route += route
    ACR = list(accumulate([0] + route))
    for i in range(num):
        for j in range(1, cnt + 1):
            temp3 = ACR[j + i] - ACR[i]
            temp2 = max(temp2, temp3)
            # print((i, j), temp3)
    temp1 += temp2
    # print(temp1)
    ans = max(ans, temp1)
print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  # print(l)
  # print(roop)

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1]))
    else:
      ans=max(ans,max(l[i][1:K+1]))
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans1=c*l[i][roop_count]
        k=K%roop_count
        _ans1+=max(l[i][1:k+1]+[0])
        if c>=1:
          _ans2=(c-1)*l[i][roop_count]
          _ans2+=max(l[i][1:])
          ans=max(ans,_ans1,_ans2)
        else:
          ans=max(ans,_ans1)

  return ans

# main()
print(main())