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:
from copy import copy
n, k = map(int, input().split())
p = list(map(int,input().split()))
c = list(map(int, input().split()))
di = {}
for i in range(n):
    di[i+1] = False
l = 1
cc = 0
per = [] # ループの順番
while cc < n:
    tmp = []
    while True:
        if di[l]:
            break
        else:
            tmp.append(l)
            di[l] = True
            cc += 1
            l = p[l-1]
    per.append(tmp)
    for i in range(n):
        if not di[i+1]:
            l = p[i]
#print(per)
dd = {} # 何個目のループに属するか
for i in range(n):
    dd[i+1] = 0
for i in range(len(per)):
    for j in per[i]:
        dd[j] = i
#print(dd)
su = [] # ループ１週の和
for i in range(len(per)):
    tmp = 0
    for j in per[i]:
        tmp += c[j-1]
    su.append(tmp)
#print(su)
s2 = [] # ループ１週何個か
for i in range(len(per)):
    s2.append(len(per[i]))
#print(s2)
ans = -1*(10**10)
#d2 = {} # per[dd]の中でなんばんめにあるか(0インデックス)
#for i in range(len(per)):
#    for j in range(len(per[i])):
#        d2[per[i][j]] = j
#print(d2)
for i in range(n):
    loop = dd[i+1]
    w = i+1
    kk = copy(k)
    if k < s2[loop]:
        tmp = 0
        m = -10**9
        for j in range(k):
            w = p[w-1]
            tmp += c[w-1]
            m = max(m, tmp)
        ans = max(ans, m)
    else:
        if su[loop] <= 0:
            tmp = 0
            m = -10**9
            for j in range(k):
                w = p[w-1]
                tmp += c[w-1]
                m = max(m, tmp)
            ans = max(ans, m)
        else:
            m_loop = kk // (s2[loop])
            m_loop -= 1
            kk -= m_loop * s2[loop]
            tmp = su[loop]*m_loop
            m = -10**9
            for j in range(kk):
                w = p[w-1]
                tmp += c[w-1]
                m = max(m, tmp)
            ans = max(ans, m)
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 = -99999999999999999999999
for i in range(n):
    base = c[i]
    ans_check = c[i]
    ttt = p[i]-1
    for j in range(k-1):
        ans_check += c[ttt]
        ttt = p[ttt] - 1
        if base < ans_check:
            base = ans_check
    
    if base > ans:
        ans = base
        
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()))

k = 0
score_list = []
for i in range(N):
  position = i
  score = 0
  for k in range(K):
  	position = P[position] - 1
  	score += C[position]
  	score_list.append(score)

print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    N,K = LMIIS()
    P = list(map(lambda x: int(x)-1,input().split()))
    C = LMIIS()
    score_sets = []
    used = [False]*N
    tmp = P[0]
    for i in range(N):
        if not used[i]:
            tmp = i
            score_set = []
            while not used[tmp]:
                used[tmp] = True
                tmp = P[tmp]
                score_set.append(C[tmp])
            score_sets.append(score_set)
        
    ans = -INF
    for score_set in score_sets:
        # 合計が最大になる区間を探す
        tmp_max = -INF
        base_cum = 0
        sum_score_set = sum(score_set)
        remain_K = K
        if sum_score_set > 0:
            num = max(0,K//len(score_set)-1)
            base_cum = sum_score_set * num
            remain_K -= num*len(score_set)


        for i in range(len(score_set)):
            cum = base_cum
            for j in range(i,i+remain_K):
                cum += score_set[j%len(score_set)]
                tmp_max = max(tmp_max,cum)
        ans = max(ans,tmp_max)
                
    print(ans)




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

dp = [[0]*(n+1) for _ in range(k+1)]
for i in range(k):
    for j in range(n):
        dp[i+1][P[j]-1] = dp[i][j]+C[P[j]-1]
ans = max(list(map(lambda x: max(x[:-1]), dp[1:])))
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()))

check=[0]*n
group=[]

for i in range(n):
    tmp=i
    if check[tmp]==0:
        tmp_group=[]
        while check[tmp]==0:
            tmp_group.append(tmp)
            check[tmp]=1
            tmp=p[tmp]-1

        group.append(tmp_group)

ans="start"

#startの最低とgoalの最高の和
for item in group:
    
    #一周すると何になるか。これはどこスタートでも同じ
    circle=0
    cnt=k
    if len(item)<k:
        for v in item:
            circle+=c[v]
        cnt=k-len(item)
    
    #一周した後のあまりで最強を探す


    goal=(-1)*(10**18)
    
    #startは各groupのindexが入ってる
    for start in range(len(item)):
        tmp=0
        #print("start",item,start,cnt)
        for i in range(start,start+cnt):
            #print(">>",i)
            tmp+=c[item[i%len(item)]]
            #print(item[i%len(item)],c[item[i%len(item)]])
            goal=max(goal,tmp)

    #print(item,circle,goal)
    if ans=="start":
        ans=goal+max(0,circle)
    else:
        ans=max(ans,goal+max(0,circle))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = [0]
p = list(map(int, input().split()))
for j in p:
    P.append(j)
C = [0]
c = list(map(int, input().split()))
for j in c:
    C.append(j)

ans = []
for i in range(1, N + 1):
    points = []
    has_been_points = []
    k = K
    x = i
    old_point = 0
    for j in range(K):
        x = P[x]
        has_been_points.append(x)
        new_point = C[x]
        points.append(old_point + new_point)
        k -= 1

        # if has_been_points.count(x) > 2:
        #     loop_first = has_been_points.index(x)
        #     loop_end = j
        #     for k in range(len(has_been_points[loop_first, loop_end + 1])):
        #         pass
        #
        #

        old_point += new_point
    ans.append(max(points))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import bisect
from collections import deque
from copy import copy, deepcopy
 
 
def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
    ans=-10e10
    for p in range(1,N+1):
        tmp_max=-10e10
        tmp_sum=0
        tmp_ans=-10e10
        _p=p
        end=False
        for i in range(N):            
            if p==P[_p-1]:
                end=True
            _p=P[_p-1]
            tmp_sum+=C[_p-1]
            #print("tmp_sum:",tmp_sum)
            tmp_max=max(tmp_max,tmp_sum)
            if end:
                break

        if tmp_sum<=0:
            tmp_ans=tmp_max
        else:
            tmp_ans=(K//(i+1))*tmp_sum
            #print("tmp_ans",tmp_ans)
            tmp_sum=0
            tmp_max=0
            for j in range(K%(i+1)):
                _p=P[_p-1]
                tmp_sum+=C[_p-1]
                tmp_max=max(tmp_max,tmp_sum)
            tmp_ans+=tmp_max
        #print(tmp_ans)
        ans = max(ans,tmp_ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))
check_dict = {}
loop_list = []
flag = 0
for i in range(n):
    if i in check_dict:
        continue
    next_no = i
    score_list = []
    check_dict[next_no] = 1
    while True:
        score_list.append(c_list[next_no])
        if flag == 0:
            if c_list[next_no] > 0:
                flag = 1
        next_no = p_list[next_no] - 1
        if next_no in check_dict:
            break
        else:
            check_dict[next_no] = 1
    loop_list.append(score_list)
if flag == 0:
    print(max(c_list))
else:
    max_score = 0
    for score_list in loop_list:
        if sum(score_list) <= 0 or len(score_list) <= k:
            for start in range(len(score_list)):
                score = 0
                for i in range(start, start + k):
                    temp_i = i % len(score_list)
                    score += score_list[temp_i]
                    if score > max_score:
                        max_score = score
        else:
            t = k // len(score_list)
            sum_score = sum(score_list) * t
            t = k - t * len(score_list)
            for start in range(len(score_list)):
                score = 0
                for i in range(start, start + t):
                    temp_i = i % len(score_list)
                    score += score_list[temp_i]
                    if score + sum_score > max_score:
                        max_score = score + sum_score
    print(max_score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (acos, asin, atan, ceil, cos, degrees, factorial, hypot, inf,
                  log2, pi, radians, sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))

# For getting input from input.txt file
#sys.stdin = open('input.txt', 'r')

# Printing the Output to output.txt file
#sys.stdout = open('output.txt', 'w')


def main():
    n, k = invr()
    p = inlist()
    c = inlist()
    ans = max(c)
    for i in range(n):

        tot = c[i]
        curr = p[i]
        mx = tot
        for m in range(k-1):
            tot += c[curr-1]
            mx = max(tot, mx)
            curr = p[curr-1]
        ans = max(ans, mx)
    print(ans)


# ab
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    main()

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

ans = c[0]

for i in range(n):
  #print('試行')
  np = i
  point = 0
  j = 0
  while(j<k):
    #print(j, np, point)
    j += 1
    np = p[np] - 1
    if j > 1 and np == p[i] - 1: #1週してポイントが1以上なら
      if point > 0:
      	#print('roop')
      	#print(point, j)
      	point = point*((k//(j-1)) - 1)
      	j = (j-1)*((k//(j-1)) - 1)
      	while(j<k):
        	j+=1
        	np = p[np]-1
        	point += c[np]
        	#print(j,point)
        	if point > ans:
          		ans = point
      break
    point += c[np]
    if point > ans:
      ans = point
   
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p_lis = list(map(int, input().split()))
score_lis = list(map(int, input().split()))

visited = [False]*n
# same_group = [False]*n

ans = -10**9


for start in range(n):
    visited = [False]*n
    point_tmp = 0
    visited[start] = True
    # same_group[start] = True
    tmp = start

    for i in range(k):
        tmp = p_lis[tmp-1]
        point_tmp += score_lis[tmp-1]
        visited[tmp-1] = True
        # same_group[tmp-1] = True
        
        if point_tmp > ans:
            ans = point_tmp

        # ループ
        if tmp == start-1:
            if point_tmp > 0:
                p_cycle = point_tmp
                l = visited.count(True)
                t = k//l
                amari = k%l
                point_tmp = 0
                tmp = start
                for j in range(l):
                    tmp = p_lis[tmp-1]
                    point_tmp += score_lis[tmp-1]

                    if j+1 <= amari:
                        ans = max(ans, point_tmp+p_cycle*(t))
                    else:
                        ans = max(ans, point_tmp+p_cycle*(t-1))
            break

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

visited = [False]*N
lp = [[0] for _ in range(N)]

lidx = 0
for s in range(N):
    if visited[s]:
        continue

    nex = s
    while not visited[nex]:
        visited[nex] = True
        now = P[nex]
        nex = now
        lp[lidx].append(lp[lidx][-1] + C[now])

    lidx += 1

ans = -(10**10)

for k in range(lidx):
    loop = lp[k]
    km = loop[-1]
    
    lenloop = len(loop)-1

    pt = 0

    kk = K

    x = max(kk//lenloop-1, 0)
    if km > 0:
        pt += x*km
    kk -= x*lenloop

    # print(x, kk, km)

    for i in range(lenloop*2):
        loop.append(loop[i+1]+km)
    
    for i in range(lenloop):
        for j in range(i+1, i+kk+1):
            # print(i, j, loop[j]-loop[i])
            ans = max(loop[j]-loop[i]+pt, ans)

# print(lp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    n,k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = []

    def recur(n,m,cnt,l):
        go = p[n]-1
        m += c[go]
        l.append(m)
        if cnt == k:
            return max(l)
        if n in l:
            return max(l)
        return recur(go,m,cnt+1,l)

    for i in range(n):
        l = []
        ans.append(recur(i,0,1,l))
    print(max(ans))

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()))
m = None
for i in range(N):
    nx = P[i] - 1
    r = 0
    for j in range(K):
        r += C[nx]
        m = r if m is None else max(r, m)
        nx = P[nx] - 1
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys, math

def calcweight_bellman_ford(N_vertices, edges, times, cost3, inf):
    is_confirmed = [False] * N_vertices

    distances = [0] * N_vertices
    distances[-1] = inf
    flag_updated = True
    """
    edges: [start, dest, cost] -> [cost, start, end]
    """
    moved = [0] * N_vertices
    for time in range(times):
        for edge in edges:
            left = edge[1]
            dest = edge[2]
            cost = edge[0]
            if(distances[left] == inf or moved[left] >= times):
                continue

            if(distances[dest] > distances[left] + cost ):
                distances[dest] = distances[left] + cost
                moved[dest] = moved[left]+1

    if(moved[-1]==1):
        distances[-1] = cost3 * (-1)

    return distances[-1]


if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )

    edges = [ [] for _ in range(N+2) ]
    for i in range(N):
        edges[0].append([0, i]) #[cost, edge]
    for i in range(1, N+1):
        edges[i].append([0, N+1])
    for i in range(N):
        edges[i].append([ CList[i]*(-1), PList[i] ])
    """
    N, K= map(int, input().strip().split() )
    PList = list( map(int, input().strip().split() ) )
    CList = list( map(int, input().strip().split() ) )
    inf = 10**6

    """
    N_vertices = 2+N
    """
    N_vertices = 1+N

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i]*(-1), i, PList[i]-1 ])
        costs.append(CList[i])

    cost = max(costs)
    """
    for i in range(N):
        edges3.append([0, 0, i+1]) #[cost, start, end]
    """
    for i in range(N):
        edges3.append([0, i, N])


    """
    weight = -inf
    for i in range(1, N+1):
        weight2 =(-1) * calcweight_bellman_ford(N_vertices, edges3, K+1, cost, inf)
        if(weight2 > weight):
            weight = weight2
    """
    weight =(-1) * calcweight_bellman_ford(N_vertices, edges3, K+1, cost, inf)
    #weight= calcweight_bellman_ford(N_vertices, 0, edges3, K+2, cost, inf)


    print( weight)

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

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]
    x=y
    for i in range(n):
        x=p[x]
        pt+=c[i]
        if x==y:
            r=i+1
            break
    rp[y]=r
    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,pp=roop(i)
    if k<=n:
        tmp=tr(i,k)
    else:
        tmp0=tr(i,k)    
        tmp1=(k//r)*pp+tr(i,k%r)
        tmp2=max(0,(k//r)-1)*pp+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:
from copy import copy
n, k = map(int, input().split())
p = list(map(int,input().split()))
c = list(map(int, input().split()))
di = {}
for i in range(n):
    di[i+1] = False
l = 1
cc = 0
per = [] # ループの順番
while cc < n:
    tmp = []
    while True:
        if di[l]:
            break
        else:
            tmp.append(l)
            di[l] = True
            cc += 1
            l = p[l-1]
    per.append(tmp)
    for i in range(n):
        if not di[i+1]:
            l = p[i]
#print(per)
dd = {} # 何個目のループに属するか
for i in range(n):
    dd[i+1] = 0
for i in range(len(per)):
    for j in per[i]:
        dd[j] = i
#print(dd)
su = [] # ループ１週の和
for i in range(len(per)):
    tmp = 0
    for j in per[i]:
        tmp += c[j-1]
    su.append(tmp)
#print(su)
s2 = [] # ループ１週何個か
for i in range(len(per)):
    s2.append(len(per[i]))
#print(s2)
ans = -1*(10**10)
d2 = {} # per[dd]の中でなんばんめにあるか(0インデックス)
for i in range(len(per)):
    for j in range(len(per[i])):
        d2[per[i][j]] = j
#print(d2)
for i in range(n):
    loop = dd[i+1]
    w = i+1
    kk = copy(k)
    if k < s2[loop]:
        tmp = 0
        m = -10**9
        for j in range(k):
            w = p[w-1]
            tmp += c[w-1]
            m = max(m, tmp)
        ans = max(ans, m)
    else:
        if su[loop] <= 0:
            tmp = 0
            m = -10**9
            for j in range(k):
                w = p[w-1]
                tmp += c[w-1]
                m = max(m, tmp)
            ans = max(ans, m)
        else:
            m_loop = kk // (s2[loop])
            m_loop -= 1
            kk -= m_loop * s2[loop]
            tmp = su[loop]*m_loop
            m = -10**9
            for j in range(kk):
                w = p[w-1]
                tmp += c[w-1]
                m = max(m, tmp)
            ans = max(ans, m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

P2 = copy.deepcopy(P)

ans = 0
while P2:
    count = K
    ans_tmp = 0
    s = P2.pop()
    while count:
        ans_tmp += C[s-1]
        count -= 1
        s = P[s-1]
        ans = max(ans, ans_tmp)

if ans == 0:
    print(max(C))
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
pn = list(map(int, input().split()))
cn = list(map(int, input().split()))

ans = -float('inf')

for i in range(n):
    now = i
    total = 0
    for j in range(1, k+1):
        now = pn[now]-1
        total += cn[now]
        ans = max(ans, total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,k=map(int,input().split(" "))
P=list(map(int,input().split(" ")))
C=list(map(int,input().split(" ")))
count=[]
def f (i):
    q=deepcopy(i)
    count1=[]
    count2=0
    for j in range(k):
        count2+=C[i]
        count1.append(count2)
        if i==q and count2<0:
            break
        i=P[i]-1
    return max(count1)
for i in range(n):
    count.append(f(i))
print(max(count))

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]



def solve(k,C,P):
    ans = float('-inf')
    for i in range(len(P)):
        curr = P[i]
        score = 0
        for _ in range(k):
            # print(f'{i=} | {P[i]=} | {ans=} | {curr=} | {score=}')
            score += C[curr]
            ans = max(ans, score)
            curr = P[curr]
    return ans

n,k = ip()
P = [int(i) - 1 for i in stdin.readline().split()]
C = ip()
print(solve(k,C,P))

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

maxn=-10**15
for i in range(n):
    #si=0
    ck=k
    ans=0
    koma=i
    while ck>=1:
        koma=p[koma]-1
        ans+=c[koma]
        maxn=max(maxn,ans)
        ck-=1
print(maxn)

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):
    ans.append(C[P[i]-1])

for i in range(N):
    p = ans[i]
    n = P[i]
    for j in range(K-1):
        n = P[n-1]
        p += C[n-1]
        ans[i] = max(ans[i], p)
print(max(ans))

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(n):
    score = 0
    prev = i
    for j in range(k):
        score += c[p[prev]-1]
        prev = p[prev]-1
        ans = max(ans, score)
if k <= n:
    print(ans)
    exit()
else:
    s = deepcopy(c)
    shuuki = [1]*n
    for i in range(n):
        score = 0
        prev = i
        for j in range(n):
            if p[prev]-1 == i:
                break
            s[i] += c[p[prev]-1]
            prev = p[prev]-1
            shuuki[i] += 1
    for i in range(n):
        score = 0
        prev = i
        num = k//shuuki[i]
        amari = k-num*shuuki[i]
        for j in range(amari):
            score += c[p[prev]-1]
            prev = p[prev]-1
        ans = max(ans, s[i]*num+score)
print(ans)

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 = [x - 1 for x in P]

max_score = -10**10
for i in range(N):
    visited = [False] * N
    score = 0
    max_score_i = -10**10
    n = 0
    x = i

    while (True):
        n += 1
        x = P[x]

        score += C[x]

        if (max_score_i < score):
            max_score_i = score
        if (n == K):
            break

    if (max_score < max_score_i):
        max_score = max_score_i

print(max_score)