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:
LI = lambda: list(map(int, input().split()))

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

INF = 10 ** 10


def all_minus():
    for c in C:
        if c > 0:
            return False
    return True


def main():
    if all_minus():
        ans = max(C)
        print(ans)
        return
        
    ans = -INF
    for i in range(N):
        w = [0]
        d = {i: 0}
        j = 1
        x = P[i] - 1
        while x not in d:
            d[x] = j
            w.append(w[j - 1] + C[x])
            x = P[x] - 1
            j += 1

        a, b = d[x], j
        for _ in range(b - a):
            w.append(w[-1] + C[x])
            x = P[x] - 1

        if K < 2 * b - a or w[b] - w[a] <= 0:
            v = max(w[:K + 1])
            ans = max(ans, v)
            continue
        
        v = w[a]
        k = K - a
        r = k // (b - a) - 1
        k -= r * (b - a)
        v += r * (w[b] - w[a])
        v += max(w[a : a + k + 1]) - w[a]
        ans = max(ans, v)
    print(ans)
        
                
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,K = map(int, input().split())
    P = list(map(lambda s: int(s)-1, input().split()))
    C = list(map(int, input().split()))

    m = min(C)
    for i in range(N):
        n = i
        visited = [-1]*N
        c = 0
        S = []
        while visited[n] < 0:
            visited[n] = c
            c += 1
            n = P[n]
            if len(S) == 0:
                S += C[n],
            else:
                S += (S[len(S)-1]+C[n]),

        if K < len(S):
            m = max(m, max(S[:K]))
            continue

        pre = 0 if visited[n] == 0 else S[visited[n]-1]
        if S[len(S)-1] - pre <= 0:
            m = max(m, max(S))
            continue

        count = (K - visited[n]) // (len(S) - visited[n])
        rest = (K - visited[n]) % (len(S) - visited[n])
        l = S[visited[n]:visited[n]+rest]
        r = S[visited[n]+rest:]
        if len(l) > 0:
            m = max(m, max(l)+S[len(S)-1]*count)
        if len(r) > 0:
            m = max(m, max(r)+S[len(S)-1]*(count-1))
        if len(S[:visited[n]]) > 0:
            m = max(m, max(S[:visited[n]]))


    print(m)

main()

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

def get_loop_score(start): # return loop len and its loop score
    now_p=0
    visited=set()
    nxt=p[start]-1

    while True:
        nxt=p[nxt]-1
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    return now_p

def simulate(start,nokori): # ret max possible score
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]


    while True:
        nxt=p[nxt]-1
        visited.add(nxt)
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==nokori:
            break

    return max(p_lis)

for i in range(n):
    p_lis=[]

    cnt=0
    now_p=0
    nxt=p[i]-1

    visited=set()

    while True:
        now_p+=c[nxt]
        nxt=p[nxt]-1
        p_lis.append(now_p)

        cnt+=1
        if cnt==k:
            break

        if k>5010 and nxt in visited:
#            print(visited)
            break
        visited.add(nxt)

    if cnt!=k: # loop detected
#        print(i,p_lis)
        nokori = k-cnt
        loop_score=get_loop_score(nxt)
        if loop_score <= 0: # no loop
            nokori=len(visited)
        else: # loop as much as possible
            loops = nokori//len(visited) - 1
            now_p+= loops*loop_score
            nokori = loops*len(visited)

#        print("loop score:",loop_score)
        score = simulate(nxt,nokori)
        p_lis.append(score)

#    print(i,max(p_lis))

    ans=max(ans,max(p_lis))

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(N):
  p = 0
  f = P[i]
  for j in range(K):
    p += C[f-1]
    f = P[f-1]
    if p > ans:
      ans = p
if ans == 0:
  ans = max(C)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(_) for _ in input().split()]
p = [int(_)-1 for _ in input().split()]
c = [int(_) for _ in input().split()]
ans = -10**9
for i in range(n):
    idx = i
    s = [c[idx]]
    cu = -10**9
    ishuu = 0
    while 1:
        idx = p[idx]
        ishuu += 1
        if idx == i:
            break
        s.append(s[-1]+c[idx])
        # cu = max(s)
    if k >= ishuu:
        ans = max(ans, (k//ishuu-1)*s[-1] + max(s), max(s))

        if (k % ishuu) != 0:
            ans = max(ans, (k//ishuu)*s[-1]+max(s[: k % ishuu]))
        else:
            ans = max(ans, (k//ishuu)*s[-1])
    else:
        ans = max(ans, max(s[:k]))
    # print(s[-1], s, (k//ishuu-1)*s[-1] + max(s), ans),
    #       (k//ishuu)*max(s[-1], 0)+max(s[: k % ishuu]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k=map(int,input().split())
P = list(map(int,input().split()))
for i in range(n):P[i] -= 1
C = list(map(int,input().split()))
max_val = -inf
for i in range(n):
  now = i
  point = 0
  max_point = -inf
  j = k
  data = [[-1]*2 for i in range(n)]
  while j >0:
    j-=1
    now = P[now]
    point += C[now]
    max_point = max(max_point,point)
    # if data[now][0] == -1:
    #   data[now][0] = j
    #   data[now][1] = point
    # else:
    #   if j == 0:break
    #   elif point - data[now][1] > 0:
    #     point += (point - data[now][1]) * ((j-1)//(data[now][0]-j))
    #     if j % (data[now][0]-j) != 0:j %= (data[now][0]-j)
    #     else :j == (data[now][0]-j)
    #   else:
    #     if j % (data[now][0]-j) != 0:j %= (data[now][0]-j)
    #     else :j == (data[now][0]-j)
    max_point = max(max_point,point)
    # print(point)

  max_val = max(max_val,max_point)
  # print(max_point,i)
  # print(max_point)
  # print(max_point,point)
print(max_val)
# print(const,max_val,k)
# print(l*const)

Submission status: Time Limit Exceeded

Solution code:
N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
DispP = [0]*N
for TN in range(0,N):
    Now   = Next[TN]
    Point = GetP[Now]
    MAXP  = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        if Now==TN and Point>=0:
            RoopFlag = True
            break
        elif Now==TN and Point<0:
            RoopFlag = False
            break
        if MAXP<Point:
            MAXP = Point
    if RoopFlag:
        Omit = K-RoopC*((K//RoopC)-1)
        Point *= (K//RoopC)-1
        MAXP = Point
        for TO in range(0,Omit):
            Now = Next[Now]
            Point += GetP[Now]
            if MAXP<Point:
                MAXP = Point
    DispP[TN] = MAXP
print(max(DispP))

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

def get_loop_score(start): # return loop len and its loop score
    now_p=0
    visited=set()
    nxt=p[start]-1

    while True:
        nxt=p[nxt]-1
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    return now_p

def simulate(start,nokori): # ret max possible score
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]


    while True:
        nxt=p[nxt]-1
        visited.add(nxt)
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==nokori:
            break

    return max(p_lis)
  
for i in range(n):
    p_lis=[]

    cnt=0
    now_p=0
    nxt=p[i]-1

    visited=set()

    while True:
        now_p+=c[nxt]
        nxt=p[nxt]-1
        p_lis.append(now_p)

        cnt+=1
        if cnt==k:
            break

        if k>10000 and nxt in visited:
#            print(visited)
            break
        visited.add(nxt)

    if cnt!=k: # loop detected
#        print(i,p_lis)
        nokori = k-cnt
        loop_score=get_loop_score(nxt)
        if loop_score <= 0: # no loop
            nokori=len(visited)
        else: # loop as much as possible
            loops = nokori//len(visited) - 1
            now_p+= loops*loop_score
            nokori = loops*len(visited)

#        print("loop score:",loop_score)
        score = simulate(nxt,nokori)
        p_lis.append(score)

#    print(i,max(p_lis))

    ans=max(ans,max(p_lis))

print(ans)

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()))
temp_max = 0
for i in range(N):
 
  mass = i+1
  score = c_list[mass-1]
  if(i==0):
    temp_max = score
  elif(temp_max<score):
    temp_max=score
  for k in range(K-1):
    mass = p_list[mass-1]
    score += c_list[mass-1]
    if(temp_max<score):
      temp_max = score

print(temp_max)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [int(pn) for pn in input().split()]
c = [int(cn) for cn in input().split()]
ans = -(10**9)
for i in range(n):
  genzai = p[i] - 1
  score = c[genzai]
  better_score = score
  for _ in range(k-1):
    genzai = p[genzai] - 1
    score += c[genzai]
    if score > better_score:
      better_score = score
  if better_score > ans:
    ans = better_score
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()))
l = []
ans = []
for i in range(n):
    l.append(c[p[i]-1])
    x = p[i]-1
    while x != i and len(l) < k:
        l.append(l[-1] + c[p[x]-1])
        x = p[x]-1
    if len(l) < k:
        l.append(l[-1] + c[p[x]-1])
        x = p[x]-1
    while l[-1] > 0 and len(l) < k:
        l.append(l[-1] + c[p[x]-1])
        x = p[x] - 1
    ans.append(max(l))
    l = []
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k=map(int,input().split())
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
r1,r2,r3=deque(),deque(),deque()
for i in p:
  r1=[i]
  r2=[]
  for j in range(k):
    r2.append(c[r1[-1]])
    r1.append(p[r1[-1]])
    r3.append(sum(r2))
print(max(r3))

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 = max(C)
check = 0
for i in range(N):
    now_i = i
    for j in range(K):
        now_i=P[now_i]-1
        check+=C[now_i]
        ans=max(ans,check)
    check=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
pp = input().split()
cc = input().split()
npp=np.array(pp, dtype=int)
ncc=np.array(cc, dtype=int)

pointmax=-1E9

for istart in range(0,n):
  point=0
  loc=istart
  k_pointmax=-1E9
  for ik in range(1,k+1):
    loc=npp[loc]-1
    point+=ncc[loc]
    if (point >= k_pointmax): k_pointmax=point 

  if (k_pointmax >= pointmax): pointmax=k_pointmax
#nmax=n*10

print(pointmax)

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

loop = [0] * N
cnts = [0] * N
for i in range(N):
  nxt = P[i]-1
  tmp = 0
  for j in range(N):
    tmp += C[nxt]
    nxt = P[nxt]-1
    if nxt == i:
      tmp += C[nxt]
      cnt = j+2
      break
  loop[i] = tmp
  cnts[i] = cnt

mx = [0] * N
for i in range(N):
  if loop[i] > 0:
    mx[i] += ((K//cnts[i])-1) * loop[i]
    
for i in range(N):
  nxt = P[i]-1
  tmp = 0
  m = min(C) - 1
  for j in range((K%cnts[i])+cnts[i]):
    tmp += C[nxt]
    m = max(m, tmp)
    nxt = P[nxt]-1
  mx[i] += m

ans = max(mx)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
    ans = -10 ** 10
    for i in range(N): #好きなコマを選ぶ
        cnt = 0
        score = 0
        num = i
        while cnt < K:
            basho = P[num] - 1
            score += C[basho]
            num = basho
            cnt += 1
            if score > ans:
                ans = score
    print(ans)
    


    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from collections import Counter
import math
import numpy as np


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    p_rev = [0] * n
    for i in range(len(p)):
        p_rev[p[i] - 1] = i
    c = list(map(int, input().split()))

    dp = [[0] * n for i in range(k + 1)]

    for i in range(1, k + 1):
        for j in range(n):
            dp[i][j] = dp[i - 1][p_rev[j]] + c[j]
    print(np.max(dp[1:]))


if __name__ == "__main__":
    main()

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 = c[0] + c[p[0] - 1]
for i in range(n):
  scr = 0
  for j in range(k):
    i = p[i]
    i = i - 1
    scr = scr + c[i]
    if (scr > ans):
      ans = scr
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
r1,r2,r3=[],[],[]
for i in p:
  r1=[i]
  r2=[]
  for j in range(k):
    r2.append(c[r1[-1]])
    r1.append(p[r1[-1]])
    r3.append(sum(r2))
print(max(r3))

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

r=[[0]*n for ii in range(k)]
x=[0]*n
for jj in range(n):
  x[jj]=jj

for ii in range(k):
  for jj in range(n):
    x[jj]=p[x[jj]]-1
    if ii>0:
      r[ii][jj]=r[ii-1][jj]
    r[ii][jj]+=c[x[jj]]

import numpy as np
rr=max(r[0])
for ii in np.arange(1,k):
  rr=max(rr,max(r[ii]))
print(rr)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
cs = [int(i) for i in input().split()]

global_max = -10**10
past_score = [[]]*N
past_time = [[]]*N
for n in range(N):
    score = 0
    itta = [0]*N
    iru = n
    k = 0
    while k < K:
        score += cs[ps[iru]-1]
        k += 1
        if itta[iru] == 1:
            # print('itta')
            # print(f'iru is {iru}')
            # print(f'score is {score}')
            # print(f'past_score is {past_score}')
            if score > past_score[iru]:
                # print('plus loop')
                T = k - past_time[iru]  # 周期
                # print(f'周期は {T}')
                if K - k > (2 * T) + 1:
                    # print(f'繰り返しは{((K-k)//T - 1)}回')
                    # print('それによって', (((K-k)//T - 1)*(score - past_score[iru])))
                    score += (((K-k)//T - 1)*(score - past_score[iru]))
                    k += T * ((K-k)//T - 1)
                    # print(f'new score is {score}')
                    # print(f'new k is {k}')
            else:
                # print('break!')
                break
        itta[iru] = 1
        # print(iru)
        # print(ps[iru]-1)
        # print(f'score is {score}')
        global_max = max(score, global_max)
        past_score[iru] = score
        past_time[iru] = k
        iru = ps[iru]-1
print(global_max)

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 = [x-1 for x in P]
X = max(C)
for i in range(N):
  k = i
  S = 0
  SS = []
  for j in range(K):
    S += C[P[k]]
    SS.append(S)
    k = P[k]
  X = max(X,max(SS))
print(X)

Submission status: Time Limit Exceeded

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

def _d(s):
    #print(s)
    pass


N, K = map(int, input().split())
Ps = [int(i) for i in input().split()]
Cs = [int(i) for i in input().split()]

max_score = None
for cur in range(0, N):
    score = 0
    _d(f"{cur=} ****")
    for i in range(0, K):
        new_cur = Ps[cur] - 1
        cur = Ps[cur] - 1
        score += Cs[cur]
        _d(f"{cur=} {score=}")
        if max_score is None:
            max_score = score
        if score > max_score:
            max_score = score
            _d(f"{cur=} {score=} !!")

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, K = map(int, input().split())
  R_lst = list(map(int, input().split()))
  scores = list(map(int, input().split()))
  now = list(range(N))
  next = list(range(N))
  score_lst = [[0 for i in range(N)] for j in range(K)]
  for i in range(K):
    for j in range(N):
      next[j] = R_lst[now[j]]-1
      if i > 0:
        score_lst[i][j] = scores[next[j]] + score_lst[i-1][j]
      else:
        score_lst[i][j] = scores[next[j]]
    now = next
  max_lst = [0] * K
  for i in range(K):
    max_lst[i] = max(score_lst[i])
  print(max(max_lst))
main()

Submission status: Time Limit Exceeded

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

d = defaultdict(int)

# マスの数が5000以下であるため、KがNより大きい場合必ずループする
# それぞれのますが何回移動してからループに入るかを調べ残す
for i in range(N):
    idx = P[i]
    count = 0
    score = 0
    new_K = K
    while new_K > 0:
        # if (idx == P[i] and count != 0):
        #     break
        score += C[idx - 1]
        if (d[i + 1] == 0):
            d[i + 1] = score
        else:
            d[i + 1] = max(d[i + 1], score)
        idx = P[idx - 1]
        count += 1
        new_K -= 1


ans = -1 * 10 ** 10 + 7
for v in d.values():
    ans = max(ans, v)

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

been = [False]*N
n_been=0
loops = []

while True:
    #スタート地点を選ぶ
    for i in range(N):
        if not been[i]:
            now=i
            break
    else:
        break
    cand=[]       
    for _ in range(N):
        if been[now]:
            break
        else:
            cand.append(C[now])
            been[now]=True

        now = P[now]-1
    loops.append(cand)

ans=-10**20
for l in loops:
    m=len(l)
    sum_l = sum(l)
    if sum_l>0:
        k_gene = range(max(0,K-m), K+1)
    else:
        k_gene = range(1,min(m,K)+1)
    for k in k_gene:
        for i in range(m):
            if m-i>=K:
                cand = sum(l[i:i+k]) 
            else:
                cand = sum(l[i:]) +sum_l* ((k-m+i)//m) + sum(l[:(k-m+i)%m] ) 
            ans=max(ans,cand)
            

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

for i in range(n):
    p[i] = p[i] - 1

ans = -1e10

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# O(EV)
def bellman_ford(s):
    d = [0]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    x=s
    for tt in range(k):
        update = False # 更新が行われたか
        aa,bb,cc=g[x][0],g[x][1],g[x][2]
        if d[bb] < d[aa] + cc:
                d[bb] = d[aa] + cc
                update = True
            
        if not update:
            break

        x=bb
    return d

n,k=map(int,input().split())

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

if max(c)<0:
    print(max(c))
    exit()

for i in range(n):
    g.append((i,p[i]-1,c[p[i]-1]))

ans=0

for i in range(n):
  ans=max(ans,max(bellman_ford(i)))

print(ans)

Submission status: Time Limit Exceeded

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


def start_game(cursor_masu):
    # initialize
    visit_count = [0 for _ in range(N + 1)]
    point = 0
    points = list()

    # move
    for _ in range(K):
        cursor_masu = masues[cursor_masu]

        point += masu_points[cursor_masu]
        points.append(point)

        visit_count[cursor_masu] += 1

    return points


result = list()
for i in range(1, N + 1):
    result += start_game(i)
print(max(result))

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

L = [[] for i in range(n+1)]
length = [0]*(n+1)

for i in range(1,n+1):
    c = 0
    x = i

    s = set([])
    sw = 0
    for j in range(1,n+1):

        x = P[x]
        if P[x] in s and sw == 0:
            length[i] = j-1
            sw = 1
            
        s.add(P[x])
        point = C[x]
        if L[i] != []:
            L[i].append(L[i][-1]+C[x])
        else:
            L[i].append(C[x])
            
    if sw == 0:
        length[i] = n



ans = -float("Inf")

if k > n:

    
    for i in range(1,n+1):
        m = k//length[i]
        p = k%length[i]
        
        point = m * L[i][length[i]-1] + max(L[i][:p])

        ans = max(ans,point)

    
    for a in L[1:]:
        ans = max(max(a[:k]), ans)
else:
    for a in L[1:]:
        ans = max(max(a[:k]), ans)
        
print(ans)

Submission status: Time Limit Exceeded

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

score=[0]*n
for i in range(n):
    p[i]-=1
#print(p)
maxx=min(c)
for i in range(n):
    ind=i
    for move in range(k):
        ind=p[ind]
        score[i]+=c[ind]
        maxx=max(score[i],maxx)
print(maxx)

Submission status: Time Limit Exceeded

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

    max_sum=-10**9
    for i in range(N):
        m_sum=0
        k=i
        for j in range(K):
            m_sum += C_list[k]
            if m_sum > max_sum:
                max_sum=m_sum
            k=P_list[k]-1
    print(max_sum)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
pp = list(map(int, input().split()))
cc = list(map(int, input().split()))

import numpy as np
next_ = [0]*n
for i in range(n):
    next_[pp[i]-1] = i
scores = cc.copy()
maxscore = max(cc)
pos_now = np.arange(n)
for i in range(k-1):
    pos_now = [next_[pos] for pos in pos_now]
    scores = [score + cc[pos] for score, pos in zip(scores, pos_now)]
    maxscore = max(max(scores), maxscore)
print(maxscore)

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()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        rl.append(tc)
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        s.add(tc)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
Ps = list(map(int, input().split()))
Ps.insert(0,0)
Cs = list(map(int, input().split()))
Cs.insert(0,0)
Ls = [0] * (n + 1)  # 周期
As = [] # 回答候補

# 周期を見つける
for i in range(1,n + 1):
  count = 1
  temp = Ps[i]
  while temp != i:
    temp = Ps[temp]
    count += 1
  Ls[i] = count

# それぞれの最大値を見つける
for i in range(1, n + 1):
  ans = 0
  p = []  #途中経過集
  tempIndex = i
  tempSum = 0
  for j in range(Ls[i]):
    tempIndex = Ps[tempIndex]
    tempSum += Cs[tempIndex]
    p.append(tempSum)
  # print(f'p:{p}')
  # ansを求める
  if p[-1] <= 0:
    ans = max(p[:min(k,Ls[i])])
  else:
    q, r = divmod(k, Ls[i])
    # print(f'q,r,k,Ls[i]:{q}{r}{k}{Ls[i]}')
    start = q * p[-1]
    anss = [start]
    tempIndex = i
    tempSum = start
    for z in range(r):
      tempIndex = Ps[tempIndex]
      tempSum += Cs[tempIndex]
      anss.append(tempSum)
    ans = max(anss)
  As.append(ans)
print(max(As))

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 = (-1)*float('inf')

for start in range(1,n+1):
    now = start
    num = k
    now_p = 0
    for i in range(k):
        now = p[now-1]
        num -= 1
        now_p += c[now-1]
        ans = max(ans, now_p)

        if now == start:
            break
    if num > 0 and now_p > 0:
        junkai_num = k-num
        sho = num//junkai_num
        if sho != 0:
            now_p += now_p*sho
            num -= sho*junkai_num
        ans = max(ans, now_p)
        for i in range(num):
            now = p[now-1]
            num -= 1
            now_p += c[now-1]
            ans = max(ans, now_p)
print(ans)

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

    P_id = [p - 1 for p in P]

    max_ = -float('inf')

    for start in range(N):
        # print("#loop{}".format(start))

        # 解析

        current = start
        visited = [-1] * N
        visited[current] = 0

        history = [current]
        before_loop_ids = []
        loop_ids = []

        for step in range(1, N):  # 高々N回で抜ける
            next_ = P_id[current]
            if visited[next_] != -1:
                # loop_start = history.index(next_)
                loop_start = visited[next_]
                loop_ids = history[loop_start:]
                before_loop_ids = history[:loop_start]
                history.append(next_)
                break
            else:
                history.append(next_)
                current = next_
                visited[current] = step

        score_per_loop = sum([C[i] for i in loop_ids])
        # print('history', history)
        # print('before', before_loop_ids)
        # print('loop', loop_ids)
        # print('score_per_loop', score_per_loop)

        score = 0
        current = start
        num_move = K

        # before loop

        for i in range(len(before_loop_ids)):
            current = P_id[current]
            if num_move > 0:
                score += C[current]
                max_ = max(max_, score)
                num_move -= 1

        # loop
        if score_per_loop > 0:
            n = num_move // len(loop_ids)
            score += n * score_per_loop
            max_ = max(max_, score)
            num_move -= n * len(loop_ids)

        # after loop
        for i in range(num_move):
            current = P_id[current]
            if num_move > 0:
                score += C[current]
                max_ = max(max_, score)
                num_move -= 1

    print(max_)


if __name__ == '__main__':
    main()

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 = [0] * n

for i in range(n):
  score = 0
  tmp_list = []
  index = p[i]
  for _ in range(min(k,k)):
    tmp = score + c[index-1]
    score = tmp
#    score = max(score,tmp)
    tmp_list.append(tmp)
    index = p[index-1]
  ans[i] = max(tmp_list)
print(max(ans))
#print(ans)