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: Runtime Error

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:])))
	elif K%(len(temp)-1)!=0:
		t=temp[-1]*(K//(len(temp)-1))
		t+=max(temp[:1+K%(len(temp)-1)])
		ans=max(ans, t)
    else:
        t=temp[-1]*(K//(len(temp)-1))-temp[-1]
        t+=max(temp)
        ans=max(ans,t)
		
print(int(ans))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = c[0]
jud = []
for i in range(n):
    if i not in jud:
        l = []
        j = p[i] - 1
        while j not in jud:
            jud.append(j)
            l.append(c[p[j]-1])
            j = p[j] - 1
        le = len(l)
        l *= (k//le +2)
        for ii in range(le):
            val = l[ii]
            ans = max(ans,val)
            for cnt in range(ii+1, ii + k):
                val += l[cnt]
                ans = max(val, ans)

print(ans)

Submission status: Runtime Error

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

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
#print(F)
#print(I)
#print(CN)
ans=-(10**9)*2
for i in range(N):
  cnt=C[i]
  #動かす回数が一周に満たない時
  if K+1<I[i]:
    d=0
    nex=i
    for j in range(K+1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<0:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    acnt=cnt
    bcnt=C[i]
    syuukai=(K+1)//I[i]
    nokori=(K+1)%I[i]
    syuukai-=1
    nokori+=I[i]
    b+=syuukai*CN[i]
    d=0
    nex=i
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      bcnt=max(d,bcnt)
    cnt=max(acnt,bcnt)
  ans=max(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
P = [-1]+list(map(int,input().split()))
C = [-1]+list(map(int,input().split()))
visited = [True]+[False]*n
circles = []
for i in range(1,n+1):
    if not visited[i]:
        pre = i
        visited[i]=True
        s = [C[i]]
        while P[i] != pre:
            s.append(C[P[i]])
            visited[P[i]] = True
            i = P[i]
        circles.append((s,sum(s)))
# print(circles)
anslist = []

for ci in circles:
    ci_ans = 0
    if ci[1] > 0:
        ci_ans += ci[1]*(k//len(ci[0]))
    acc = list(accumulate(ci[0]*2))
    maxi = -10**9
    for start in range(len(ci[0])):
        ci2 = (ci[0]*2)[start:(start+len(ci[0]))]
        point = 0
        for i in range(min(k%len(ci[0]),len(ci[0]))):
            point += ci2[i]
            maxi = max(maxi,point)
    ci_ans += maxi
    anslist.append(ci_ans)
print(max(anslist))

Submission status: Runtime Error

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=sum1*by_last
if sum1<0:
  for i in range(n):
    ans=0
    nxt=i
    for j in range(n):
        nxt=p[nxt]-1
        ans+=c[nxt]
        cnt=max(ans,cnt)
  print(cnt)
  sys.exit()
else:
  for i in range(n):
    ans=sum1*by_last
    nxt=i
    for j in range(last):
      nxt=p[nxt]-1

      ans+=c[nxt]
      cnt=max(ans,cnt)
  print(cnt)

Submission status: Runtime Error

Solution code:
def read_input():

    n, k = map(int, input().split())
    p = list(map(lambda x : int(x) - 1, input().split()))
    c = list(map(int, input().split()))

    return n, k, p, c

def solve_i(i, k, p, c, n):
    
    points = None
    maxi = None

    s = set()
    i = p[i]
    while i not in s:
        
        s.add(i)
        if points is None:
            points = [c[i]]
        else:
            points.append(points[-1] + c[i])

        if maxi is None:
            maxi = points[-1]
        else:
            maxi = max(maxi, points[-1])

        i = p[i]

    if points[-1] <= 0:
        return maxi
    else:
        cycles = k // len(points)
        remainder = k % len(points)

        potential = points[-1] * cycles + max(points[:remainder])

        return max(maxi, potential)



def solve(n, k, p, c):

    maxi = []
    for i in range(n):
        maxi.append(solve_i(i, k, p, c, n))

    return max(maxi)        


print(solve(*read_input()))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
ans = -10**20
for start in range(N):
    now = P[start]
    tmp = C[now]
    ans = max(ans, tmp)
    c = K-1
    k = 1
    kick = [tmp]
    step = None
    kick_tmp = None
    while c > 0 and k < N:
        now = P[now]
        tmp += C[now]
        ans = max(ans, tmp)
        c -= 1
        k += 1
        kick.append(tmp)
        if now == start:
            step = k
            kick_tmp = tmp
            break
    if step != None:
        ans = max(ans, kick_tmp*(K//step)+max(kick[:K%step]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, K = map(int, input().split())
P = list(map(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))
weight = []
visited = [0]*N
ans = - float('inf')

def dfs(u, cnt, w):
  w += [C[u]]
  visited[u] = 1
  v = P[u]
  if visited[v] != 1:
    dfs(v, cnt+1, w)
  else:
    return

for i in range(N):
  weight = []
  visited = [0]*N
  dfs(i, 1, weight)
  print(i, weight)
  if len(weight) > K:
    weight = weight[:K]
    tmp = 0
    for j in range(K-1):
      weight[j+1] += weight[j]
    tmp = max(weight)
    ans = max(ans, tmp)
  else:
    s = sum(weight)
    if s > 0:
      tmp = (K//len(weight))*s
      weight = weight[:K%len(weight)]
      for j in range(len(weight)-1):
        weight[j+1] += weight[j]
      tmp += max(weight)
      ans = max(ans, tmp)
    else:
      tmp = 0
      for j in range(len(weight)-1):
        weight[j+1] += weight[j]
      tmp = max(weight)
      ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
ans = -10**20
for start in range(N):
    now = P[start]
    tmp = C[now]
    ans = max(ans, tmp)
    c = K-1
    k = 1
    if S > 0 and K > N:
        ans = max(ans, tmp+S*(K//N))
    kick = [tmp]
    step = None
    kick_tmp = None
    while c > 0 and k < N:
        now = P[now]
        tmp += C[now]
        ans = max(ans, tmp)
        c -= 1
        k += 1
        kick.append(tmp)
        if now == start:
            step = k
            kick_tmp = tmp
            break
    if K > N:
        ans = max(ans, kick_tmp*(K//step)+max(kick[:K%step]))
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
ans = -10**15
S = sum(C)
for start in range(N):
    now = P[start]
    tmp = C[now]
    ans = max(ans, tmp)
    c = K-1
    k = 1
    if S > 0 and K > N:
        ans = max(ans, tmp+S*(K//N))
    kick = [tmp]
    step = None
    kick_tmp = None
    while c > 0 and k < N:
        now = P[now]
        tmp += C[now]
        ans = max(ans, tmp)
        c -= 1
        k += 1
        kick.append(tmp)
        if now == start:
            step = k
            kick_tmp = tmp
            break
    if K > N:
        ans = max(ans, kick_tmp*(K//step)+max(kick[:K%step]))
print(ans)

Submission status: Runtime Error

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

Sss = [[0]*N for _ in range(K)]
Sss[0] = Cs
if max(Cs) < 0:
    print(max(Cs))
else:
    for i in range(1, K):
        X = 0
        for j in range(N):
            X = Ps[X]
            Sss[i][j] = Sss[i-1][j] + Cs[X]
        X += 1
    print(max(map(max,Sss)))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
P = [int(i) - 1 for i in input().split()]
C = list(map(int, input().split()))

memo = [[]  for i in range(n)]
for i in range(n):
    memo[i].append(C[i])
    j = P[i]
    while True:
        memo[i].append(memo[i][-1] + C[j])
        j = P[j]
        if j == i:
            memo[i].append(memo[i][-1] + C[j])
            break

circles = [memo[i][-1] - memo[i][0] for i in range(n)]

ans = -1e10
for i  in range(n):
    le = (len(memo[i]) - 1)
    m = k // le
    if circles[i] > 0 and m > 0:
        k_ = k % le
        alt = max(memo[i][:k_]) + circles[i] * m
        ans = max(alt, ans)
        alt =  max(memo[i][:-1]) + circles[i] * (m-1)
        ans = max(alt, ans)
    else:
        alt =  max(memo[i][:-1])
        ans = max(alt, ans)
print(ans)

Submission status: Runtime Error

Solution code:
def mss(l,length,k):
    x = 0
    for i in range(length):
        temp = 0
        for j in range(i,i+k-1):
            temp += l[j]
            if temp > x:
                x = temp
    return x

if __name__ == '__main__':
    N,K = map(int,input().split())
    P = [int(p)-1 for p in input().split()]
    C = [int(c) for c in input().split()]
    #閉路の探索
    L_close = []
    Done = [0] * N
    for i in range(N):
        if Done[i] == 1:
            continue
        score = []
        #start
        Done[i] = 1
        #Next
        p = P[i]
        Done[p] = 1
        score.append(C[p])
        while p != i:
            p = P[p]
            Done[p] = 1
            score.append(C[p])
        L_close.append(score)
    #それぞれの閉路に対して
    ans = 0
    for l in L_close:
        total = sum(l)
        length = len(l)
        l = l + l
        if total <= 0:
            ans = max(ans,mss(l,length,K))
        else:
            ans = max(ans,total * (K//length) + mss(l,length,K%length))
    print(ans)

Submission status: Runtime Error

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

max_score = -1000000000
for i in range(n):
    period = 0
    count = 0
    start = p[i]-1
    now = start
    for _ in range(k):
        period += c[now]
        now = p[now]-1
        count += 1
        if now == start:
            div = k // count
            break
    count = 0
    now = start
    for _ in range(k%count):
        score += c[now]
        max_score = max(max_score,score)
        now = p[now]-1

if period < 0:
    print(max_score)
else:
    print(max_score + period * div)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = c[0]
jud = []
for i in range(n):
    if i not in jud:
        l = [c[p[i]-1]]
        j = p[i] - 1
        jud.append(p[i]-1)
        while j != i:
            l.append(c[p[j]-1])
            j = p[j] - 1
            jud.append(j)
        le = len(l)
        l *= (k//le +2)
        for ii in range(le):
            val = l[ii]
            ans = max(ans,val)
            for cnt in range(ii+1, ii + k):
                val += l[cnt]
                ans = max(val, ans)

print(ans)

Submission status: Runtime Error

Solution code:
import queue
N,K=map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
check = [0]*N
ans = -10**13
for i in range(N):
	if check[i] == 0:
		cur = i
		k = K
		check2 = [0]*N
		p = 0
		a = 0
		anst = 0
		while check2[cur] != 1:
			check2[cur] = 1
			check[cur] = 1
			cur = P[cur]-1
			anst += C[cur]
			p += 1
		if p < k:
			a = k//p
			b = k%p
		for l in range(1,p+1):
			ans2 = 0
			cur2 = i
			q = queue.Queue()
			for j in range(l):
				cur2 = P[cur2]-1
				ans2 += C[cur2]
				q.put(cur2)
			ans = max(ans2,ans)
			if l <= b:
				ans = max(ans,ans2+a*anst)
			else:
				ans = max(ans,ans2+(a-1)*anst)
			for j in range(p-1):
				o = q.get()
				ans2 -= C[o]
				cur2 = P[cur2]-1
				ans2 += C[cur2]
				q.put(cur2)
				ans = max(ans2,ans)
				if l <= b:
					ans = max(ans,ans2+a*anst)
				else:
					ans = max(ans,ans2+(a-1)*anst)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
maxsc = 0
for s in range(1,n+1):
  x = s
  sc = [0]
  i = 0
  while i<k:
    x = p[x]
    sc.append(sc[i]+c[x])
    i += 1
  print(sc)
  maxsc = max(maxsc, max(sc))
print(maxsc)

Submission status: Runtime Error

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

import collections

def flatten(l):
    for el in l:
        if isinstance(el, collections.abc.Iterable) and not isinstance(el, (str, bytes)):
            yield from flatten(el)
        else:
            yield el

Sss = [[0]*N for _ in range(K)]
Sss[0] = Cs
for i in range(1, K):
    X = 0
    for j in range(N):
        X = Ps[X]
        Sss[i][j] = Sss[i-1][j] + Cs[X]
    X += 1
print(max(flatten(Sss)))

Submission status: Runtime Error

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

def roop(i):
  if p[i]-1 not in visit:
    roopcnt.append(roopcnt[-1]+c[p[i]-1])
    global rooph
    rooph+=1
    visit.append(i)
    roop(p[i]-1)
  
l=[]
for i in range(n):
  visit=[i]
  roopcnt=[c[i]]
  rooph=1
  roop(i)
  a=(k+1)%rooph
  b=(k+1)//rooph
  if a==0:
    l.append(b*roopcnt[-1]-roopcnt[0])
  else:
    l.append(b*roopcnt[-1]+roopcnt[a-1]-roopcnt[0])
print(max(l))

Submission status: Runtime Error

Solution code:
,k = map(int, input().split())
ap = list(map(int, input().split()))
cp = list(map(int, input().split()))

score = []

for m in range(n):
  p = m
  s = []
  ss = 0
  np = -1
  while np != m:
    np = ap[p]-1
    ss = ss + cp[np]
    p = np
    s.append(ss)
  score.append(s)
print(score)

max_s = -(10**9)
for m in range(n):
  loop = int(k / len(score[m]))
  sl = score[m][-1] * loop
  if sl < 0:
    sl = 0
  sm = score[m][0]
  y = k % len(score[m])
  for j in range(y):
    sm = max(sm, score[m][j])
  max_s = max(max_s, sm + sl)

print(max_s)

Submission status: Runtime Error

Solution code:
import sys
import resource
sys.setrecursionlimit(1000000000)

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

for i in range(N):
    P[i] = P[i]-1

def move(pre,score,optimal,remain):
    if remain==0:
        #print("optimal",optimal)
        return optimal
    else:
        score += C[P[pre]]
        optimal = max(optimal,score)
        #print("score",score)
        remain -= 1
        return move(P[pre],score,optimal,remain)


ans_l = []
for i in range(N):
    temp = move(i,0,-1000000000,K)
    ans_l.append(temp)
    #print("===============")

#print(ans_l)
ans = max(ans_l)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
 
 
def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
    ans=-10e10
    for p in range(1,N+1):
        tmp_max=-10e10
        tmp_sum=0
        tmp_ans=-10e10
        _p=p
        end=False
        tmp_list=[]
        for i in range(N):            
            if p==P[_p-1]:
                end=True
            _p=P[_p-1]
            tmp_list.append(C[_p-1])
            #tmp_sum+=C[_p-1]
            #print("tmp_sum:",tmp_sum)
            #tmp_max=max(tmp_max,tmp_sum)
            if end:
                break
        tmp_sum=sum(tmp_list)
        tmp_max=max(np.cumsum(np.array(tmp_list,dtype=np.int64)))
        if tmp_sum<=0:
            tmp_ans=tmp_max
        else:
            tmp_ans=(K//(i+1))*tmp_sum
            #print("tmp_ans",tmp_ans)
            tmp_sum=0
            tmp_max=0
            tmp_list=[]
            mod = K%(i+1)
            for j in range(mod):
                _p=P[_p-1]
                tmp_list.append(C[_p-1])
                #tmp_sum+=C[_p-1]
                #tmp_max=max(tmp_max,tmp_sum)
            #tmp_sum=sum(tmp_list)
            tmp_max=max(np.cumsum(np.array(tmp_list,dtype=np.int64)))
            tmp_ans+=tmp_max
        #print(tmp_ans)
        ans = max(ans,tmp_ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
    ans=-10e10
    for p in range(1,N+1):
        tmp_max=-10e10
        tmp_sum=0
        tmp_ans=-10e10
        _p=p
        end=False
        tmp_list=[]
        for i in range(N):            
            if p==P[_p-1]:
                end=True
            _p=P[_p-1]
            tmp_list.append(C[_p-1])
            #tmp_sum+=C[_p-1]
            #print("tmp_sum:",tmp_sum)
            #tmp_max=max(tmp_max,tmp_sum)
            if end:
                break
        tmp_sum=sum(tmp_list)
        tmp_max=max(np.cumsum(np.array(tmp_list,dtype=np.int64)))
        if tmp_sum<=0:
            tmp_ans=tmp_max
        else:
            tmp_ans=(K//(i+1))*tmp_sum
            #print("tmp_ans",tmp_ans)
            tmp_sum=0
            tmp_max=0
            tmp_list=[]
            mod = K%(i+1)
            for j in range(mod):
                _p=P[_p-1]
                tmp_list.append(C[_p-1])
                #tmp_sum+=C[_p-1]
                #tmp_max=max(tmp_max,tmp_sum)
            #tmp_sum=sum(tmp_list)
            tmp_max=max(np.cumsum(np.array(tmp_list,dtype=np.int64)))
            tmp_ans+=tmp_max
        #print(tmp_ans)
        ans = max(ans,tmp_ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

L = [[] for _ in range(N)]
for i in range(N):
    cnt = C[i]
    blk = P[i]
    L[i].append([cnt, blk])
    for j in range(N):
        li = L[i][j][1]
        if li == i:
            break
        else:
            cnt += C[li]
            blk = P[li]
            L[i].append([cnt, blk])

ans = []
for l in L:
    maxl = 0
    lenl = len(l)
    modK = K % lenl
    numK = K // lenl
    if l[lenl - 1][0] > 0:
        maxl += numK * l[lenl - 1][0]
        maxl += max(l[:modK], key = lambda x:x[0])[0]
    else:
        maxl += max(l[:min(K, lenl)], key = lambda x:x[0])[0]
    ans.append(maxl)

print(max(ans))

Submission status: Runtime Error

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

def roop(i):
  if p[i]-1 not in visit:
    roopcnt.append(roopcnt[-1]+c[p[i]-1])
    global rooph
    rooph+=1
    visit.append(i)
    roop(p[i]-1)
  
l=[]
for i in range(n):
  visit=[]
  roopcnt=[c[i]]
  rooph=1
  roop(i)
  a=(k+1)%rooph
  b=(k+1)//rooph
  if a==0:
    l.append(b*roopcnt[-1]-roopcnt[0])
  else:
    l.append(b*roopcnt[-1]+roopcnt[a-1]-roopcnt[0])
print(max(l))

Submission status: Runtime Error

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

def big(m,l,init=-10**9):
    ret = -10**9
    ll = l + l + l
    """
    for i in range(1,m+1):
        ret_ = sum(ll[:i])
        su = ret_
        for j in range(len(l)):
            su += ll[i+j] - ll[j]
            ret_ = max(ret_,su)
        ret = max(ret,ret_)
    """
    return max(ret,init)

visited = [False]*n

def dfs(l,v):
    if visited[v]:
        return l
    visited[v] = True
    return dfs(l + [c[v]],p[v])

ret = -10**9
for i in range(n):
    l = dfs([],i)
    #print(l)
    if len(l) == 0:
        continue
    if k//len(l) > 0:
        ret = max(ret,sum(l)*(k//len(l))+big(k%len(l),l,init=0))
        ret = max(ret,big(len(l),l))
        ret = max(ret,sum(l)*(k//len(l)-1)+big(len(l),l))
    else:
        ret = max(ret,big(k,l))

print(ret)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
P = list(map(int, input().split()))
P.insert(0,0)
C = list(map(int, input().split()))
C.insert(0,0)
fa = 0
c_flag = 0
for i in range(1,N+1):
    t_list = []
    fill = [0] * (N+1)
    t = P[i]
    c = 0
    sc = 0
    while fill[t] == 0:
        c += 1
        sc += C[t]
        t_list.append(sc)
        fill[t] = 1
        t = P[t]

    if K <= c:
        t_ans = max(t_list[0:K])

        fa = max(t_ans, fa)
        if fa == 0:
            fa = t_list[0]
        continue
    total = t_list[-1]
    loop = len(t_list)
    if total <= 0:
        t_ans = max(t_list[0:K])

        fa = max(t_ans, fa)
        if fa == 0:
            fa = t_list[0]
        continue
    q, mod = divmod(K,loop)
    t_ans = total * q + max(t_list[0:mod])

    fa = max(t_ans, fa)
    if fa == 0:
        fa = t_list[0]
print(fa)

Submission status: Runtime Error

Solution code:
import sys
def main():
  input = sys.stdin.readline
  n, k = map(int , input().split())
  p_list = list(map(int, input().split()))
  c_list = list(map(int, input().split()))
  
  dp = [[float('-inf')]*n for _ in range(k+1)]
  dp[0] = [0]*n
  for i in range(k):
    for j in range(n):
      if i==0:
        dp[i+1][p_list[j]-1] = dp[i][j]+c_list[j]
      else:
        dp[i+1][p_list[j]-1] = max(dp[i][p_list[j]-1], dp[i][j]+c_list[j])
  print(max(dp[-1]))

if (__name__=='__main__'):
  main()

Submission status: Runtime Error

Solution code:

n, k = map(int, input().split())
k = k
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+1, 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+1]), s * (k // roop - 1) + max(a))
            #print(a[:k % roop+1])
print(max(ans))

Submission status: Runtime Error

Solution code:

n, k = map(int, input().split())
k = k
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+1, 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+1]), s * (k // roop - 1) + max(a))
            print(a[:k % roop+1])
print(max(ans))

Submission status: Runtime Error

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


Cum = [0]*(N+2)
temp = 1
SUM = 0
for i in range(N+1):
    temp = P[temp-1]
    SUM += C[temp-1]
    Cum[i+1] += SUM
    
 
    

group = []
group_C = []
group_Cum = []

check = [1]*N

while sum(check)!=0:
    temp = []
    start_num = check.index(1)+1
    temp_p = P[start_num-1]
    check[temp_p-1] -= 1
    temp.append(temp_p)
    
    temp_c = C[temp_p-1]
    
    temp_Cum = [0]
    temp_Cum.append(temp_c)
    
    for i in range(N):
    
        temp_p = P[temp_p-1]
        check[temp_p-1] -= 1
        temp.append(temp_p)
        temp_c += C[temp_p-1]
        temp_Cum.append(temp_c)
                
        if temp_p == start_num:
            break
    
    for i in range(len(temp)):
        temp_Cum.append(temp_c+temp_Cum[1+i])
    
    
    group.append(temp)
    group_C.append(max(0,temp_c))
    group_Cum.append(temp_Cum)
    
ans = -10**12

for i in range(len(group_C)):
    X = len(group[i])
    Y = K//X
    Z = K%X
       
    group_max = -10**12
    for k in range(1,Z+1):

        for j in range(X):
            group_max = max(group_max,group_Cum[i][k+j]-group_Cum[i][j])
            
        
        ans = max(ans,group_max+Y*group_C[i])
        
    if Y == 1 or group_C == 0:
        Z += X
        
        for k in range(1,Z+1):

            for j in range(X):
                group_max = max(group_max,group_Cum[i][k+j]-group_Cum[i][j])
                

            ans = max(ans,group_max+(Y-1)*group_C[i])
    
print(ans)

Submission status: Runtime Error

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

a=[]
def dfs(max_result, result, pos, num):
  if num >= k:
    a.append(max_result)
    return
    
  next = p[pos-1]
  result += c[next-1]
  max_result = max(result, max_result)
  dfs(max_result, result, next, num+1)

for i in range(1,n+1):
  dfs(-10**9,0,i,0)
print(max(a))

Submission status: Runtime Error

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

ans = 0

if sum(C) > 0 and K > N:
    ans += sum(C) * (K // N)
    K_ = K % N

if K == 1:
    ans += max(C)
else:
    r = []
    now = 0
    for _ in range(N):
        r.append(P[now]-1)
        now = P[now]-1

    r = r + r
    ruiseki = [0 for _ in range(N*2 + 3)]
    for i in range(N*2):
        ruiseki[i+1] = ruiseki[i] + C[r[i]]

    m = -9999999999999999999999
    m_ = -9999999999999999999999
    for i in range(N*2 - K):
        for j in range(i+1, i+1+K):
            m = max(m, ruiseki[j] - ruiseki[i])
        for j in range(i+1, i+1+K_):
            m_ = max(m_, ruiseki[j] - ruiseki[i])


    ans = max(m, ans+m_)

print(ans)

Submission status: Runtime Error

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

def big(m,l,init=-10**9):
    ret = -10**9
    ll = l + l + l
    for i in range(1,m+1):
        ret_ = sum(ll[:i])
        su = ret_
        for j in range(len(l)):
            su += ll[i+j] - ll[j]
            ret_ = max(ret_,su)
        ret = max(ret,ret_)
    return max(ret,init)

visited = [False]*n

def dfs(l,v):
    if visited[v]:
        return l
    visited[v] = True
    return dfs(l + [c[v]],p[v])

ret = -10**9
for i in range(n):
    l = dfs([],i)
    #print(l)
    if len(l) == 0:
        continue
    if k//len(l) > 0:
        ret = max(ret,sum(l)*(k//len(l))+big(k%len(l),l,init=0))
        ret = max(ret,big(len(l),l))
        ret = max(ret,sum(l)*(k//len(l)-1)+big(len(l),l))
    else:
        ret = max(ret,big(k,l))

print(ret)

Submission status: Runtime Error

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

n, k = map(int, input().split())
parr = list(map(int, input().split()))
carr = list(map(int, input().split()))

dp = [[0]*n for _ in range(k+1)]
maximum = -10**9

for i in range(1, k+1):
    for j in range(n):
      tmp = dp[i-1][j] + carr[j]
      dp[i][parr[j]-1] = tmp
      if tmp > maximum:
        maximum = tmp

print(int(maximum))

Submission status: Runtime Error

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

ans = 0

if sum(C) > 0 and K > N:
    ans += sum(C) * (K // N)
    K_ = K % N

if K == 1:
    ans += max(C)
else:
    r = []
    now = 0
    for _ in range(N):
        r.append(P[now]-1)
        now = P[now]-1

    r = r + r
    ruiseki = [0 for _ in range(N*2 + 3)]
    for i in range(N*2):
        ruiseki[i+1] = ruiseki[i] + C[r[i]]

    m = -9999999999999999999999
    m_ = -9999999999999999999999
    for i in range(N*2 - K):
        for j in range(i+1, i+1+K):
            m = max(m, ruiseki[j] - ruiseki[i])
        for j in range(i+1, i+1+K_):
            m_ = max(m, ruiseki[j] - ruiseki[i])


    ans = max(m_, ans+m)

print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
r = -10**9
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    y = k//len(e)*e[-1]+max(e[:w])
    g=y
  else:
    g=max(e)
  r = max(r,g)
  
print(r)