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 = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]
INF = float("INF")
ans = -INF
for i in range(n):
    flag = [False]*n
    now = i
    cnt = 0
    j = 0
    mlst = [-INF]*n
    m = -INF
    while not flag[now]:
        flag[now] = True
        now = p[now]
        cnt += c[now]
        m = max(cnt,m)
        mlst[j] = m
        j += 1
    # print(mlst)
    q,r = divmod(k,j)
    if q == 0: res = mlst[r-1]
    elif cnt >= 0: res = max(cnt*q+mlst[r-1],cnt*(q-1)+mlst[j-1])
    else: res = mlst[j-1]
    # print("res",res)
    ans = max(ans,res)
print(ans)

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>2*n):
    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:
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]]

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

        # ans = sum(points) * (k // len(points)) + sum(points[:k % len(points)])
        # print(k // len(points), k % len(points))

        ans = max(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()))
ans=-10**10
for st in range(N):
	now = st+1
	temp=[0]
	while(P[now-1] != st+1):
		temp.append(temp[-1]+C[P[now-1]-1])
		now = P[now-1]
	temp.append(temp[-1]+C[P[now-1]-1])
	if len(temp)<=K+1:
		ans=max(ans, max(temp[1:K+1]))
		continue
	if temp[-1]<=0:
		ans = max(ans, (max(temp[1:])))
	else:
		t=temp[-1]*(K//(len(temp)-1))
		t+=max(temp[:1+K%(len(temp)-1)])
		ans=max(ans, t)
		
print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import accumulate
import sys
sys.setrecursionlimit(1000000)

def func(x):
    return x - 1

def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    flag = False
    for i in range(N):
        if C[i] >= 0:
            flag = True
    if not flag:
        print(max(C))
        exit()
    cand = []
    visited = [False] * N
    for i in range(N):
        if not visited[i]:
            Q = deque([i])
            tmp = []
            while Q:
                x = Q.pop()
                visited[x] = True
                v = P[x]
                if not visited[v]:
                    Q.append(v)
                    tmp.append(C[v])
            tmp.append(C[v])
            cand.append(tmp+tmp)
    ans = 0
    for item in cand:
        tmp_score = 0
        S = sum(item) // 2
        L = len(item) // 2
        D = [0] + list(accumulate(item))
        if S > 0:
            cnt = K % L
            for l in range(L):
                for j in range(cnt):
                    tmp = D[l+j+1] - D[l] 
                    tmp_score = max(tmp_score, tmp)
            tmp_score += (K // L) * S
            ans = max(ans, tmp_score)
        else:
            cnt = min(K,L)
            for l in range(L):
                for j in range(cnt):
                    tmp = D[l+j+1] - D[l] 
                    tmp_score = max(tmp_score, tmp)
            ans = max(ans, tmp_score)

    print(ans)
            




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

N, K = mi()
P = li()
C = li()
ans = -float('inf')

for i in range(N):
    ind = i
    his = []
    while True:
        ind = P[ind] - 1
        his.append(C[ind])
        if ind == i:
            his = list(accumulate(his))
            #print(his)
            L = len(his)
            if K > L:
                if his[-1] > 0:
                    if not K%L:
                        ans = max(ans, his[-1] * (K//L))
                    else:
                        ans = max(ans, max(his[:K%L]) + his[-1] * (K//L), his[-1] * (K//L))
                else:
                    ans = max(ans, max(his))
            else:
                ans = max(ans, max(his[:K]))
            break

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
used = [0]*n
c = list(map(int,input().split()))
ans = -float("INF")
def calc(x):
    l = []
    now = x
    score = 0
    while used[now] == 0:
        used[now] = 1
        l.append(c[now])
        now = p[now]-1
    S = sum(l)
    le = len(l)
    if S > 0 and k > le:
        score += (k//le-1)*S
        mod = k%le
        now = -float("INF")
        for i in range(le):
            cal = 0
            for j in range(le):
                if j == mod:
                    now = max(now,cal+S)
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    else:
        mod = min(le,k)
        now = -float("INF")
        for i in range(le):
            cal = 0
            for j in range(mod):
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    
    

for i in range(n):
    if used[i] == 0:
        ans = max(ans,calc(i))
print(ans)

Submission status: Wrong Answer

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

c = [0] * N
s = [0] * N
ignore = []
for i in range(N):
    if i in ignore:
        continue
    p = P[i]
    c[i] = 1
    s[i] = C[p]
    temp = []
    while p != i:
        temp += [p]
        p = P[p]
        s[i] += C[p]
        c[i] += 1
    for j in temp:
        c[j] = c[i]
        s[j] = s[i]
    ignore += temp

ans = -10**10
for i in range(N):
    s1 = K//c[i]*s[i]
    p = P[i]
    s2 = [C[p]]
    for j in range(1, K%c[i]):
        p = P[p]
        s2 += [s2[-1]+C[p]]
    s2 = max(s2)
    if K//c[i] == 0:
        ans = max(ans, s2)
    else:
        ans = max([ans, s1 + s2, s2])
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    N, K = list(map(int, input().split()))
    P = list(map(lambda x: int(x)-1, input().split()))
    C = list(map(int, input().split()))
    scores = [0 for _ in range(N)]
    for i in range(N):
        pos = P[i]
        i_scores = []
        score = 0
        for j in range(N):
            score += C[pos]
            i_scores.append(score)
            if i == pos:
                break
            pos = P[pos]
        finalscore = (K//len(i_scores))*score
        finalscore += i_scores[K%len(i_scores)-1] if K%len(i_scores) != 0 else 0
        i_scores_max = max(i_scores) if K >= len(i_scores) else max(i_scores[:K])
        scores[i] = max(finalscore, i_scores_max)
    print(max(scores))


if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
# print(C)
ans = -10**16
hoge = K
for i in range(N):
    K = hoge
    start_point = i
    visited = set()
    ruisekiwa = [0]
    tmp = 0
    for j in range(min(K, N)):
        # とりあえず回数の許す限り次のマスへ行く
        # ループしているなら
        if start_point in visited:
            break
        visited.add(start_point)
        ruisekiwa.append(ruisekiwa[-1]+C[P[start_point]])
        start_point = P[start_point]
    # ループが可能な場合
    if K > len(visited):
        # 可能な限りループする（最後の1回はループしない）
        tmp += ruisekiwa[-1]*(K//len(visited)-1)
        K %= len(visited)  # 余ったループ回数
        # 左側はもう1ループして，余力のループを行った場合．
        # 右側は最後の1ループを理想的なところで止めた場合
        # print("K %= N のあとの : ", K)
        if K != 0:
            tmp += max(ruisekiwa[-1]+max(ruisekiwa[1:K+1]), max(ruisekiwa[1:]))
        else:
            tmp += max(ruisekiwa)
        ans = max(ans, tmp)
    else:
        ans = max(ans, max(ruisekiwa[1:]))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

ans = c[0]

for i in range(n):
  #print('試行')
  np = i
  point = 0
  j = 0
  while(j<k):
    #print(j, np, point)
    j += 1
    np = p[np] - 1
    if j > 1 and np == p[i] - 1: #1週してポイントが1以上なら
      if point > 0:
      	#print('roop')
      	#print(point, j)
      	point = point*((k//(j-1)) - 1)
      	j = (j-1)*((k//(j-1)) - 1)
      	while(j<k):
        	j+=1
        	np = p[np]-1
        	point += c[np]
        	#print(j,point)
        	if point > ans:
          		ans = point
    break
    point += c[np]
    if point > ans:
      ans = point
   
    

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root_rec(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def root(self, n):
        stack = []
        while n >= 0:
            stack.append(n)
            n = self.parent[n]
        m = stack.pop()
        while stack:
            self.parent[stack.pop()] = m
        return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups(self):
        if isinstance(self.parent,list):
            return list(filter(lambda i: self.parent[i]<0, range(len(self.parent))))
        else: # self.parent: defaultdict
            return list(filter(lambda i: self.parent[i]<0, self.parent.keys()))
 
    def groups_num(self):
        return len(self.groups())

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, K = inpl()
P = list(map(lambda x: x-1,inpl()))
C = inpl()

uf = UnionFind(N)
for i in range(N):
    uf.merge(i, P[i])

ans = C[0]
for g in uf.groups():
    L = uf.size(g)
    cycle = C[g]
    p = P[g]
    while p != g:
        cycle += C[p]
        p = P[p]
    q, r = K//L, K % L
    if cycle > 0:
        score = q * cycle
    else:
        score = 0

    s = g
    v = C[g]
    for _ in range(L):
        u = score
        t = s
        for i in range(1,L+1):
            u += C[t]
            t = P[t]
            if i > r:
                if q > 0 and cycle > 0:
                    u -= cycle
                elif q > 0 and cycle <= 0:
                    pass
                elif q == 0:
                    continue
            if u > v:
                v = u
        s = P[s]

    if v > ans:
        ans = v

print(ans)

Submission status: Wrong Answer

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

flag = [True] * N

ans = -1000000000
for i in range(N):
    if flag[i]:
        x = i
        l = 0
        A = []
        while(flag[x]):
            flag[x] = False
            l += 1
            A.append(C[x])
            x = P[x]
        B = [0]
        for j in range(l):
            B.append(B[-1] + A[j])
        for j in range(l):
            B.append(B[-1] + A[j])
        
        for j in range(l):
            for k in range(min(l,K)):
                ans = max(ans,B[j+k+1]-B[j])
        sA = sum(A)
        if sA > 0:
            for j in range(l):
                for k in range(K%l):
                    ans = max(ans,sA*(K//l)+B[j+k+1]-B[j])
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**9
for i in range(n):
    scores = [0]
    seen = set([i])
    now = i
    loop = False
    for _ in range(k):
        now = p[now]-1
        scores.append(c[now])
        if now in seen:
            loop = True
            break
        seen.add(now)
    for i in range(len(scores)-1):
        scores[i+1] += scores[i]
    tmp = max(scores[1:])
    ans = max(ans, tmp)
    if not loop or scores[-1]<=0:
        continue
    tmp = scores[-1]*(k//(len(scores)-1))
    rem = k%(len(scores)-1)
    tmp += max(scores[:rem+1])
    ans = max(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()))
ans = []
for i in range(n):
    visit = [-1 for i in range(n)]
    cou = 0
    visit[i] = 0
    kar = []
    now = i
    while True:
        cou += 1
        if cou > k:
            break
        nex = p[now] - 1
        if visit[nex] == -1:
            visit[nex] = cou
            if kar:
                kar.append(kar[-1] + c[nex])
            else:
                kar.append(c[nex])
            now = nex
        elif visit[nex] != -1:
            if kar:
                lokz = cou
                losu = kar[-1] + c[nex]
                if losu > 0:
                    if k % lokz == 0:
                        kar.append(losu * (k//lokz))
                    elif k % lokz != 0:
                        tyu = losu * (k//lokz)
                        tyu += max(kar[:(k%lokz)])
                        kar.append(tyu)
            else:
                if c[nex] >= 0:
                    kar.append(c[nex]*k)
                elif c[nex] < 0:
                    kar.append(c[nex])
            break
    ans.append(max(kar))
print(max(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 63


def run():
    N, K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    C = list(map(int, sysread().split()))
    P = [p-1 for p in P]

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    #print(loops)
    #print(loopSums)
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] < 0 or K <= len(loop)-2:
                j = i
                max_val = -INF
                while True:
                    if j >= len(loop):j=0
                    if i != j and j:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    if i == j: break
                ans = max(ans, max_val)
                continue


            rest = K
            #if K <= len(loop) - i - 1:
            #    val += loopSum[i + K - 1] - loopSum[i]
            #    ans = max(ans, val)
            #    continue
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            val += (rest // (len(loop)-1)) * loopSum[-1]
            rest = rest % (len(loop) - 1)
            val += max(loopSum[:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
L = [0]*N
Max = -10**9
for i in range(N):
    if L[i] != 0:
        continue
    else:
        c = 0
        L[i] = 1
        c += C[i]
        a = P[i] - 1
        Cs = [c]
        Ds = [c]
        l = 1
        while a != i:
            c += C[a]
            Ds.append(C[a])
            a = P[a]-1
            L[a] = 1
            l += 1
            Cs.append(c)
        if c > 0:
            m = -10**9
            k = K % l
            for i in range(1,k+1):
                for j in range(l):
                    if j + i >= l:
                        M = Cs[l-1] - Cs[j] + Cs[i+j-l]
                    else:
                        M = Cs[j+i]-Cs[j]
                    if M > m:
                        m = M
            x = K // l
            max0 = c*x+m
        else:
            if K >= l:
                A = [0]*l
                A[0] = Ds[0]
                for i in range(1,l):
                    A[i] = min([A[i-1]+Ds[i],Ds[i]])
                max0 = c - A[l-1]
                if max0 == 0:
                    max0 = max(Ds)
            else:
                m = -10**9
                k = K
                for i in range(1,k+1):
                    for j in range(l):
                        if j + i >= l:
                            M = Cs[l-1] - Cs[j] + Cs[i+j-l]
                        else:
                            M = Cs[j+i]-Cs[j]
                        if M > m:
                            m = M
                max0 = m

    if Max < max0:
        Max = max0
print(Max)

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)

        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:
def max_score(_l, n):
  _l = _l + _l
  if n == 0:
    return 0
  ans = -(10 ** 100)
  for i in range(1, n + 1):
    _ans = -(10 ** 100)
    _tmp = 0
    for j in range(i):
      _tmp += _l[j]
    _ans = max(_ans, _tmp)
    for j in range(i, len(_l) - 1):
      _tmp += _l[j]
      _tmp -= _l[j - i]
      _ans = max(_ans, _tmp)
    ans = max(ans, _ans)
  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:
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
        if k==0:
            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)
if max(P[1:])<0:
    print(max(P[1:]))
else:
    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 ** 100
for i in range(n):
    d = [-1] * n
    d[i] = 0
    res = 0
    t = i
    cnt = 1
    while d[p[t] - 1] == -1:
        cnt += 1
        d[p[t] - 1] = d[t] + 1
        t = p[t] - 1
        res += c[t]
    t = p[t] - 1
    res += c[t]
    K = max(0, k - d[t])
    rt = 0
    q = i
    for i in range(min(d[t], k)):
        q = p[q] - 1
        rt += c[q]
        ans = max(ans, rt)
    q = t
    co = 0
    for i in range(min(K, cnt)):
        q = p[q] - 1
        co += c[q]
        ans = max(ans, co)
    re = 0
    r = 0
    for i in range(K % cnt):
        t = p[t] - 1
        r += c[t]
        re = max(r, re)
    ans = max(ans, res * (K // cnt) + rt + re)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    N, K = map(int, input().split())
    Ps = list(map(lambda x: int(x)-1, input().split()))
    Cs = list(map(int, input().split()))

    cycless = [[] for _ in range(N)]
    useds = [0] * N
    for no in range(N):
        if useds[no]: continue
        x = no
        while True:
            useds[x] = 1
            cycless[no].append(Cs[x])
            x = Ps[x]
            if x == no:
                break

#    for no in range(N):
#        print('# no:', no, '/ cycless[no]:', cycless[no], file=sys.stderr)

    ans = -float('inf')
    for no in range(N):
        if not cycless[no]: continue
        L = len(cycless[no])
        accCycles = list(accumulate([0]+cycless[no]+cycless[no]+cycless[no]))
        sumC = sum(cycless[no])
#        print('\n# no:', no, '/ sumC:', sumC, file=sys.stderr)
        if sumC > 0:
            num = K//L
            if num > 1:
                num -= 1
                score = -float('inf')
                K = L + K%L
                for M in range(0, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
                score += sumC * num
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        elif sumC == 0:
            num = K//L
            if num > 1:
                score = -float('inf')
                K = 2*L
                for M in range(0, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        else:
            score = -float('inf')
            K = K if K <= L else L
            for M in range(1, K+1):
                for st in range(L):
                    s = accCycles[st+M] - accCycles[st]
                    if s > score:
                        score = s
        if score > ans:
            ans = score
#        print('# no:', no, '/ score:', score, file=sys.stderr)

    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
temp = [int(x) for x in input().split()]
p = [-1]
for x in temp:
    p.append(x)
c = [-1]
temp = [int(x) for x in input().split()]
 
for x in temp:
    c.append(x)
 
# print(p)
# print(c)
# print()
ans = -int(1e12)
for i in range(1, N+1):
    ans = max(ans, c[p[i]])

for i in range(1, N+1):
    # print("i: ", i)
    visited = [False] * (N+1)
    cur_sum = 0
    cur_box = i
    l = 0
    k = K
    while k > 0:
        if visited[cur_box]:
            break
        cur_sum += c[p[cur_box]]
        ans = max(ans, cur_sum)
        visited[cur_box] = True
        cur_box = p[cur_box]
        k -= 1
        l += 1
        # print(cur_sum)
    if k != 0 and cur_sum > 0:
        cur_sum = (cur_sum * (K // l))
        ans = max(ans, cur_sum)
        k = K % l
        while k > 0:
            cur_sum += c[p[cur_box]]
            ans = max(ans, cur_sum)
            cur_box = p[cur_box]
            k -= 1
            # print(cur_sum)
    
    # print("i:", i , ", sum:", cur_sum)
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 = -float("INF")
for i in range(n):
    pi = p[i]
    x = c[pi-1]
    a = x
    for j in range(k-1):
        pi = p[pi-1]
        a = max(a,x+c[pi-1])
        x += c[pi-1]
    ans = max(ans,x)
print(ans)