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 = list(map(int,input().split()))
C = list(map(int,input().split()))
L = []
S = set()
for i in range(N):
    if i in S:
        continue
    L.append([C[i]])
    S.add(i)
    tmp = i
    Next = P[i] - 1
    while Next != tmp:
        S.add(Next)
        L[-1].append(C[Next])
        Next = P[Next] - 1

ans = 0

for l in L:
    score = 0
    k = len(l)
    SUM = sum(l)
    l = [0] + l + l
    if SUM > 0:
        score = SUM * (K // k)
        m = K % k
    else:
        m = k
    for i in range(2 * k):
        l[i+1] += l[i]
    for i in range(k):
        for j in range(i+1, i+m+1):
            ans = max(ans, score + l[j] - l[i])

if ans == 0:
    ans = max(C)

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()))
INF = 10 ** 18


def solve(v):
    res = []
    set_ = set()
    tot = 0
    while True:
        nxt_v = p[v] - 1
        cost = c[nxt_v]
        if nxt_v not in set_:
            set_.add(nxt_v)
            tot += cost
            res.append(tot)
            v = nxt_v
        else:
            break
    return res, tot


ans = -INF

# 1回移動する場合
for v in range(n):
    ans = max(c[v], ans)

for v in range(n):
    res, tot = solve(v)
    if tot < 0:
        for i in range(min(k, len(res))):
            ans = max(res[i], ans)
    else:
        lap, rem = divmod(k, len(res))
        tmp = lap * tot
        if lap > 0:
            ans = max(ans, tmp)
        for i in range(min(rem, len(res))):
            ans = max(tmp + res[i], ans)
print(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()))
memo = []
ans = -1e16
A = [[0 for _  in range(K+1) ] for _ in range(N+1)]

for i in range(1,N+1):
  cnt = 0
  sumn = 0
  now = i
  for j in range(K):
    now = P[now]
    cnt += 1
    sumn += C[now]
    ans = max(sumn,ans)
    A[i][cnt] = sumn
    if now == i:
      break
  memo.append((cnt, sumn))

for i in range(1,N+1):
  cnt, sumn = memo[i-1]
  if sumn < 0:
    continue
  if cnt >= K:
    continue
  sumn = sumn * (K // cnt)
  cnt = K % cnt 
  ans = max(ans, sumn + A[i][cnt])

  #for i in range(1,N+1):
  #if P[i] == i:
  #  ans = max(ans, C[i] *K)
    
#print(memo)
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 i in range(n):
	K=k
	score=0
	pre_score=0
	visit=[0]*n
	now=i
	cnt=0
	while visit[now]==0:
		cnt+=1
		visit[now]=1
		now=p[now]-1
		pre_score+=c[now]
		if cnt!=1:
			score=max(score,pre_score)
		else:
			score=pre_score
		K-=1
		if K==0:
			break
	ans=max(score,ans)
	if K==0:
		continue
	loop=[0]
	NOW=now
	#NOWはループ元
	for j in range(n):
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if NOW==now:
			break
	pre_score+=max(loop[-1],0)*(K//(len(loop)-1))
	K%=(len(loop)-1)
	pre_score+=max(loop[:K+1])
	score=max(score,pre_score)
	ans=max(ans,score)
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())
    p = [int(i)-1 for i in ipt().split()]
    c = [int(i) for i in ipt().split()]
    ma = -10**27
    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+1
        nm = 0
        sm = sum(pts)
#        print(pts)
        if sm > 0:
            nm = (k//ln)*sm
            if jt == ln:
                nm -= sm
        ma1 = -10**27
        for j in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[j-jj]
                if ma1 < sm:
                    ma1 = sm
        if ma < nm+ma1:
            ma = nm+ma1
#        print(ma)

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil



def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
from math import inf

for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -inf
    for i in range(n):
        st = set()
        st.add(i)
        cur = i
        x = []
        while p[cur]-1 not in st:
            cur = p[cur]-1
            st.add(cur)
            x += [c[cur]]
        x += [c[p[cur]-1]]

        pre = [0]*len(x)
        pre[0] = x[0]
        for i in range(1, len(x)):
            pre[i] = pre[i-1] + x[i]
        if len(x) >= k:
            ans = max(ans, max(pre[:k]))
        else:
            kc = k
            anss = 0
            if pre[-1] > 0:
                anss += pre[-1]*(kc // len(x))
                kc = kc % len(x)
                if kc:
                    anss += max(pre[:kc])
                ans = max(ans, anss)
            else:
                ans = max(ans, max(pre))
    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)
d = {}
for i in range(N):
    if i in d:
        continue
    s = P[i]-1
    d[s] = 0
    l = [C[i]]
    while s != i:
        l.append(C[s])
        s = P[s]-1
        d[s] = 0
    c = K//len(l)*sum(l)
    l += l
    if c>0:
        r = K%(len(l)//2)
        c_l = [0]*(len(l)+1)
        ans = max(ans,c)
        for i in range(len(l)):
            c_l[i] = c_l[i-1]+l[i]
        r = K%(len(l)//2)
        for j in range(len(l)//2):
            for k in range(r):
                s = c_l[j+k]-c_l[j-1]
                ans = max(ans,s+c)
    else:
        c_l = [0]*(len(l)+1)
        for i in range(len(l)):
            c_l[i] = c_l[i-1]+l[i]
        r = min(len(l)//2,K)
        for j in range(len(l)//2):
            for k in range(r):
                s = c_l[j+k]-c_l[j-1]
                ans = max(ans,s)

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()))
l = []
for i in range(n):
    cur = i
    l2 = []
    score = 0
    cnt = 0
    while True:
        if p[i] - 1 in l2:
            score += c[p[i] - 1]
            break
        l2.append(i)
        score += c[p[i] - 1]
        i = p[i] - 1
        cnt += 1
    l.append([score, cnt + 1])
A = []
for i in range(n):
    ans = 0
    if l[i][0] < 0:
        ans = c[i]
    else:
        ans = l[i][0] * (k // l[i][1])
        cnt = 0
        cur = i
        for j in range(k % l[i][1]):
            cnt += c[p[cur] - 1]
            cur = p[cur] - 1
        ans += cnt
    A.append(ans)
print(max(A))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

from collections import defaultdict

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    score = []
    c_sum = [0]
    s = set()
    while cnt < k:
        s.add(now)
        score.append(c[now])
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k == cnt:
        ans = max(ans, sum(score), max(c_sum[1:]))
    else:
        temp = sum(score)
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += sum(score[:q])
        ans = max(ans, temp, max(c_sum[1:]))
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()))

def solve(start):
    loopcnt = 0
    loopsum = 0
    reached = [0]*n
    scoremax = [-10**20]
    scoresum = 0
    ans = 0
    now = start
    while True:
        reached[now] = 1
        nxt = P[now]-1
        loopcnt += 1
        loopsum += C[now]
        scoresum += C[now]
        scoremax.append(max(scoremax[-1], scoresum))
        if reached[nxt]:break
        now = nxt
    if loopsum < 0 or loopcnt > k:
        ans = scoremax[min(k,len(scoremax)-1)]
    else:
        ans = max(loopsum * (k//loopcnt) + max(0,scoremax[k%loopcnt]),max(scoremax[1:]))#,max(scoremax[1:]))
    return ans #- C[start]
ans = -10**20
for i in range(n):
    ans = max(ans, solve(i))
    # print(solve(i))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A=[[0]*n]
Cur=[int(i)+1 for i in range(n)]
L=[0]*n
for _ in range(n):
  N=[0]*n
  for i in range(n):
    N[i]=A[-1][i]+C[P[Cur[i]-1]-1]
    Cur[i]=P[Cur[i]-1]
    if L[i]==0 and Cur[i]==i+1:
      L[i]=_+1
  A.append(N)
ans=max(A[1])
for i in range(n):
  ct=0
  loop=L[i]
  loop_ct=A[loop][i]
  rem=-float("inf")
  if k>loop and loop_ct>0:
    ct+=(k//loop)*loop_ct
    rem=0
    for j in range(k%loop):
      rem=max(rem,A[j+1][i])
    ans=max(ans,rem+ct)
  else:
    for j in range(min(k,n)):
      rem=max(rem,A[j+1][i])
    ans=max(ans,rem)
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()))

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)
  return ans
final_ans=-10000000
for i in range(N):
  final_ans=max(calc(i),final_ans)
print(final_ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def solve(P, C, K, Checked, s):
    B = []
    B.append( C[s])
    now = P[s]
    Checked[s] = True
    while now != s:
        B.append(C[now])
        Checked[now] = True
        now = P[now]
    sumB = sum(B)
    L = len(B)
    accB = [0] + list( accumulate(B))
    ret = B[0]
    for i in range(L):
        for j in range(i+1,L+1):
            if j - i > K:
                continue
            if accB[j] - accB[i] > ret:
                ret = accB[j] - accB[i]
    accRB = [0] + list( accumulate(B[::-1]))
    # print(B, accB, accRB)
    # print(ret)
    for i in range(L+1):
        for j in range(L+1):
            if i==0 and j==0:
                continue
            if i + j > K:
                continue
            t = accB[i] + accRB[j]
            if sumB > 0:
                t += (K-(i+j))//L*sumB
            if t > ret:
                ret = t
                print(i,j,ret)
    return ret
        
    
def main():
    N, K = map( int, input().split())
    P = list( map( lambda x: int(x)-1, input().split()))
    C = list( map( int, input().split()))
    Checked = [False]*N
    ans = C[0]
    for s in range(N):
        if Checked[s]:
            continue
        ans_s = solve(P, C, K, Checked, s)
        if ans_s > ans:
            ans = ans_s
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n,k = l_in()
P = l_in()
C = l_in()

s = min(k,n)

res = -(10**10)
for start in range(n):
    j = start
    current = 0
    tmp = -(10**10)
    for i in range(1, k+1):
        j = P[j]-1
        current += C[j]
        tmp = max(tmp, current)
        if j == start:
            if current > 0:
                s = k%i
                add = current*(k//i)

                j = start
                current = 0

                for i2 in range(1, s+1):
                    j = P[j]-1
                    current += C[j]
                    tmp = max(tmp, current+add)
            break
                
    res = max(tmp, res)
    
print(res)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,K = MI()
P = LI()
C = LI()

from itertools import accumulate

flag = [0]*N
ans = max(C)
for i in range(N-1):
    if flag[i] != 0:
        continue
    A = [C[i]]
    flag[i] = 1
    a = i
    j = P[i]-1
    while j != i:
        A.append(C[j])
        flag[j] = 1
        j = P[j]-1
    a = len(A)
    s = 0
    if sum(A) > 0:
        s = sum(A)*(K//a)
    else:
        for i in range(a):
            if A[i] >= 0:
                break
        else:
            s = max(A)
    r = K % a
    if r == 0:
        r = a
    A = [0] + A + A
    S = list(accumulate(A))
    m = 0
    for i in range(a):
        for k in range(1,r+1):
            b = S[i+k] - S[i]
            m = max(m,b)
    s += m
    ans = max(ans,s)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
P = np.array([*map(int, input().split())], dtype=int) - 1
C = np.array([*map(int, input().split())], dtype=int)

V = np.zeros(N, dtype=int)
score = -1e9
for _ in range(K):
  V = C + V[P]
  score = max(score, V.max())
print(score)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
used = [-1]*N 
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    Next = fr[cur]
    Next -= 1
    for chi in [Next]:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(P,i,-1,index,li)
    index += 1
    renketu.append(li)
ren = renketu
n = len(ren)
ans = -1*10**20
for i in range(n):
    li = ren[i]
    nn = len(li)
    val = 0
    nnow = li[0]
    for jj in range(nn):
        val += C[P[nnow]-1]
        nnow = P[nnow]-1
    if val <= 0:
        for k in range(nn):
            now = li[k]
            v = 0
            for j in range(nn):
                v += C[P[now]-1]
                ans = max(ans,v)
                now = P[now]-1
    else:
        vvv = val*(K//nn)
        nnn = K % nn
        for k in range(nn):
            now = li[k]
            v = 0
            for j in range(nnn):
                v += C[P[now]-1]
                now = P[now]-1
                ans = max(ans,vvv+v)


print(ans)

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


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(min(n,k)):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    #print(a, b)
    ans = max(b)
    for i in range(n):
        co = b[i]
        i = a[i]
    #    print(i, co)
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    #        print(i, co)
            ans = max(ans, co)
    #    print()

print(ans)

Submission status: Wrong Answer

Solution code:
R = lambda: map(int, raw_input().split())
n, k = R()
p, c = R(), R()
p = [x - 1 for x in p]
vis = [False] * n
ans = max(c)

for i in xrange(n):
    if vis[i]:
        continue
    t = [c[i]]
    j = p[i]
    while j != i:
        vis[j] = True
        t.append(c[j])
        j = p[j]

    m = len(t)
    s = sum(t)

    ta = 0
    tk = k
    if s > 0:
        ta += s * (tk / m)
        tk %= m

    t = t + t
    j = -1
    v = 0
    mv = max(t)
    for i in xrange(len(t)):
        if v < 0:
            j = i - 1
            v = 0
        v += t[i]
        if i - j > tk:
            j += 1
            v -= t[j]
        mv = max(mv, v)
    ans = max(ans, ta + mv)

    if tk < k:
        mv2 = mv
        for i in xrange(len(t)):
            if v < 0:
                j = i - 1
                v = 0
            v += t[i]
            if i - j > k:
                j += 1
                v -= t[j]
            mv2 = max(mv2, v)
        ans = max(ans, mv)
print ans

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

ans = -float('inf')

for start in range(N):
    loop_len = 1
    pos = P[start]
    score = C[pos]
    scores = [score]
    while pos != start:
        loop_len += 1
        pos = P[pos]
        score += C[pos]
        scores.append(score)
    loops = (K-1)//loop_len
    cand = max(0, score * loops)
    cand += max(scores[:(K-loop_len * loops)])
    ans = max(ans, cand)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return

def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i,p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0]*N for _ in range(31)]
    score_doubling = [[0]*N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2,31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
            score_doubling[k][i] = score_doubling[k-1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[0,-inf] for i in range(N)]
    locate = [[i,i] for i in range(N)]
    ans = max(C)

    if ans<0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            #print(score[i],locate[i])
            score[i][1] += score_doubling[k + 1][locate[i][1]]
            if score[i][1] < score[i][0]:
                locate[i][1] = locat_doubling[k + 1][locate[i][1]]
        if K&(1<<k)>0:
            for i in range(N):
                score[i][0] += score_doubling[k+1][locate[i][0]]
                locate[i][0] = locat_doubling[k+1][locate[i][0]]
    for s in score:
        ans = max(ans,s[0],s[1])
    print(ans)
    return

def examE():
    R, C, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(min(n,k)):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    print(a, b)
    ans = max(b)
    for i in range(n):
        co = b[i]
        i = a[i]
    #    print(i, co)
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    #        print(i, co)
            ans = max(ans, co)
    #    print()

print(ans)

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()))
res = max(c)

def solve(d):
    ret = res
    sz = len(d)
    for i in range(sz):     # iから
        tmp = 0
        for j in range(min(k, sz)):
            tmp += d[(i + j) % sz]
            ret = max(ret, tmp)
    sm = sum(d)
    a,b = divmod(k, sz)
    if sm > 0 and a > 0:
        ret = max(ret, a * sm)
        for i in range(sz):
            tmp = 0
            for j in range(b):
                tmp += d[(i + j) % sz]
                ret = max(ret, a * sm + tmp)
    return ret

done = [False for _ in range(n)]
for i in range(n):
    if done[i]:
        continue
    d = []
    cur = i
    while 1:
        done[cur] = True
        d.append(c[cur])
        cur = p[cur]
        if cur == i:
            break
    res = max(res, solve(d + d))

print(res)

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 = -1e9
for i in range(N):
  cost = 0
  S = []
  M = -1e9
  x = P[i] - 1
  X = -1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if cost > M:
      M = cost
      X = l
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    M += cost * ((K - X) // l)
  ans = max(ans, M)
print(ans)

Submission status: Wrong Answer

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

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

#高々N回で1周する
class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1] * n
 
    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
 
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u == v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u # size[u] <= size[v]
        self.size[v] += self.size[u]
        self._par[u] = v
 
    def same(self, u, v):
        return self.root(u) == self.root(v)

uf = UnionFind(n)
for i in range(n):
    uf.unite(i, p[i])

ans = []
for i in range(n):
    ite = uf.size[uf.root(i)]
    #print(ite)
    if k > ite:
        memo = [0 for _ in range(ite+1)]
        tmp = i
        for j in range(ite):
            tmp = p[tmp]
            memo[j+1] = memo[j] + c[tmp]
        div = k // ite
        mod = k % ite
        #print(memo)
        if memo[-1] <= 0:
            ans.append(max(memo[:mod+1]))
        else:
            m = max(memo[1:])
            ans.append(max(max(memo[:mod+1]) + div * memo[-1], m))
    
    else:
        memo = [0 for _ in range(ite+1)]
        tmp = i
        for j in range(k):
            tmp = p[tmp]
            memo[j+1] = memo[j] + c[tmp]
        ans.append(max(memo[1:]))
        

print(max(ans))