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())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

mv_array = [[] for _ in range(n)]
score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score


for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    for j in range(k):
        pos = p[pos]-1
        if pos in mv_array[i]:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        mv_array[i].append(pos)
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print(max(score_array))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# from pdb import set_trace
N, K = map(int, input().split(" "))
P = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))

for x, n in enumerate(range(N)):
    scores = [0]
    for k in range(K):
        p = P[n]
        scores.append(scores[-1]+C[p-1])
        n = p - 1
    if x==0:
        vmax = max(scores[1:])
    else:
        vmax = max(vmax, max(scores[1:]))
print(vmax)

Submission status: Time Limit Exceeded

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

p = [i-1 for i in p]
import numpy as np
tuuka_id = []
point_list = []

#check = []
for mass in range(n):
  score = 0
  scorelist = []
  move_cnt = 0
  st_mass = mass
  if mass in tuuka_id:
    continue
  
  tuuka_id.append(mass)
  while True:
    mass = p[mass]
    #print(mass, c[mass])
    tuuka_id.append(mass)
    score += c[mass]
    scorelist.append( c[mass] )
    move_cnt += 1
    
    if mass == st_mass:
      break
  #check.append( [score, move_cnt, scorelist] )
  
  scorel3 = scorelist *3
  if move_cnt*2 <= k:
    mul = max(0,(k // move_cnt-1))
    k_res = move_cnt + k % move_cnt
    res_val = max([ np.cumsum(scorel3[i:i+k_res]).max() for i in range( len(scorelist) )])
    point_list.append( max( score, res_val, score*mul + res_val ) )
  else:
    k_res = k
    res_val = max([ np.cumsum(scorel3[i:i+k_res]).max() for i in range( len(scorelist) )])
    point_list.append( res_val  )
  #print(score, res_val, mul)
print(max(point_list))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import glob

class InputGenerator(object):
    def __init__(self, input_path=None):
        if input_path != None:
            self.g = self.input_generator(input_path)
        else:
            self.g = None

    def input_generator(self, input_path):
        with open(input_path) as f:
            for line in f:
                yield line

    def get_input(self):
        if self.g == None:
            return input()
        else:
            return next(self.g)

def get_max_local_trip(sorted_c_list, local_trip_k):
    n = len(sorted_c_list)
    local_trip_sum_max = -1e10
    sorted_c_list += sorted_c_list
    for i in range(1, local_trip_k+1):
        local_trip = sorted_c_list[0:i]
        local_trip_sum = sum(local_trip)
        # print(i, j, local_trip, len(local_trip), local_trip_sum)
        if local_trip_sum > local_trip_sum_max:
            local_trip_sum_max = local_trip_sum

    return local_trip_sum_max

def get_local_kn(sorted_c_list, k):
    n = len(sorted_c_list)

    if k % n == 0:
        num_round    = k // n - 1
        local_trip_k = n
    else:
        num_round    = k // n
        local_trip_k = k % n
        # print(num_round, local_trip_k)

    return num_round, local_trip_k

def get_local_max_score(sorted_c_list, k):
    num_round, local_trip_k = get_local_kn(sorted_c_list, k)
    round_sum = sum(sorted_c_list)
    local_max_score = get_max_local_trip(sorted_c_list, local_trip_k)
    # print('max', local_max_score, round_sum, num_round, local_trip_k)

    if round_sum > 0 and num_round > 0:
        local_max_score += (num_round * round_sum)

    return local_max_score

def solve(gen):
    n, k = list(map(int, gen.get_input().rstrip().split()))
    p_list = list(map(int, gen.get_input().rstrip().split()))
    c_list = list(map(int, gen.get_input().rstrip().split()))
    # print(n, k)
    # print(p_list)
    # print(c_list)

    sorted_c_list = []
    global_max_score = -1e10
    unvisited_list = list(range(n))
    for i in unvisited_list:
        start_i = i
        while True:
            next_i = p_list[i] - 1
            sorted_c_list.append(c_list[next_i])
            i = next_i
            if i == start_i:
                local_max_score = get_local_max_score(sorted_c_list, k)
                if global_max_score < local_max_score:
                    global_max_score = local_max_score
                sorted_c_list = []
                break

    print(global_max_score)

if __name__ == '__main__':
    test_flag = len(sys.argv) > 1

    if test_flag == True:
        file_path_list = sorted(glob.glob('test/*'))
    else:
        file_path_list = [None]

    for file_path in file_path_list:
        gen = InputGenerator(file_path)
        solve(gen)

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()))
mx=-float("inf")

from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
for i in range(n):

  sc=0
  pn=i
  mass=[0]*n
  for j in range(k):
    pn=p[pn]-1
        
    if mass[pn]!=0:
      lpk=j-mass[pn][0]
      amari=(k-j)%lpk
      lpsc=sc-mass[pn][1]
      #print(sc)
      for l in range(amari):
        sc+=c[pn]
        pn=p[pn]-1
        mx=max(mx,sc)
      sc+=lpsc*(Decimal(str((k-j-amari)/lpk)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
      
      mx=max(mx,sc)
      #print(lpk,j,amari,lpsc)
      break
    
    mass[pn]=[j,sc]
    sc+=c[pn]
    mx=max(mx,sc)
  #print(mass)
print(mx)

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

ans = -10000000000
for i in range(N):
    x = i
    A = [C[x]]
    while(P[x] != i and len(A)<K):
        x = P[x]
        A.append(A[-1] + C[x])
    if A[-1] > 0 and len(A) < K:
        for j in range(len(A)):
            A[j] += A[-1] * ((K - j - 1) // len(A))
    ans = max(ans, max(A))

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 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt_tmp = nxt
    nxt = p[nxt]
    for j in range(extra):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    score += score * a
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        nxt = p[nxt]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


show_flg=False
show_flg=True

ans=0

n,k=LI()
p=LI_()
c=LI()

rp=[-1]*n
pp=[-1]*n
def roop(y):
    pt=0
    if rp[y]!=-1:
        return rp[y],pp[y]
    x=y
    for i in range(n):
        x=p[x]
        pt+=c[i]
        if x==y:
            r=i+1
            break
    rp[y]=r
    pp[x]=pt
    for i in range(r):
        pp[x]=pt
        rp[x]=r
        x=p[x]
        
        
    return r,pt

def tr(x,t):
    pt=0
    rt=-inf
    for i in range(t):
        x=p[x]
        pt+=c[x]
        rt=max(rt,pt)
    return rt



ans=-inf
for i in range(n):
    r,ppx=roop(i)
    if k<=n:
        tmp=tr(i,k)
    else:
        tmp0=tr(i,k)    
        tmp1=(k//r)*ppx+tr(i,k%r)
        tmp2=max(0,(k//r)-1)*ppx+tr(i,n)
        tmp=max(tmp0,tmp1,tmp2)
    ans=max(tmp,ans)
    #show(i,(r,pp),tr(i,n),(k//r),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()))

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

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (t if k < r else 0))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i]-=1
#print(P)
C = list(map(int,input().split()))
Flag = True
for c in C:
  if c >= 0:
    Flag = False
    break
if Flag:
  print(max(C))
  exit()
L = []
for i in range(N):
  visited = set([])
  now = i
  temp = []
  while now not in visited:
    nxt = P[now]
    visited.add(now)
    temp.append(C[nxt])
    now = nxt
  L.append(temp)
#print(L)
ans = 0
S = []
for X in L:
  start = [0]
  for i in range(len(X)):
    temp = start[-1]+X[i]
    start.append(temp)
  S.append(start)
#print(S)
for X,SS in zip(L,S):
  n = len(X)
  cycle_sum = SS[-1]
  if K <= n:
    kouho = max(SS[:K+1])
  elif cycle_sum < 0:
    kouho = max(SS)
  else:
    amari = K%n
    loop = K//n
    first = 0 #余りよりも後で最大
    second = 0 #余りよりも前で最大
    first = (loop-1)*cycle_sum + max(SS)
    second = loop*cycle_sum + max(SS[:amari+1])
    kouho = max(first,second)
  ans = max(ans,kouho)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
from collections import deque
ans = -2*10**9
for idx, root in enumerate(P):
    scores = [C[root]]
    p = P[root]
    while True:
        scores.append(scores[-1] + C[p])
        p = P[p]
        if p == root:
            break

    sc = scores[-1]
    if sc <= 0:
        if k < len(scores):
            ans = max(ans, max(scores[:k]))
        else:
            ans = max(ans, max(scores))
    else:
        kk, r = divmod(k, len(scores))
        if r == 0:
            ans = max(ans, kk*sc, (kk-1)*sc + max(scores))
        else:
            ans = max(ans, kk*sc + max(scores[:r]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    (n,k),p,c=[[*map(int,t.split())]for t in open(0)]
    m=-10**18
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    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 = []
for i in range(N):
  x = i
  ans = 0
  for s in range(K):
    ans += C[P[x]-1]
    x = P[x]-1
    ANS.extend([ans])
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()))
seen = set()
circuits = []

for x in range(N):
    cir = []
    point = 0
    while True:
        if x in seen: 
            if cir != []: circuits.append((cir,point))
            break
        seen.add(x)
        point += C[x]
        cir.append(x)
        x = P[x] - 1
ans = -1000000000000
for x in circuits:
    tmp = 0
    if x[1] > 0 and K >= len(x[0]) * 2: 
        tmp = (K // len(x[0]) - 1) * x[1]
        r = K % len(x[0]) + len(x[0])
    else:
        r = K
    for y in x[0]:
        tmp2 = 0
        for _ in range(r):
            y = P[y] - 1
            tmp2 += C[y]
            ans = max(ans, tmp + tmp2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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()))
if max(c) <= 0:
    print(max(c))
    exit()
ans = 0
for begin in range(n):
    i = p[begin]
    s = c[i]
    round = 1
    score = 0
    kk = 0
    while i != begin:
        i = p[i]
        s += c[i]
        round += 1
    if k < round:
        kk = k
    else:
        if s > 0:
            score += s * (k // round)
            kk = k % round
        else:
            kk = round
    smax = 0
    now = 0
    i = begin
    while kk > 0:
        i = p[i]
        now += c[i]
        smax = max(now, smax)
        kk -= 1
    roundmax = 0
    if k // round >= 1 and s > 0:
        kk = round
        now = 0
        i = begin
        while kk > 0:
            i = p[i]
            now += c[i]
            roundmax = max(now, roundmax)
            kk -= 1
        ans = max(ans, score-s+roundmax, score+smax)
    else:
        ans = max(ans, score + smax)

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**9

for i in range(1,n+1):
    m=i
    co=0
    an=0
    for j in range(n):
        m=p[m-1]
        co+=1
        if m==i:
            break      
    m=i
    x=[0 for j in range(co+1)]
    for j in range(co):
        m=p[m-1]
        x[j+1]=x[j]+c[m-1]
    
    if k<=co:
        ans=max(ans,max(x[j] for j in range(1,k+1)))
    else:
        if x[-1]<=0:
            ans=max(ans,max(x[j] for j in range(1,co+1)))
        else:
            f=max(0,k%co-1)
            an+=x[-1]*f
            s=k-f*co
            
            m=i
            for i in range(s):
                m=p[m-1]
                an+=c[m-1]
                ans=max(ans,an)
    
print(ans)

Submission status: Time Limit Exceeded

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

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

answer = max(C)
for i in range(N):
  pos = P[i] - 1
  score = C[pos]
  score_list = [score]
  step = 1
  while pos!=i and step<K:
    pos = P[pos] - 1
    score += C[pos]
    score_list.append(score)
    step += 1
  if score_list[-1]>0 and step<K:
    loop = K//step
    amari = K%step
    score_max_tmp = 0
    for j in range(step):
      if j<amari:
        score_max_tmp = max(score_max_tmp, score_list[-1]+score_list[j])
      else:
        score_max_tmp = max(score_max_tmp, score_list[j])
    score_max = score_max_tmp+score_list[-1]*(loop-1)
  else:
    score_max = max(score_list)
  answer = max(answer,score_max)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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()]

    ans = -float("inf")
    for i in range(N):
        next = P[i] - 1
        cnt = 0
        tmp = 0

        f = False
        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if next == i:
                break
            if cnt == K or next == i:
                f = True
                break
            next = P[next] - 1

        if f or tmp <= 0:
            continue

        q, r = divmod(K, cnt)
        next = P[i] - 1
        tmp *= q
        cnt = 0
        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == r:
                break
            next = P[next] - 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
INF = float('inf')
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = -INF
for init in range(1, N + 1):   # 初めの場所をiとする
    score = defaultdict(int)  # int/bool/list....
    visited = defaultdict(bool)  # int/bool/list....
    visited[init] = True
    i = init
    max_init = -INF
    for k in range(1, K + 1):
        prev = i
        i = P[i]    # k回移動後に着くところ

        score[i] = score[prev] + C[i]
        max_init = max(max_init, score[i])

        if visited[i]:
            if k == K:
                break # これ以上移動できない
            start = i   # ループを開始するノード
            loop_score = 0
            loop_len = 0
            # ループを探す
            jj = start
            while P[jj] != start:
                jj = P[jj]
                loop_score += C[jj]
                loop_len += 1
            loop_score += C[start]
            loop_len += 1

            loop_num = (K - k) // loop_len # ループをあと何回回れるか
            loop_rem = (K - k) % loop_len

            if loop_rem == 0:
                loop_num -= 1
                loop_rem = loop_len

            jj = start
            temp = 0
            temp_max = 0
            for l in range(loop_rem):
                jj = P[jj]
                temp += C[jj]
                temp_max = max(temp_max, temp)

            loop_max = temp_max + max(loop_num * loop_score, 0)
            max_init = max(max_init, score[start] + loop_max)
            break

    max_score = max(max_score, max_init)

if max_score == -INF:
    max_score = max(C[1:])

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
P = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
score_candidate = []
for n in range(N):
    score_candidate_tmp = []
    # current position
    cp = n
    for k in range(K):
        # next position
        np = P[cp] -1
        if score_candidate_tmp == []:
            score_candidate_tmp.append(C[np])
        else:
            score_candidate_tmp.append(score_candidate_tmp[-1] + C[np])
        cp = np
    score_candidate.append(max(score_candidate_tmp))
print(max(score_candidate))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    # DFSでやる?
    def rec(now: int, score: int, cnt: int):
        nonlocal ans
        if cnt >= k:
            ans = max(ans, score)
            return
        seen[now] = True
        rec(P[now], score + C[P[now]], cnt + 1)

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

    seen = [False] * N
    ans = -(10 ** 9)
    for k in range(1, K + 1):
        for i in range(N):
            rec(i, 0, 0)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# template: v1.3.1

import io
import sys
import math

### DEBUG ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
2 3
2 1
10 -7
"""
_EXPECTED = """\
8

"""
if _DEB:
    sys.stdin = io.StringIO(_INPUT)
    print("!! Debug Mode !!")

def logd(str):
    if _DEB: print(f"[deb] {str}")


### INPUT ####

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

'''
n=5000
k=10**9-7
p=[i for i in range(1,n+1)]
c=[i for i in range(1,n+1)]
'''


### Solve ####
def solve():
    # sorted C
    from collections import deque
    cq=[]

    pcnt=0
    pi=0
    cq.append(deque([]))
    while pcnt < n:
        if p[pi] == -1:
            pi%=n
            if len(cq[-1]) != 0:
                cq.append(deque([]))
            pi+=1
            continue

        i=p[pi]-1
        cq[-1].append(c[i])
        p[pi]=-1
        pi=i
        pcnt+=1
    
    maxs=-float("inf")
    maxsi=-1
    minstep=min(n,k)
    
    for i,q in enumerate(cq):
        kqdiv,kqmod=divmod(k,len(q))
        s=sum(q)
        lq= len(q)
        if s <= 0 or minstep == k:
            #Loop不要
            for qi in range(lq):
                msc=1
                while msc <= minstep:
                    ss=0
                    for st in range(msc):
                        idx=(qi+st)%lq
                        ss+=q[idx]
                    maxs=max(maxs,ss)
                    msc+=1

        else:
            #Loop価値あり
            skn=s*(kqdiv)
            for qi in range(lq):
                msc=1
                while msc <= minstep:
                    ss=0
                    for st in range(msc):
                        idx=(qi+st)%lq
                        ss+=q[idx]
                    if msc <= kqmod:
                        maxs=max(maxs,ss+(skn))
                    else:
                        maxs=max(maxs,ss+(skn-s))
                    msc+=1
    ans=maxs

    # OUPUT
    ans = str(ans)
    print(ans)
    return ans

### MAIN ###
if __name__ == "__main__":
    ans = solve()

    # Checker
    if _DEB:
        if _EXPECTED.strip() == ans.strip(): print("\n!! Success !!")
        else: print(f"\n!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

vis = np.zeros(N, dtype=bool)
ans = np.zeros(N, dtype=int) - 10 ** 10
for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print(ans.max().item())