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 -*-
import sys 
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
P = [0] + list(map(int,readline().split()))
C = [0] + list(map(int,readline().split()))

check = [False]*(N+1)
data = []
for i in range(1,N+1):
    if check[i]:
        continue
    cnt = 0
    point = []
    n = i
    while True:
        if check[n]:
            break
        check[n] = True
        cnt += 1
        point.append(C[n])
        n = P[n]
    data.append((cnt,point))

S = len(data)
INF = 10**31
ans = -INF
for i in range(S):
    cnt,point = data[i]
    a = K // cnt
    b = K % cnt
    sum_point = sum(point)
    if sum_point > 0:
        tmp = sum_point * a
    else:
        tmp = 0
    if tmp == 0 and a >= 1:
        tt = -INF
        P = [0]+point+point
        SS = list(accumulate(P))
        for k in range(1,cnt):
            for i in range(cnt):
                t = SS[i+k]-SS[i]
                tt = max(t,tt)
        tmp += tt
    else:
        tt = -INF
        P = [0]+point+point
        SS = list(accumulate(P))
        for k in range(1,b+1):
            for i in range(cnt):
                t = SS[i+k]-SS[i]
                tt = max(t,tt)
        tmp += tt
    ans = max(tmp,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()))

ans = min(C)
for i in range(N) :
    log = [i+1]
    t = 0
    b = 0
    a = i+1
    while len(log) == len(set(log)) :
        b += C[P[a-1]-1]
        ans = max(ans,b)
        t += 1
        log.append(P[a-1])
        a = P[a-1]
        if t == K :
            break
    if b >= 1  :
       d = K%t
       e = K//t
       f = b*e
       for _ in range(d) :
           f += C[P[a-1]-1]
           a = P[a-1]
           ans = max(ans,f)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**20

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        if K==1:
            output=max(output,C[P[i]-1])
            continue

        while True:
            count+=1
            now=P[now]-1

            if now in st:
                count-=1
                break
    
            lst[i][count]=lst[i][count-1]+C[now]
            st.add(now)
            
            if count==K:
                break


        if lst[i][count]>0:
            if K%count:
                s=lst[i][count]*(K//count)+max(0,max(lst[i][1:K%count+1]))
            else:
                s=lst[i][count]*(K//count)
        else:
            s=max(lst[i][1:count+1])
        
        output=max(output,s)

    print(output)

main()

Submission status: Wrong Answer

Solution code:
import numpy

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_P_list = list()
        organaized_C_list = list()
        organaized_P_list.append(now)
        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_P_list.append(now)
                organaized_C_list.append(C_list[now])
                
        all_organaized_P_list.append(organaized_P_list)
        all_organaized_C_list.append(organaized_C_list)
        
#print(all_organaized_P_list)
#print(all_organaized_C_list)

#整理したループ毎に得点を求める
def get_loop_ans(organaized_C_list):
    #ループしない場合の得点を求める
    ans = max(organaized_C_list)
    res = numpy.cumsum(organaized_C_list + organaized_C_list)
    #print(res)
    for i in range(0,len(organaized_C_list)):
        for j in range(1,len(organaized_C_list)):
            temp_ans = res[i+j] - res[i]
            #print(i,j,temp_ans)
            ans = max(ans,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=map(int, input().split())
P_ls=list(map(int, input().split()))
C_ls=list(map(int, input().split()))


ans=-99999999999999999999

for i in range(1,N+1):
	C=[]
	s=set(range(1,N+1))
	while True:
		try:
			C+=[C_ls[i-1]]
			s.remove(i)
			i=P_ls[i-1]
		except:
			break
	
	anscand=C[0]
	anscand_sum=C[0]
	print(C)
	flag=0
	for i in C[1:min(K,len(C))]:
		anscand_sum+=i
		if anscand_sum>=anscand:
			anscand=anscand_sum
			flag=i
	
	if anscand_sum>0 and K>len(C):
		anscand+=(K-flag)//len(C)*anscand_sum
	
	ans=max(ans,anscand)

print(ans)

Submission status: Wrong Answer

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

seen = [0] * N

ans = -10**20

for i in range(N):
    if not seen[i]:
        seen[i] = 1
        loop = [C[i]]
        while True:
            i = P[i]
            if seen[i]:
                break
            seen[i] = 1
            loop.append(C[i])
        L = len(loop)
        loop = loop + loop
        loop = [0] + list(accumulate(loop))
        if loop[L] <= 0:
            move = min(L, K)
            for i in range(L):
                for j in range(1, move + 1):
                    ans = max(ans, loop[i + j] - loop[i])
        else:
            continue
            if K > L:
                div, mod = divmod(K, L)
                tmp = div * loop[L]
                move = min(mod, L)
                if move:
                    for i in range(L):
                        for j in range(1, move + 1):
                            ans = max(ans, tmp + loop[i + j] - loop[i])
                else:
                    ans = max(ans, tmp)
                tmp = (div - 1) * loop[L]
                move = L
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
            else:
                move = K
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

def main():
    inf=float("inf")
    n,k=map(int,input().split())
    plst=list(map(int,input().split()))
    clst=list(map(int,input().split()))
    sm=-inf

    seen=[0]*n
    for i in range(n):
        if seen[i] : continue
        pos=i
        work=[]
        while not seen[pos]:
            seen[pos]=1
            work.append(clst[pos])
            pos=plst[pos]-1
        nwork=len(work)
        work=[0]+list(accumulate(work))

        sm_add=0
        numcut=min(nwork,k)
        if work[-1]>0 and k>=nwork:
            sm_add=work[-1]*(k//nwork)
            numcut=k%nwork
        
        for i in range(nwork):
            for j in range(i,i+numcut):
                if j<nwork :
                    smwork=work[j+1]-work[i]
                else :
                    smwork=work[nwork]-work[i]+work[j-nwork+1]
                if smwork+sm_add>sm : sm=smwork+sm_add


    print(sm)

main()

Submission status: Wrong Answer

Solution code:
nk=input("").split(" ")
n=int(nk[0])
k=int(nk[1])
lisp=input("").split(" ")
lisc=input("").split(" ")
p=[]
c=[]
plis=[]
for i in range(n):
    p+=[int(lisp[i])-1]
    c+=[int(lisc[i])]
    plis+=[1]
cycle=[]
cyp=[]
cyc=[]


for i in range(n):
    
    
        np=p[i]
        cys=c[i]
        
        cyct=[c[i]]
        while(np!=i):
            
            cys+=c[np]
            
            cyct+=[cys]
            np=p[np]
        cycle+=[cys]
        
        cyc+=[cyct]
if(max(cycle)<=0):
    m=max(cyc[0])
    
    for i in cyc:
        if(m<max(i)):
            m=max(i)
    print(m)
elif(k>n+2):
    m=[cycle[0],len(cyc[0])]
    t=[0]
    
    for i in range(n):
        if(m[0]*len(cyc[i])<cycle[i]*m[1]):
            m=[cycle[i],len(cyc[i])]
            t=[i]
        elif(m[0]*len(cyc[i])==cycle[i]*m[1]):
            t+=[i]
    lll=len(cyc[t[0]])
    for i in t:
        if(lll<len(cyc[i])):
            lll=len(cyc[i])
    syou=(k-1)//lll
    amari=(k-1)%lll
    ten=syou*cycle[i]
    tama=0
    
    for i in t:
        syo=amari//len(cyc[i])
        if(tama<syo*cycle[i]+cyc[i][amari%len(cyc[i])]):
            tama=syo*cycle[i]+cyc[i][amari%len(cyc[i])]
            
    print(ten+tama)
else:
    t=0
    for i in range(n):
        cc=c[i]
        ccc=[cc]
        np=p[i]
        
        for kws in range(k):
                cc+=c[np]
                
                np=p[np]
                ccc+=[cc]
        
        if(t<max(ccc)):
            t=max(ccc)
    print(t)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**18
m = 10**9 + 7

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

    ans = - INF
    used = [0] * N
    candidate = []

    for i in range(N):
        if used[i]: continue
        now = i
        used[i] = 1
        tmp = [i]
        # print(tmp,P[i])
        
        while P[now]-1 not in tmp:
            used[P[now]-1] = 1
            tmp.append(P[now]-1)
            now = P[now]-1
        
        candidate.append(tmp)

    # print(candidate)
    # 各ループごとにK回以内で回して最大値を調べていく
    for tmp in candidate:
        M = len(tmp)
        accumT = []
        for t in tmp:
            accumT.append(C[t])
        accumT = [0] + list(accumulate(accumT*2))
        # print(accumT,K,M)

        if K < M:# ループにならない
            res = - INF
            for i in range(2*M+1):
                for j in range(i+1,2*M+1):
                    if j - i > K: 
                        break
                    res = max(res,accumT[j]-accumT[i])
            ans = max(ans,res)
            # print(M,res)
        else:
            SUM = accumT[M]
            # print(SUM)
            if SUM > 0:
                addition = SUM * (K//M)
                res = - INF
                for i in range(2*M+1):
                    for j in range(i+1,2*M+1):
                        if j - i > K%M: 
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res+addition)
                # print(ans,res,addition)
            else:
                # M回までやる
                res = - INF
                for i in range(2*M+1):
                    for j in range(i+1,2*M+1):
                        if j - i > M:
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
cs = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
# print(n, k, ps, cs)

ans = -float('inf')
done = []

if max(ps) <= 0:
    ans = max(ps)

else:
    for start in range(1, n + 1):  # 最初の場所
        # 終わってるやつ
        if start in done:
            continue

        now = start
        flag = True
        points = []

        while now != start or flag:
            done.append(now)
            flag = False
            now = cs[now - 1]
            points += [ps[now - 1]]

        if max(points) <= 0:
            ans = max(ans, max(points))

        else:
            x, y = k // len(points), k % len(points)
            # print('x, y', x, y)
            p_sum = sum(points) if sum(points) > 0 else 0

            for i in range(len(points)):
                for j in range(y + 1):
                    tmp_ans = p_sum * x + sum((points + points)[i:i + j])
                    ans = max(ans, tmp_ans)
                # print(ans, tmp_ans)

            # print(start, points, 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()))
c = [1] * N
s = [C[P[i]-1] for i in range(N)]
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        s[i] += C[P[j]-1]
        if  c[i] <= K:
            if s[i] > m[i][c[i]-1]:
                m[i][c[i]] = s[i]
            else:
                m[i][c[i]] = m[i][c[i]-1]
ans = min(C)
for i in range(N):
    if s[i] > 0:
        if  s[i] * (K//c[i]) + m[i][K%c[i]] > ans:
            ans = s[i] * (K//c[i]) + m[i][K%c[i]]
    else:
        if max(m[i][1:c[i]]) > ans:
            ans = max(m[i][1:c[i]])
print(ans)

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 > 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())
k = k+1
p = [0] * n
c = [0] * n
a = [0] * (n+1)
ans = [0] * n

p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    s = 0
    x = i
    roop = 0
    for j in range(n):
        s += c[x]
        a[j+1] = s
        x = p[x] - 1
        if x == i:
            roop = j + 1
            break
    if s <= 0:
        ans[i] = max(a[1:min(roop, k)])
    else:
        if k%roop  == 0:
            ans[i] = max(s * (k // roop) , s * (k // roop - 1) + max(a))
        else:
            ans[i] = max(s * (k // roop) + max(a[:k % roop]), s * (k // roop - 1) + max(a))
print(max(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n,k=map(int,input().split())

p=list(map(int,input().split()))
p=[q-1 for q in p]
c=list(map(int,input().split()))


loopcnt=[]
visited=set([])

for i in range(n):
    first=p[i]
    if first in visited:
        continue
    now=first
    vs=set([now])
    for j in range(n):
        now=p[now]
        if now in visited:
            continue
        visited.add(now)
        if now in vs:
            loopcnt.append(vs)
            continue
        vs.add(now)
        
lll=[]
for item in loopcnt:
    point=0
    for v in item:
        point+=c[v]
        
    lll.append((list(item),point))
print(lll)

anslist=[]

for sss,ppp in lll:
    # print(sss,pspp)
    ls=len(sss)
    if ppp<=0:
        ans=max(c)
        for i in range(ls):
            now=sss[i]
            point=0
            for j in range(k):
                now=p[now]
                point+=c[now]
                ans=max(ans,point)
        anslist+=(ans),
    else:
        ans=max(c)
        for i in range(ls):
            now=sss[i]
            point=0
            for j in range(k%ls):
                now=p[now]
                point+=c[now]
                ans=max(ans,point)
        anslist+=(ans+ppp*(k//ls)),
        
print(max(anslist))

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:
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
            gpos=10**10
        

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 = max(C)
for i in range(N):
    s = P[i]-1
    l = [C[i]]
    while s != i:
        l.append(C[s])
        s = P[s]-1
    if sum(l) > 0:
        c = K//len(l)*sum(l)
        n = K%len(l)
        ans = max(ans,c)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,c+x)
    else:
        n = min(N,K)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,x)
            
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list((map(lambda a: int(a)-1, input().split())))
C = list(map(int,input().split()))
checked = [True] * N
scores = []
res = - 10 ** 60
for i in range(N):
    if checked:
        current = i
        score = []
        while checked[current]:
            checked[current] = False
            Next = P[current]
            score.append(C[Next])
            current = Next
        if len(score) > 0:
            scores.append(score)
for s in scores:
    l = len(s)
    Sum = sum(s)
    s = s+s
    wa = [0] * (l+1)
    kukan = K % l
    loop = K // l
    wa = [0] * (l+kukan+1)
    for i in range(l+kukan):
        wa[i+1] = wa[i] + s[i]
    Max = - 10 ** 60
    for i in range(l):
        Max = max(Max,wa[i+kukan]-wa[i])
    print(Sum,loop,Max)
    res = max(res, Sum * loop + Max)
print(res)

Submission status: Wrong Answer

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, k = sp()
p = L()
arr = L()
answer = -(10 ** 20)
for start in range(n):
    s = set()
    moves = []
    temp = 0
    i = start+1
    while True:
        i = p[i-1]
        if i in s:
            if not moves:
                moves.append(arr[i-1])
            else:
                moves.append(moves[-1] + arr[i-1])
            break
        s.add(i)
        if not moves:
            moves.append(arr[i-1])
        else:
            moves.append(moves[-1] + arr[i-1])
    temp = k % len(moves)
    new2 = 0
    for j in range(temp):
        new2 = max(new2, moves[j])
    if moves:
        answer = max(answer, max(moves))
    move = k // len(moves)
    for i in moves:
        if i < 0:
            answer = max(answer, i)
        else:
            new1 = move * i
            answer = max(answer, new1 + new2)
out(answer)

Submission status: Wrong Answer

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

ans = -10**9
loops = {}
if 5000 < K:
    for i in range(1,N+1):
        p = i
        k = K
        max_score = -10**9
        score = 0
        visited = set([p])
        visited_lst = [p]
        score_lst = [0]
        while 0 < k:
            score += C[P[p]]
            max_score = max(max_score,score)
            score_lst.append(score)
            p = P[p]
            k -= 1
            if p in visited:
                if p in loops:
                    if 0 < loops[p][0]:
                        score += loops[p][0]*(k//loops[p][1])
                        k %= loops[p][1]
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
                else:
                    idx = visited_lst.index(p)
                    l = len(score_lst)-1-idx
                    for j in range(idx,l):
                        loops[visited_lst[j]] = [score-score_lst[idx],l]
                    if 0 < score-score_lst[idx]:
                        score += (score-score_lst[idx])*(k//l)
                        k %= l
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
            else:
                visited.add(p)
                visited_lst.append(p)
        # print(max_score)
        max_score = max(max_score,score)
        ans = max(ans,max_score)
    # print(loops)
else:
    for i in range(1,N+1):
        p = i
        k = K
        max_score = -10**9
        score = 0
        while 0 < k:
            score += C[P[p]]
            max_score = max(max_score,score)
            p = P[p]
            k -= 1
        ans = max(ans,max_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()))
D=[0 for i in range(N+1)]
D[0]=2
ANS=-10**20
for z in range(1,N+1):
    if D[z]==0:
        D[z]=1
        X=[[0,z]]
        for i in range(N*2):
            if D[X[-1][1]]!=3:
                D[X[-1][1]]+=1
                X.append([X[-1][0]+P[C[X[-1][1]]],C[X[-1][1]]])
            else:
                break
        #print(X)
        roop=(len(X)-1)//2
        
        Roop=max(0,X[roop][0])
        #print(roop)
        k=K%roop
        f=0
        if k==0:
            f=1
            k=roop
        cnt=0
        for i in range(1,k+1):
            for j in range(roop):
                #print(i+j,j)
                cnt=max(cnt,X[i+j][0]-X[j][0])
                #print(cnt)
        #print(cnt)
        ANS=max(ANS,(K//roop)*(Roop)+cnt)
for i in range(1,N+1):
    if P[i]==i:
        if C[i]*K>ANS:
            ANS=C[i]*K
if max(P[1:])<0:
    print(max(P[1:]))
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
l=[]
vis=[0]*n
ans=0
flag=0
for i in range(n):
    vis=[0]*n
    q=[i]
    c1=[c[i]]
    t=0
    while True:
        a=q[-1]
        vis[a]=1
        if vis[p[a]-1]==1:
            t=p[a]-1
            break
        else:
            q.append(p[a]-1)
            c1.append(c[p[a]-1])
    m=0
    m1=-c1[0]
    flag1 = 0
    for j in range(len(q)):
        if q[j]==t or j>k:
            break
        m1+=c1[j]
        if m1 >= 0:
            flag1 += 1
        m=max(m1,m)
    t1=m1
    if j<=k:
        for j1 in range(j,min(len(q),k+1)):
            m1 += c1[j1]
            m = max(m1, m)
            if m1>=0:
                flag1+=1
        s=sum(c1[j:])
        t1+=((k+1-j)//(len(q)-j))*s
        if t1 >= 0:
            flag1 += 1
        m1=0
        m2=0
        for j1 in range(j,j+(k+1-j)%(len(q)-j)):
            m1+=c1[j1]
            m2=max(m1,m2)
        t1+=m2
        if t1 >= 0:
            flag1 += 1
        m=max(m,t1)
    flag=max(flag,flag1)
    ans=max(ans,m)
if flag<2:
    ans=-INF
    for i in range(n):
        ans=max(ans,c[p[i]-1])
out(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()))
last=k%n
by_last=k//n
sum1=sum(c)
cnt=0

for i in range(n):
  ans=sum1*by_last
  nxt=i
  for j in range(last):
    nxt=p[nxt]-1
    cnt=max(ans,cnt)
    ans+=c[nxt]
  
print(cnt)