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:
X,K=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(2)]
m=[]
n=[]
for i in range(1,X+1):
  count=2
  k=l[0][i-1]
  a=l[1][i-1]+l[1][k-1]
  while k != i:
    k=l[0][k-1]
    a=a+l[1][k-1]
    count=count+1
  t=a*(K//count)
  k=i
  u=0
  for j in range(K%count):
    k=l[0][k-1]
    u=u+l[1][k-1]
    n.append(u)
  m.append(t+max(n))
print(max(m))

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

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:
import sys
import copy
input = sys.stdin.readline


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

ans=-1*(10**10)

if K<100000:
    for i in range(N):
    tmp=0
    pos=i
    count=0
    while count<K:    
        #print(pos,P[pos])
        tmp+=C[P[pos]-1]
        if tmp>ans:
            ans=tmp
        
        pos=P[pos]-1
        count+=1
 
    print(ans)
else:
    
    for i in range(N):
        tmp=0
        pos=i
        gpos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            
            pos=P[pos]-1
            count+=1
            if pos==gpos and count!=K:
                divide=K//count
                tmp=tmp*divide
                count=count*divide
                gpos=10**10
            
    
    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(1,N+1):
  y = 0
  x = i
  for j in range(1,K+1): 
    x = P[x-1]
    y = y+C[x-1]
        
  w = max(0,z)
print(w)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys, copy,itertools
input = sys.stdin.readline

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

ans = [-10**12] * n
#print(ans)

q = k // n
mod = k % n

POINT = [[-10**12 for i in range(n)] for j in range(k)]
PLACE = [[0 for i in range(n)] for j in range(k)]
for i in range(n):
  POINT[0][i] = C[P[i]-1]  
  PLACE[0][i] = P[i]-1 #P[i]は1スタートなのでずれる

tempmax= max(POINT[0])

z = min(k,n)

for j in range(1,z): #日付
  for i in range(n):
    PLACE[j][i]=P[PLACE[j-1][i]]-1
    POINT[j][i]=POINT[j-1][i] + C[PLACE[j][i]]
    tempmax = max(tempmax,POINT[j][i])

tt = -10**-12
if k <= n:
  answer = tempmax
else:
  for i in range(n):
    ans[i] = q * POINT[n][i]
    for j in range(mod):
      tt = max(tt, POINT[j][i])
    ans[i] += tt
print(max[answer])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 21:47:07 2020

@author: riichi
"""


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

d = dict()
c = dict()

for i in range(N):
    d[i+1] = P[i]
    
for i in range(N):
    c[i+1] = C[i]
    
check = [0]*N

def a(arr):
    ans = 0
    SU = sum(arr)
    k = K
    if K > len(arr) and SU > 0:
        ans2 = (K//len(arr)) * SU
        k = K % len(arr)
    
    ma = [0]*len(arr)
    for i in range(len(arr)):
        ans = 0
        mans = -(10**9)-1
        for j in range(k):
            ans += arr[(i+j)%len(arr)]
            if ans > mans:
                mans = ans
        ma[i] = mans
    return (max(ma)+ans2)
    
anan = []

for i in range(N):
    if check[i] == 1:
        #print(i,'OK')
        continue
    
    p = i+1
    tmp = []
    for j in range(N+1):
        p = d[p]
        if check[p-1] == 0:
            check[p-1] = 1
            tmp.append(c[p])
        else:
            #print(j,tmp,a(tmp))
            anan.append(a(tmp))
            break
            
print(max(anan))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

dp = np.zeros((k+1, n))
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())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

ps = [p-1 for p in ps]

visited = []
coarses = []
scores = []
while True:
    if len(visited) == n:
        break

    now = list(set(ps) - set(visited))[0]
    coarse = []
    score = []
    s, pre_s = 0, 0

    while True:
        nxt = ps[now]
        if nxt in visited:
            break

        s += cs[now]
        if cs[now] > 0:
            score.append(dict(bgn=pre_s, now=s, max=s))

        for sc in score:
            sc["now"] = s
            if sc["now"] > sc["max"]:
                sc["max"] = sc["now"]

        visited.append(nxt)
        coarse.append(nxt)
        now = nxt
        pre_s = s
    
    scores.append(score)
    coarses.append(coarse)

s_cands = []
for score in scores:
    s_cands.append(score["max"] - score["bgn"])

for coarse in coarses:
    sm = 0
    for i in coarse:
        sm += cs[i]
    s_cands = sm * (k // len(coarse))

print(max(s_cands))

Submission status: Runtime Error

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

cost_list=[]
 
for n in range(N):
  temp_cost=0
  next_n=n
  for k in range(K):
    temp_cost+=C[P[next_n]-1]
    cost_list.append(temp_cost)
    next_n=P[P[next_n]-1]
print(min(cost_list))

Submission status: Runtime Error

Solution code:
# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.

import itertools

n, k = list(map(int, input().split(" ")))
#n, k = 10, 33
p = list(map(int, input().split(" ")))
c = list(map(int, input().split(" ")))
#p = [9, 1, 6, 7, 8, 4, 3, 2, 10, 5]
#c = [8, 10, -2, 7, -3, -5, -4, 1, 6, 9]

max_score = 0
for start_position in range(1, len(p)+1):
    score = 0
    tokuten_history = []
    now_position = start_position
    for i in range(len(p)):
        now_position = p[now_position-1]
        score += c[now_position - 1]
        tokuten_history.append(score)
        max_score = max(max_score, score)
        if now_position == start_position:
            # 2 shuume ikou
            if score <= 0:
                # shukai surukatinasi
                break
            else:
                # shukaino
                nokori_idou_kaisuu = k - (i+1)
                nokori_shukai_kaisuu = nokori_idou_kaisuu // (i+1)
                score += (nokori_shukai_kaisuu * score)
                max_score = max(score, max_score)

                nokori_idou_kaisuu = nokori_idou_kaisuu - (nokori_shukai_kaisuu * (i+1))
                now_position = start_position

                score += max(tokuten_history[:-1][:nokori_idou_kaisuu])
                max_score = max(max_score, score)

if max_score == 0:
    print(max(c))
else:
    print(max_score)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
list = []
if sum(c)<=0 or 2*n>=k:
  for i in range(n):
    s = 0
    m = -10**10
    for j in range(k):
      i = p[i]-1
      s += c[i]
      m = max(m, s)
      list.append(m)
else:
  for i in range(n):
    s = 0
    m = -10**10
    pre = k//n -1
    k = k - pre*n
      for j in range(k):
      i = p[i]-1
      s += c[i]
      m = max(m, s)
      list.append(m)
print(max(list))

Submission status: Runtime Error

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

score = 0

NINF = -10 ** 9 * (N + 1)
# １回以上移動する

A = []
A_max = [NINF] * K
for i in range(N):
    A += [[NINF] * K]

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

for i in range(N):
    for k in range(K - 1):
        if (A[i][k + 1] != NINF):
            continue
        else:
            A[i][k + 1] = A[P[i] - 1][k] + C[P[i]-1]
    A_max[i] = max(A[i])
print(max(A_max))

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 make_group_shim0(x, check):
    lis = [x - 1]
    while not P[x - 1] - 1 in lis:
        lis.append(P[x - 1] - 1)
        check.append(P[x - 1] - 1)

        x = P[x - 1]
    return lis


Big_lis = []
check = []
i = 1
while i < N:
    if i - 1 not in check:
        Big_lis.append(make_group_shim0(i, check))
    i += 1


LIST_kazu = len(Big_lis)

for i in range(LIST_kazu):
    N = len(Big_lis[i])

    k_hasuu = K % N
    k_kaisu = K // N
    summ = 0

    for j in Big_lis[i]:
        summ += C[j]
    dp = [[0 for i in range(N+1)] for j in range(K+1)]

    for j in range(1, N):
        dp[j][0] = Big_lis[i][j]
    ans1 = max(Big_lis[i])
    
    for j in range(1,N):
        for k in range(K):
            dp[P[j]][k] = dp[j][k-1] + C[P[j]]
            ans1 = max(ans1, dp[P[j]][k])
print(dp[K][N])

Submission status: Runtime Error

Solution code:

n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

if (sum(c) <= 0) | (k < n):
  ans = 0
else:
	ans = sum(c)*(k//n)
x = []
for j in range(1,n+1):
  r_c = []
  for i in range(j,n+j):
    i = i % n
    r_c.append(c[p[i]-1])
    
    k = k % n
    tmp = max([sum(r_c[:i+1]) for i in range(k-1)])
    if k == n:
      tmp = max(sum(r_c),tmp)
    x.append(tmp)
print(ans + max(x))

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline
t = 0 #得点記録
w = 0 #現在地点
e = 0
n, k = map(int,input().split())
p = [list(input().split()) for _ in range(n)]
c = [list(input().split()) for _ in range(n)]
pt = []
for i in range(n):
  w = i
  for j in range(k):
    w = int(p[w])
    e = int(c[w])
    t += e
    pt.append(t)
  else:
    t = 0
print(max(pt))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
turn = [0] * n
for i in range(n):
    turn[p[i] - 1] = c[i]
print(turn)
x = 0
y = 0
z = 0
if k % n + n >= k:
    for i in range(1,k + 1): #移動させる回数
        for j in range(n): #コマのスタート
            for k in range(i): #加算するコマ
                y += turn[j + k]
            if x < y:
                x = y
            y = 0
else:
    for i in range(1,k % n + n): #移動させる回数
        for j in range(n): #コマのスタート
            for k in range(i): #加算するコマ
                y += turn[j + k]
            if x < y:
                x = y
            y = 0
    for i in range(n):
        z += turn[i]
    if z >= 0:
        x += z * (k // n - 1)
print(x)

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

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]*K
for i in range(K):
    X = i
    for j in range(N):
        X = Ps[X]
        Sss[i][j] = Sss[i-1][j] + Cs[X]
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()))

ume = [True] + [False] * N
loop = []
for i in range(1,N+1):
    if ume[i]:
        continue
    else:
        ll = [C[i-1]]
        ume[i] = True
        ne = P[i-1]
        while ume[ne] == False:
            ume[ne] = True
            ll.append(C[ne-1])
            ne = P[ne-1]
        loop.append(ll)
    if False not in ume:
        break

def maxSubArraySum(a,size): 
      
    max_so_far = 0
    max_ending_here = 0
      
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if max_ending_here < 0: 
            max_ending_here = 0
          
        # Do not compare for all elements. Compare only    
        # when  max_ending_here > 0 
        elif (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
              
    return max_so_far 

lP = []
for i in loop:
    t = sum(i)
    lP.append([t,len(i)])

ans = 0
cnt = -1
for i in lP:
    cnt += 1
    if i[0] > 0:
        tim = K // i[1]
        nok = K - tim * i[1] 
        wl = loop[cnt] + loop[cnt]
        tmp = tim * i[0] + maxSubArraySum(wl,nok)
    else:
        tmp = maxSubArraySum(loop[cnt],1)
        for j in range(2,min(len(loop[cnt],K+1)):
            tmp2 = maxSubArraySum(loop[cnt],j)
            tmp = max(tmp,tmp2)
    ans = max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K = list(map(int, input().split()))
input_list = list(map(int, input().split()))
input_list = list(np.array(input_list)-1)
c_list = list(map(int, input().split()))

#for i in range(N):
def roop_func(l, i, start, return_list=[]):
    return_list.append(l[i])
    if l[i] == start:
        return return_list 
    return roop_func(l, l[i],start, return_list)

total_best = -100000000000000000000
for start in range(N):
    p_list = roop_func(input_list, start, start,[])
    epoc = sum([c_list[i] for i in p_list])
    if epoc <= 0: # 回るごとに下がる場合
        best = c_list[p_list[0]]
        current_score = c_list[p_list[0]]
        for i in range(1, min(K, len(p_list))):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    else: #回るごとに上がる場合
        syo,amari = divmod(K, len(p_list))
        base = (syo-1) * epoc
        p_list = p_list.append(p_list[:amari])
        best = c_list[p_list[0]] + base
        current_score = c_list[p_list[0]] + base
        for i in range(1, len(p_list)):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    if best > total_best:
        total_best = best
        
print(total_best)

Submission status: Runtime Error

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

N,K=(int(x) for x in input().rstrip('\n').split())
Ps = [int(x)-1 for x in input().rstrip('\n').split()]
Cs = [int(x) for x in input().rstrip('\n').split()]
res = -10**9-1
for i in range(N):
  next = Ps[i]
  cycle = Cs[next]
  steps =[cycle]
  for a in range(1,K+1):
    next = Ps[next]
    cycle += Cs[next]
    steps.append(cycle)
    if next == i:
      if cycle>0:
        if K%a!=0:
          now = (K//(a+1))*cycle+max(steps[:K%(a+1)])
          if now>res:
            res = now
          break
        else:
          now =(K//(a+1))*cycle
          if now>res:
            res = now
          break
      else:
        now = max(steps)
        if now>res:
          res = now
        break
    if a==K:
      now = max(steps)
      if now>res:
        res = now
print(res)

Submission status: Runtime Error

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

    score = []
    checked = [0] * N
    for v in range(N):
        if checked[v]:
            continue
        t = []
        for _ in range(N):
            if checked[v]:
                break
            checked[v] = 1
            t.append(C[v])
            v = P[v]
        score.append(t)

    print(f'{score=}')

    ans = 0
    for loop_lst in score:
        L = len(loop_lst)
        s = sum(loop_lst)
        t = 0
        if s > 0:
            q, K = divmod(K, L)
            t += q * s
        K = min(K, L - 1)
        acc = [0]
        for x in loop_lst:
            acc.append(acc[-1] + x)
        add_v = 0
        for j in range(N)
        for i in range(K):
            add_v = max(acc[i+j] - acc[j])
        ans = max(ans, t + add_v)
    print(ans)


if __name__ == '__main__':
    main()

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] = P[i]-1

def move(pre,score,optimal,remain):
    if remain==0:
        return optimal
    else:
        score += C[P[pre]]
        optimal = max(optimal,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)

ans = max(ans_l)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    INF = 10**9
    n,k = map(int,input().split())
    P = [0] + list(map(int,input().split()))
    C = [0] + list(map(int,input().split()))

    scores = [0]*n

    for s in range(1,n+1):
        start = s
        dp = [-INF]*(n+1)
        dp[0] = 0
        for i in range(n):
            p = P[s]
            dp[i+1] = dp[i] + C[p]
            
            if start == p:
                break
            s = p
        if k <= i+1:
            scores[start-1] = max(dp[1:k+1])
        elif dp[i+1]<=0:
            scores[start-1] = max(dp[1:])
        else:
            r = k%(i+1)
            q = k//(i+1)
            scores[start-1] = max(max(dp[1:r+1])+dp[i+1]*q, max(dp[1:]))
    
    print(max(scores))
main()

Submission status: Runtime Error

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

loop_list = [] # ([indexes])
loop_score_list = []
loop_index_list = [0]*N
is_included_loop = [0] * N
num_loop = 0

for start in range(N):
    if is_included_loop[start]:
        continue
    now = start
    count = 1
    visited = [-1]*N # count
    visited[now] = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            terminate_count = count
            start_count = visited[now]
            loop_start_idx = now
            break
        visited[now] = count
        count += 1
    
    num_loop += 1
    now = loop_start_idx
    loop_indexes = [now]
    visited = [-1]*N
    visited[now] = 0
    count = 1
    loop_score = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            break
        loop_indexes.append(now)
        visited[now] = count
        loop_index_list[now] = num_loop
        loop_score += C[now]
        is_included_loop[now] = 1
    loop_list.append(loop_indexes)
    loop_score_list.append(loop_score)


scores = []
for start in range(N):
    tmp_score = 0
    rest = K
    now = start
    while not is_included_loop[now] and rest > 0:
        now = P[now]
        rest -= 1
        tmp_score += C[now]
        scores.append(tmp_score)
    
    if rest <= 0:
        scores.append(tmp_score)
        continue
    # loop
    number_of_loop = loop_index_list[now]
    one_cicle_score = loop_score_list[number_of_loop]
    if one_cicle_score < 0:
        continue
    if rest <= len(loop_list[number_of_loop]):
        while rest >= 0:
            now = P[now]
            rest -= 1
            tmp_score += C[now]
            scores.append(tmp_score)
        continue
    else:
        n_l = rest // len(loop_list[number_of_loop])
        tmp_score += n_l * one_cicle_score
        scores.append(tmp_score)
print(max(scores))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
check =  [0 for i in range (n+1)]
loop = []
for i in range (1,n+1):
    if check[i] == 0:
        num = i
        sloop = []
        while True:
            sloop.append(num)
            num = p[num-1]
            check[num] = 1
            if num == i:
                loop.append(sloop)
                break
loopscore = []
maxs = []
for i in range (len(loop)):
    sloopscore  = []
    for j in range (len(loop[i])):
        sloopscore.append(c[loop[i][j]-1])
    loopscore.append(sloopscore)
for i in range (len(loop)):
    s = sum(loopscore[i]) 
    if s >=0:
        if k %len(loop[i]) == 0:
            maxs.append(s*k//len(loop[i]))
        else:
            maxss = []
            for j in range (len(loop[i])):
                ss = []
                num = 0
                for y in range (k %len(loop[i])):
                    loopscore[i] += loopscore[i]
                    num += loopscore[i][j+y]
                    ss.append(num)
                maxss.append(s*k//len(loop[i])+max(ss))
            maxs.append(max(maxss))
    else:
        maxss = []
        for j in range (len(loop[i])):
            ss = []
            num = 0
            for y in range (loop[i]):
                loopscore[i] += loopscore[i]
                num += loopscore[i][j+y]
                ss.append(num)
            maxss.append(max(ss))
        maxs.append(max(maxss))
print(max(maxs))

Submission status: Runtime Error

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

check = []
s = 0

for i in range(n):
    t = 0
    u = p[i]-1
    for j in range(k):
        t += c[u]
        u = p[u]
        if (s < t):
            s = t

print(s)

Submission status: Runtime Error

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
R,C,K = inputlist()
dp = [[[0,0,0,0] for _ in range(C)] for _ in range(R)]
li = [0]*K
val = {}
pl = [0]*K
for i in range(K):
    r,c,v = inputlist()
    pl[i] = (r-1,c-1)
    val[(r-1,c-1)] = v
for i in range(K):
    dp[pl[i][0]][pl[i][1]][0] = val[pl[i]]

k = dp[0][0][0]
for i in range(1,4):
    dp[0][0][i] = k

tmp = dp[0][0][0]
for x in range(C):
    dp[0][x][1] = max(tmp,dp[0][x][0])
    if dp[0][x][0] > tmp:
        tmp = dp[0][x][0]
tmp = dp[0][0][0]
for y in range(R):
    dp[y][0][1] = max(tmp,dp[y][0][0])
    if dp[y][0][0] > tmp:
        tmp = dp[y][0][0]
for y in range(1,R):
    for x in range(1,C):
        dp[y][x][1] = max(dp[y-1][x][1],dp[y][x-1][1],dp[y][x][0])

for i in range(2,4):
    for x in range(1,C):
        dp[0][x][i] = max(dp[0][x-1][i],dp[0][x-1][i-1]+dp[0][x][0])
    for y in range(1,R):
        dp[y][0][i] = max(dp[y-1][0][i],dp[y-1][0][i-1]+dp[y][0][0])
    for y in range(1,R):
        for x in range(1,C):
            dp[y][x][i] = max(dp[y-1][x][i],dp[y][x-1][i],dp[y-1][x][i-1]+dp[y][x][0],dp[y][x-1][i-1]+dp[y][x][0])

print(dp[R-1][C-1][3])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
s=[]
for i in range(0,n):
    c=0
    for j in range(1,k+1):
        p=P[i]
        c+=C[p-1]
        s.append(c)
        i=P[i]-1

    print(s)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10**9-1
for i in range(N):
    cumsum = [0]*(N+1)
    seen = [-1]*N
    K_ = K
    now = i
    j = 0
    while K_ > 0 and seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        K_ -= 1
        j += 1
    if K_ == 0:
        ans = max(ans, max(cumsum[1:j]))
    else:
        if cumsum[j] > 0:
            loop_size = j
            loop_n = K//loop_size - 1
            tmp = loop_n*cumsum[loop_size]
            tmp += max(max(cumsum[1:loop_size]), cumsum[loop_size] + max(cumsum[0:K_+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j+1]))
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()))

ans = min(C)
for i in range(1, N + 1):
    point = []
    p = 0
    buf = i
    while P[buf] != i:
        buf = P[buf]
        p += C[buf]
        point.append(p)
    buf = P[buf]
    p += C[buf]
    point.append(p)

    if point[-1] <= 0:
        if len(point) > K:
            point_buf = max(point[:K])
        else:
            point_buf = max(point)
    else:
        if len(point) > K:
            point_buf = max(point[:K])
        else:
            division, mod = divmod(K, len(point))
            point_buf = division * point[-1] + max(point[:mod])
    if ans < point_buf:
        ans = point_buf
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

visited=[0]*n

A=[]
for i in range(1,n+1):
    if visited[i-1]==1:
        continue
    s=i
    X=[]
    while True:
        s=P[s-1]
        X.append(C[s-1])
        visited[s-1]=1
        if s==i:
            break
    A.append(X)

ANS=[]
for a in A:
    if len(a)>=k:
        B=a.copy()
        B=[0]+B+B

        D=list(accumulate(B))
        ans=-(10**18)
        for i in range(1,k+1):
            c=-(10**18)
            for j in range(len(a)):
                c=max(D[j+i]-D[i],c)
            ans=max(ans,c)
        ANS.append(ans)



print(max(ANS))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration

class BIT():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1    
    
def main():
    N, K = MI()
    P = LI()
    C = LI()
    #1週下再に加算されるスコア並びにあるますから出発した際に１マス進んだ際のスコアがわかればよい。
    #初期化
    temp = 0
    score = sum(C)
    temp_score = 0
    if score > 0:
        start = K % N
        result += score * (K // N)
    else:
        start = N
    
    for i in range(N):
        temp = P[temp]
        tree.add(i+1, C[temp])
    for i in range(start):
        for j in range(1,N-1):
            if i+j+1 > N:
                k = i+j+1-N
            else:
                k = i+j+1
            result = max(result, tree.rangesum(i+1,k))
    print(result)

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 //

Submission status: Runtime Error

Solution code:
print('input >>')
N, K = map(int,(input().split()))
Ps = [0] + list(map(int,(input().split())))
Cs = [0] + list(map(int,(input().split())))

visited = [0] * (N+1)
routes = []
for i in range(1, len(Ps)):
    if visited[Ps[i]] == 0:
        visited[i] = 1
        route = []
        start = i
        next_p = Ps[i]
        route.append(Cs[next_p])
        while True:
            visited[next_p] = 1
            next_p = Ps[next_p]
            route.append(Cs[next_p])
            if next_p == start:
                break
        routes.append(route)
        print('------')

for route in routes:
    ma = 0
    for r in routed:
        if r > 0:
            r > 

print('-----output-----')
print(routes)

# ここまでは考えたから！！！　記念提出！！