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: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -10 ** 9
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    point = scores[f_pos]
    s.append(point)
    while f_pos != i:
      f_pos = positions[i]
      point += scores[f_pos]
      s.append(point)
    loop = len(s)
    if loop > k:
      point = max(s[:k])
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(s)
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)

Submission status: Time Limit Exceeded

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

ans = []
sm = 0
for i in range(n):
    sm = c[p[i]-1]
    fsm = max(-(int(1e9)+1), sm)
    ind = p[i] - 1
    for j in range(1,k):
        sm += c[p[ind]-1]
        ind = p[ind]-1
        fsm = max(fsm, sm)

    ans.append(fsm)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
ans = -float('inf')
for s in range(N):
    S = [] 
    i = P[s] - 1
    S.append(C[i])
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])
 
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
 
    ans = max(ans, score)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
from itertools import accumulate


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

INF = 1 << 60
ans = -INF
checked = [False] * n

for i in range(n):
    # ループに出てくるパターンは一度で処理
    if checked[i] == True:
        continue
    checked[i] = True

    scores = [c[p[i]]]
    nxt = p[i]
    while nxt != i:
        scores.append(c[p[nxt]])
        checked[i] = True
        nxt = p[nxt]

    l = len(scores)
    div, mod = divmod(k, l)
    cycle_sum = sum(scores)

    if div > 0:
        div -= 1
        mod += l

    scores += scores * 2
    scores.insert(0, 0)
    cycle2 = list(accumulate(scores))
    tmp = max(max(cycle2[i + 1:i + mod + 1]) - cycle2[i] for i in range(l))
    ans = max(ans, tmp, cycle_sum * div + tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


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

INF = 1 << 60
ans = -INF
checked = [False] * n

for i in range(n):
    # ループに出てくるパターンは一度で処理
    if checked[i] == True:
        continue
    checked[i] = True

    scores = [c[p[i]]]
    nxt = p[i]
    while nxt != i:
        scores.append(c[p[nxt]])
        checked[i] = True
        nxt = p[nxt]

    l = len(scores)
    div, mod = divmod(k, l)
    cycle_sum = sum(scores)

    if div > 0:
        div -= 1
        mod += l

    scores += scores * 10
    scores.insert(0, 0)
    cycle2 = list(accumulate(scores))
    tmp = max(max(cycle2[i + 1:i + mod + 1]) - cycle2[i] for i in range(l))
    ans = max(ans, tmp, cycle_sum * div + tmp)

print(ans)

Submission status: Time Limit Exceeded

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 i in range(N):
    visited = set()
    tmp = 0
    for k in range(K):
        if P[i] in visited: break
        tmp += C[P[i]]
        i = P[i]
        visited.add(i)
        ans = max(ans, tmp)
    if tmp < 0: continue
    l = len(visited)
    rem = K-l
    d,m = divmod(rem,l)
    if m==0 and d > 0:
        m = l
        d -= 1
    tmp *= (d+1)
    for k in range(m):
        tmp += C[P[i]]
        i = P[i]
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

def loop(s):
    value = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        value += C[s]
    return len(done), value

def f(s,K):
    ans = -10**18
    total = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1

        if K==0:
            return ans

    lamb, value = loop(s)

    if K > 2*lamb:
        K -= lamb
        if value > 0:
            total += (K//lamb)*value
            ans = max(ans,total)
            K -= (K//lamb)*lamb
        K += lamb

    while K > 0:
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1
    return ans

print(max([f(s,K) for s in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-float("inf")
for i in range(n):
  count=0
  start=i+1
  for j in range(k):
    count+=c[p[start-1]-1]
    start=p[start-1]
    ans=max(ans,count)
print(ans)

Submission status: Time Limit Exceeded

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


P=[0]+P
C=[0]+C

ans=-10**10
for i in range(1,N+1):
    G=[i]
    for j in range(N):
        if P[G[j]]==i:
            break
        else:
            G.append(P[G[j]])
    
    roop=0
    g=len(G)
    for j in range(g):
        roop+=C[G[j]]
    
    x=0
    if roop>0:
        x=roop*(int(K/g)-1)
        for j in range(K-g-K%g,K):
            x+= C[G[j%g]]
            if ans<x:
                ans=x

    else:
        for j in range(g):
            x+=C[G[j]]
            if ans<x:
                ans=x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root (self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def isConnect(self, x):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parents[self.root(x)]

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

INF = 10 ** 18
ans = -INF
dp = [[-INF] * (N + 1) for _ in range(N)]
uf = Unionfind(N)

for i in range(N):
    dp[i][0] = 0
    now = i
    for j in range(min(N, K)):
        now = P[now]
        dp[i][j + 1] = dp[i][j] + C[now]
        uf.connect(i, now)
        ans = max(ans, dp[i][j + 1])

for i in range(N):
    M = uf.size(i)
    if dp[i][M] <= 0:
        continue
    roop = K // M
    move = K % M
    if move == 0:
        roop -= 1
        move = M
    for j in range(move):
        ans = max(ans, dp[i][M] * roop + dp[i][j + 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int,input().split()))
jump = list(map(int,input().split()))
arr = list(map(int,input().split()))
best = - (10**28)
VV = []
 
for i in range(n):
  if i not in VV:
    order = []
    prev_pos = i
    visited = []
    sub_best = 0
    order = []
    l = 0
 
    for jjj in range(n):
      order.append(arr[prev_pos])
      #sub_best = max(sub_best, sum(order))
      visited.append(prev_pos)
      VV.append(prev_pos)
      l += 1
 
      next_pos = jump[prev_pos] - 1
      prev_pos = next_pos
      if next_pos in visited:
        break
 
    if sum(order)<1:
      limit = min(k,l*2)
      ss = 0
    else:
      limit = (k % l) + l
      limit = min(k,limit)
      ss = sum(order) * ((k//l) - 1)
 
    sub_best += ss
    #print(limit)
    
    order = order + order + order
    
    for op in range(len(order)):
      for chuj in range(1,limit+1):
        kk = sum(order[op:op+chuj])
        best = max(best, sub_best + kk)
      
print(best)

Submission status: Time Limit Exceeded

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

dp = []
init = 0

if K<=N:
  ans = set()
  for i in range(N):
    tmp,now,last = [0],i,0
    for _ in range(K):
      last += C[P[now]]
      ans.add(last)
      now=P[now]
  print(max(ans))
  exit()
ans = -10**9
for i in range(N):
  tmp,now,done = [0],i,set()
  for _ in range(N+1):
  #while now not in done:
    tmp.append(tmp[-1]+C[P[now]])
    if P[now] == i:
      break
    now = P[now]
  tmp = tmp[1:]
  cnt = len(tmp)
  m = max(tmp)
  ans = max(ans,m,tmp[-1]*(K//cnt-1)+m)
  if K%cnt != 0:
    ans = max(ans, tmp[-1]*(K//cnt)+max(tmp[:K%cnt]))
    #print(i,ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

#マスに与えられたスコアが全部負だった場合には，その中で最もダメージの小さいマスを一つ踏んで終わる。
C_max = max(C[1:])
if C_max < 0:
    print(C_max)
    exit()


ans = 0

done = [False] * (N + 1) #チェック済みのマスはTrueにしていく。(loopはバラバラの構成員で構成されてるので。)

#loopの構成員をもらう。 -→ loopの中でマスaから始まりマスbで止まる操作をする場合の最大スコアを数える。
#の順番で解く。

for i in range(1, N + 1):
    if done[i]:
        continue
        #マスiがチェック済みの場合には何もせずiを次に進める。（continue）

    loop = [i] #ここにloopの構成員が記録される。iは最初から入れておく。
    now = P[i] #iから一歩進んだマスを起点として，loop構成員の記録を開始する。
    while now != i:
        loop.append(now)
        done[now] = True
        now = P[now]
        #今立っているマスがiでない場合は，loop構成員リストに記録して，doneをTrueにして，足を一歩進める。

    #print(loop)
    #loopの構成員のメモが完了！

    L = len(loop)
    S = sum(C[v] for v in loop) #loopを一周した時のスコア

    for a_ind in range(L):
        a = loop[a_ind]
        score_ab = -C[a]
        #例えば[3, 6, 4, 7]のloopがあった時，a = 3→6→4→7 と移っていきたいので，a_ind = 0→1→2...として，a =  loop[0]→loop[1]→loop[2]→loop[3]とする。bもまた然り。
        for b_ind in range(a_ind, a_ind + L):#aから数週してaに戻るプレイも可能なので，b == aとなる場合も含んでおかなければならない。
            dist_ab = b_ind - a_ind
            if dist_ab > K:
                break
            b = loop[b_ind % L]
            score_ab += C[b]

            max_score = score_ab + max(0, S) * ((K - dist_ab) // L)
            #スコアの最大値は，
            # S > 0の場合，[aからbまで移動した時のスコア] ＋ S * [可能な限りloopを周回する]　（周回した方が得なので）
            # S < 0の場合，[aからbまで移動した時のスコア]　（周回した方が損なので）
            #上の場合分けの切り替えを　max(0, S)　で行っている！地味にすごい！

            ans = max(ans, max_score)

print(ans)

Submission status: Time Limit Exceeded

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

dp = []
init = 0

if K<=N:
  ans = set()
  for i in range(N):
    tmp,now,last = [0],i,0
    for _ in range(K):
      last += C[P[now]]
      ans.add(last)
      now=P[now]
  print(max(ans))
  exit()
ans = -10**9
for i in range(N):
  tmp,now,done = [0],i,set()
  while now not in done:
    done.add(now)
    tmp.append(tmp[-1]+C[now])
    now = P[now]
  cnt = len(done)
  tmp = tmp[1:]
  ans = max(ans,max(tmp))
  if K%cnt == 0:
    ans = max(ans, tmp[-1]*(K//cnt-1)+max(tmp))
  else:
    ans = max(ans, tmp[-1]*(K//cnt-1)+max(tmp), tmp[-1]*(K//cnt)+max(tmp[:K%cnt]))
    #print(i,ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

ans = -10 ** 10

if  n >= k:
    for i in range(n):
        score = 0
        z = p[i] - 1
        for j in range(k):
            score += c[z]
            z = p[z] - 1
            if ans <= score:
                ans = score

else:
    row = []
    for i in range(n):
        row_i = 0
        z = p[i] - 1
        for j in range(n):
            row_i += 1
            if p[i] == p[z]:
                row.append(row_i)
                break
            z = p[z] - 1
    for i in range(n):
        x = k // row[i]
        z = p[i] - 1
        tol = 0
        total = -10 * 10
        frag = []
        for j in range(row[i]):
            tol += c[z]
            z = p[z] - 1
            if tol >= total:
                total = tol
            frag.append(tol)
        if total > 0:
            x = k // row[i]
            w = k % row[i]
            score = (tol * x) + frag[w - 1]
            if ans<= score:
                ans = score
            z = p[i] - 1
            for l in range(row[i]-1):
                score -= c[z]
                z = p[z] - 1
                if ans <= score:
                    ans = score
        else:
            if ans <= total:
                ans = total
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
ans = -10**9


for i in range(1, n+1):
    x = p[i]
    y = c[x]
    y_max = y
    cnt = 1
    while cnt < k:
        x = p[x]
        y += c[x]
        if y_max < y:
            y_max = y
        cnt += 1
    ans = max(ans, y_max)
print(ans)

Submission status: Time Limit Exceeded

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

ans = -float('inf')
for i in range(n):
    s = []
    j = p[i]-1 
    s.append(c[j])
    while j != i:
        j = p[j]-1
        s.append(s[-1]+c[j])
    l = len(s)
    if k <= l:
        a = max(s[:k])
    elif s[-1] <= 0:
        a = max(s)
    else:
        w, r = divmod(k, l)
        a1 = s[-1]*(w-1) + max(s)
        a2 = s[-1]*w
        if r != 0:
            a2 += max(0, max(s[:r]))
        a = max(a1, a2)
    ans = max(ans, a)
print(ans)

'''

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

ans = -float('inf')
for i in range(n):
    j = p[i] - 1
    s = [c[j]]
    while j != i:
        j = p[j] - 1
        s.append(s[-1] + c[j])
    l = len(s)
    if k <= l:
        score = max(s[:k])
    elif s[-1] <= 0:
        score = max(s)
    else:
        w, r = divmod(k, l)
        score1 = s[-1] * (w - 1)
        score1 += max(s)
        score2 = s[-1] * w
        if r != 0:
            score2 += max(0, max(s[:r]))
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)
'''

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import os
import numpy as np

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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

P = list(map(lambda x:x-1,P))

res = -INF
used = [False] * N
ss = []

for i in range(N):
    # print('i',i)
    if used[i]:
        continue
    cur = i
    s = []
    while not used[cur]:
        used[cur] = True
        s.append(C[cur])
        cur = P[cur]
        # print(cur)
    ss.append(s)

# print(ss)

for vec in ss:
    M = len(vec)
    # 2周の累積和
    sum = [0]*(2*M + 1)
    for i in range(2*M):
        sum[i+1] = sum[i]+vec[i%M]
    
    # amari[r] := 連続するr個の最大値
    amari = [-INF]*M
    for i in range(M):
        for j in range(M):
            amari[j] = max(amari[j],sum[i+j] - sum[i])
    
    for r in range(M):
        if r>K:
            continue
        q = (K-r)//M
        if r==0 and q==0:
            continue
        if sum[M]>0:
            res = max(res, amari[r] + sum[M] * q)
        elif r > 0:
            res = max(res, amari[r])
print(res)

Submission status: Time Limit Exceeded

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

for i in range(n):
  now = i
  check = []
  max_point = c[p[now]]
  point = 0
  for j in range(k):
    if now in check:
      l = len(check)
      lastpoint = point * int(k/l)
      for e in range(k%l):
        now = p[now]
        lastpoint += c[now]
      each_point.append(lastpoint)
      
      now = check.index(now)+1
      c1 = check[now:]
      c2 = check[:now]
      for e in reversed(c1):
        each_point.append(p[e])
      for e in reversed(c2):
        each_point.append(p[e])
      break
    check.append(now)    
    now = p[now]
    point += c[now]
    if max_point < point:
      max_point = point
  
  each_point.append(max_point)
  
print(max(each_point))

Submission status: Time Limit Exceeded

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

for i in range(n):
  now = i
  check = []
  max_point = c[p[now]]
  point = 0
  for j in range(k):
    if now in check:
      l = len(check)
      lastpoint = point * int(k/l)
      for e in range(k%l):
        now = p[now]
        lastpoint += c[now]
      each_point.append(lastpoint)
      for e in range(l):
        lastpoint -= c[now]
        now = p.index(now)
      break
    check.append(now)    
    now = p[now]
    point += c[now]
    if max_point < point:
      max_point = point
  
  each_point.append(max_point)
  
print(max(each_point))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split(" "))
P = np.array(list(map(int, input().split(" "))))-1
C = list(map(int, input().split(" ")))

max_lst = []
for i in range(len(C)):
    tmp_max_lst = []
    idx = -1
    for j in range(K+1):
        if idx!=-1:
            if len(tmp_max_lst)==0:
                tmp = C[idx]
            else:
                tmp = tmp_max_lst[-1] + C[idx]
#             import pdb; pdb.set_trace()
            tmp_max_lst.append(tmp)
            idx = P[idx]
        else:
            idx = P[i]
    max_lst.append(max(tmp_max_lst))
#     import pdb; pdb.set_trace()
out = max(max_lst)
print(out)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain


def max_add_1_to_n(loop, n):
    # print('  max_add_1_to_n', loop, n)
    l = len(loop)
    acc = loop.copy()
    # print('    ', acc)
    max_val = max(acc)
    for i in range(1, n):
        for j in range(0, l):
            acc[j] += loop[(i + j) % l]
        # print("    ", acc)
        max_val = max(max(acc), max_val)
    return max_val


def max_add_0_to_n(loop, n):
    # print('  max_add_0_to_n', loop, n)
    if n >= 1:
        return max(max_add_1_to_n(loop, n), 0)
    else:
        return 0


def max_loop_k(loop, K):
    l = len(loop)
    if K <= 2 * l:
        return max_add_1_to_n(loop, K)
    # K は 2 * l より長い
    l_sum = sum(loop)
    if l_sum <= 0:
        return max_add_1_to_n(loop, l)
    else:
        Kdiv = K // l
        Kmod = K % l
        # print('  l Kdiv Kmod', l, Kdiv, Kmod)
        return max_add_0_to_n(loop, l + Kmod) + l_sum * (Kdiv - 1)


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):
    # 簡単のためインデックスを 0 からにする
    # (使用済みは -1 を入れる)
    P = [i - 1 for i in P]
    answer = -float("inf")
    for i0 in range(N):
        if P[i0] == -1:
            continue
        loop = []
        i = i0
        while P[i] != -1:
            loop.append(C[i])
            i_next = P[i]
            P[i] = -1
            i = i_next
        answer = max(answer, max_loop_k(loop, K))

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, K, P, C)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    ans = -INF
    for i in range(N):
        # iを含むサイクルの探索
        cycle = []
        c = i
        while True:
            c = P[c]
            cycle.append(c)
            if c == i:
                break
        len_cycle = len(cycle)
        # print(i, cycle, [C[j] for j in cycle])

        # 最大スコアの探索
        score = 0
        cycle_score_total = sum([C[j] for j in cycle])
        cycle_score_cum = list(itertools.accumulate([C[j] for j in cycle]))
        # 終了地点をjと決める
        for j in range(min(len_cycle, K)):
            score = cycle_score_cum[j]
            if cycle_score_total > 0:
                score += (K - j - 1) // len_cycle * cycle_score_total
            # print(j, score)
            ans = max(score, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

ans = -1_000_000_000
for i in range(N):
    S = [C[i]]
    p = P[i]
    while p != i:
        S.append(C[p])
        p = P[p]
    s = sum(S)
    n = len(S)
    acc = 0
    for i in range(min(n, K + 2)):
        acc += S[i]
        a = acc
        if s > 0:
            a += s * ((K - (i + 1)) // n)
        ans = max(a, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

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 = int(-1e14)
for i in range(n):
    tmp = []
    cycle = 0
    index = i
    while True:
        index = p[index]
        tmp.append(c[index])
        cycle += c[index]
        if i == index:
            break
    
    l = len(tmp)
    t = 0
    for j in range(l):
        t += tmp[j]
        if j >= k:
            break
        cur = t
        if cycle > 0:
            e = int((k-j-1) / l)
            cur += e * cycle
        ans = max(cur, ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
pc_list = []
max_score = -10**9

for m in range(n):
    score = 0
    num = p_list[m] - 1
    for l in range(k):
        score += c_list[num]
        num = p_list[num] - 1
        
        if score > max_score:
            max_score = score
 
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
pc_list = []
max_score = -10**9

for m in range(n):
    score = 0
    num = p_list[m] - 1
    for l in range(k):
        score += c_list[num]
        num = p_list[num] - 1
        
        if score > max_score:
            max_score = score
 
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
pc_list = []
max_score = -10**9

for i, j in zip(p_list, c_list):
    pc_list.append([i, j])

for m in range(n):
    score = 0
    num = pc_list[m][0] - 1
    for l in range(k):
        score += pc_list[num][1]
        num = pc_list[num][0] - 1
        
        if score > max_score:
            max_score = score
 
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
score = 0
s = []

for i in range(n):
    t = p[i] - 1
    for j in range(k):
        if j == 0:
            score += c[t]
            s.append(score)
        else:
            score += c[p[t] - 1]
            s.append(score)
            t = p[t] - 1
    score = 0

print(max(s))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K= map(int,input().split())

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

    ans = -1e18

    # N個のマス目のスタート位置を全て試す
    for si in range(N):
        x = si
        s = [] # 一周した時の特点を入れる
        # 周期を探す
        while(1):
            # マスの指定の位置へ移動する
            x = p[x]-1
            s.append(c[x])
            # スタートした位置に戻ってきたら終了
            if x == si: break

        # 周期の長さのうちどこで切るかを決める
        t = 0 # 累積和
        for i in range(len(s)):
            t += s[i]
            if (i+1 > K):break # 周期の数が回せない場合は飛ばす
            # 一周での合計が正の時 →　できるだけ周期を回したい
            now = t
            if (sum(s) > 0):
                e = (K-i-1) // len(s) # 回せる周期の数
                now += sum(s) * e 

            ans = max(ans, now)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
@jit
def main():
    N,K= map(int,input().split())

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

    ans = -1e18

    # N個のマス目のスタート位置を全て試す
    for si in range(N):
        x = si
        s = [] # 一周した時の特点を入れる
        # 周期を探す
        while(1):
            # マスの指定の位置へ移動する
            x = p[x]-1
            s.append(c[x])
            # スタートした位置に戻ってきたら終了
            if x == si: break

        # 周期の長さのうちどこで切るかを決める
        t = 0 # 累積和
        for i in range(len(s)):
            t += s[i]
            if (i+1 > K):break # 周期の数が回せない場合は飛ばす
            # 一周での合計が正の時 →　できるだけ周期を回したい
            now = t
            if (sum(s) > 0):
                e = (K-i-1) // len(s) # 回せる周期の数
                now += sum(s) * e 

            ans = max(ans, now)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
@jit
def main():
    N,K= map(int,input().split())

    p = [int(item) -1 for item in input().split()]
    c = [int(item) for item in input().split()]

    ans = -1e18

    # N個のマス目のスタート位置を全て試す
    for si in range(N):
        x = si
        s = [] # 一周した時の特点を入れる
        # 周期を探す
        while(1):
            # マスの指定の位置へ移動する
            x = p[x]
            s.append(c[x])
            # スタートした位置に戻ってきたら終了
            if x == si: break

        # 周期の長さのうちどこで切るかを決める
        t = 0 # 累積和
        for i in range(len(s)):
            t += s[i]
            if (i+1 > K):break # 周期の数が回せない場合は飛ばす
            # 一周での合計が正の時 →　できるだけ周期を回したい
            now = t
            if (sum(s) > 0):
                e = (K-i-1) // len(s) # 回せる周期の数
                now += sum(s) * e 

            ans = max(ans, now)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

p = [int(item) -1 for item in input().split()]
c = [int(item) for item in input().split()]

ans = -1e18

# N個のマス目のスタート位置を全て試す
for si in range(N):
    x = si
    s = [] # 一周した時の特点を入れる
    # 周期を探す
    while(1):
        # マスの指定の位置へ移動する
        x = p[x]
        s.append(c[x])
        # スタートした位置に戻ってきたら終了
        if x == si: break

    # 周期の長さのうちどこで切るかを決める
    t = 0 # 累積和
    for i in range(len(s)):
        t += s[i]
        if (i+1 > K):break # 周期の数が回せない場合は飛ばす
        # 一周での合計が正の時 →　できるだけ周期を回したい
        now = t
        if (sum(s) > 0):
            e = (K-i-1) // len(s) # 回せる周期の数
            now += sum(s) * e 

        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
cycles, check = [], [False]*n
for pi in p:
  if not check[pi-1]:
    curr, cycle = pi, []
    check[pi-1] = True
    while pi!=p[curr-1]:
      check[curr-1] = True
      cycle.append(c[curr-1])
      curr = p[curr-1]
  check[curr-1] = True
  cycles.append(cycle + [c[curr-1]])

scores = []
for cycle in (np.array(cycle) for cycle in cycles):
  for i in range(cycle.size):
    cum = np.roll(cycle, i).cumsum()
    if cum[-1] > 0 and k > cycle.size:
      scores.append(cum[-1]*(k//cycle.size-1) + np.concatenate([cum, cum[:k % cycle.size]+cum[-1]]).max())
    else:
      scores.append(cum[:min(k, cum.size)].max())

print(max(scores))