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:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
from decimal import *

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    start = time.time()

    n, k = get_int_multi()
    p = get_int_list()
    c = get_int_list()

    kaisuu = [-1] * n
    score = [0] * n

    for i in range(n):
        wk = 0
        ichi = i
        for ii in range(n):
            ichi = p[ichi] -1
            wk += c[ichi]
            if i == ichi:
                kaisuu[i] = ii+1
                score[i] = wk
                break


    wk = 0
    ans = - 10 ** 20
    for i in range(n):
        ichi = p[i] -1
        wk = c[ichi]
        wk2 = c[ichi]
        idx = 0
        while idx < k-1:
            ichi = p[ichi] -1
            wk += c[ichi]

            wk2 = max(wk2, wk)
            idx += 1

            #ループするならメモを使って減らす
            if (k - 1 - idx > kaisuu[ichi] * 2) and kaisuu[ichi] > 0:
                roopsuu = ((k - 1 - idx) // kaisuu[ichi]) -1
                wk += roopsuu * score[ichi]
                idx += roopsuu * kaisuu[ichi]
                wk2 = max(wk2, wk)

        ans = max(ans , wk2)
    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()))
c = list(map(int, input().split()))
l = []
ans = []
for i in range(n):
    l.append(c[p[i]-1])
    x = p[i]-1
    while 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:
import sys, math, bisect

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

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

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

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

    return distances


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

    edges3 = []
    costs = []
    for i in range(N):
        edges3.append([ CList[i]*(-1), i+1, PList[i] ])
        costs.append(CList[i])
    costs.sort()
    for i in range(N):
        edges3.append([0, 0, i+1]) #[cost, start, end]
    for i in range(1, N+1):
        edges3.append([0, i, N+1])



    weights =calcweight_bellman_ford(N_vertices, 0, edges3, K, costs, inf)


    print( (-1) * weights[-1])

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
P = readInts()
C = readInts()
dic = defaultdict(int)
for i in range(n):
    dic[i+1] = P[i]
ans = -float('inf')
for start in range(n):
    nya = []
    root = defaultdict(int)
    pya = start+1
    cnt = 0
    SUM = 0
    while root[dic[pya]] == 0 and cnt < k:
        pya = dic[pya]
        #print('start',start,pya,C[pya-1])
        nya.append(C[pya-1])
        cnt += 1
        SUM += C[pya-1]
        ans = max(ans,SUM)
    if cnt < k:# まだ満たない
        need = k-cnt
        nl = len(nya)
        sumnya = sum(nya)
        a = need//nl
        SUM += sumnya * a
        nokori = need - nl*a
        SUM += sum(nya[:nokori])
        ans = max(ans,SUM)
    else:
        ans = max(ans,SUM)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#d
n, k=map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
r = []
for j in range(n):
    r.append([0])
    
    now = j
    for i in range(k):
        r[j].append(r[j][i] + c[now])
        now = p[now]-1
    
for i in range(len(r)):
    del r[i][0]

ans = -float('inf')
for i in range(len(r)):
    if ans < max(r[i]):
        ans = max(r[i])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
from sys import stdin, stdout  
n,k = map(int, stdin.readline().strip().split())
p = [int(x) for x in stdin.readline().split()] 
cost = [int(x) for x in stdin.readline().split()] 
for i in range(n):
	p[i] -= 1
ans = -10**18
for i in range(n):
	curr = 0
	cum = 0
	ind = p[i]
	temp = []
	while ind != i:
		temp.append(cost[ind])
		ind = p[ind]
	temp.append(cost[ind])
	m = len(temp)
	pref = [temp[0]]
	for j in range(1,m):
		pref.append(pref[j-1] + temp[j])
	curr = pref[0]
	for j in range(min(k,m)):
		curr = max(curr,pref[j])
	if k > m:
		for j in range(k % m):
			cum = max(cum, pref[j])
		curr = max(curr, cum + pref[m-1]*(k//m))
	ans = max(ans, curr)
print(ans)

Submission status: Time Limit Exceeded

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


def solve(start, K):
    cur = P[start]
    PC = [C[cur]]
    while cur != start:
        #print('visit {}'.format(cur))
        cur = P[cur]
        PC.append(PC[-1] + C[cur])
    M = len(PC)
    #print('M: {}'.format(M))
    #print(PC)

    S0 = 0
    if PC[-1] > 0:
        X = K // M
        if K % M == 0:
            X -= 1
        S0 = PC[-1] * X
        #print('X', X)
        K -= X * M
    else:
        K = min(K, M)

    if K > 0:
        S0 += max(PC[:K])        
    return S0

ans = None
for start in range(N):
    candidate = solve(start, K)
    #print(start, candidate)
    if ans is not None:
        ans = max(ans, candidate)
    else:
        ans = candidate
print(ans)

Submission status: Time Limit Exceeded

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

ans = - 10**10
for i in range(0,n):
  tmp = 0
  tmpm = -10**10
  pos = i
  for j in range(k):
    tmp += c[p[pos]-1]
    pos = p[pos]-1
    tmpm = max(tmpm, tmp)
  ans = max(tmpm, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    k = kwargs["k"]
    P = kwargs["P"]
    C = kwargs["C"]
    res = -INF
    tmp = [0 for i in range(n)]
    for i in range(min(k, 10 ** 6)):
        n_tmp = [tmp[P[j]-1] + C[j] for j in range(n)]
        tmp = n_tmp
        res = max(res, max(tmp))

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"], kwargs["k"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["P"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["C"] = [int(i) for i in cin]

    cout = main(kwargs)
    print(cout)

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()))
highscore = -float("inf")
for i in range(n):
    score = 0
    masu = i
    for j in range(k):
        masu = p[masu]-1
        score += c[masu]
        highscore = max(score,highscore)
print(highscore)

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 n in range(0,N):
  P[n] = P[n] - 1
  
M = -10**9
for i in range(0,N):  
  for j in range(1,K+1):
    s = 0
    index = i
    for k in range(0,j):
      index = P[index]
      s = s + C[index]
    if M < s:
      M = s
print(M)

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
n,k = map(int, input().split())
p = list(map(int, input().split()))
cost = list(map(int, input().split()))
for i in range(n):
	p[i] -= 1
ans = -10**18
for i in range(n):
	curr = 0
	cum = 0
	ind = p[i]
	temp = []
	while ind != i:
		temp.append(cost[ind])
		ind = p[ind]
	temp.append(cost[ind])
	m = len(temp)
	pref = [temp[0]]
	for j in range(1,m):
		pref.append(pref[j-1] + temp[j])
	curr = pref[0]
	for j in range(min(k,m)):
		curr = max(curr,pref[j])
	if k > m:
		for j in range(k % m):
			cum = max(cum, pref[j])
		curr = max(curr, cum + pref[m-1]*(k//m))
	ans = max(ans, curr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pd = {i: x for i, x in enumerate(p, 1)}
    cd = {i: x for i, x in enumerate(c, 1)}
    ans = -10 ** 10
    for i in range(1, n + 1):
        res = 0
        x = i
        for j in range(1, k + 1):
            res += cd[x]
            x = pd[x]
            ans = max(res, ans)
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
ps = [p-1 for p in ps]
visited = [False] * n
from collections import defaultdict
from collections import deque
ds = []
sums = []
for i in range(n):
    if visited[i]: continue
    q = deque([])
    q.append(i)
    s = cs[i]
    d = [i]
    while len(q) > 0:
        u = q.popleft()
        visited[u] = True
        nx = ps[u]
        if visited[nx]: continue
        d.append(nx)
        q.append(nx)
        s += cs[nx]
    sums.append(s)
    ds.append(d)

# print(ds,sums)
def calcmax(d,s,k,cs):
    cnt = 0
    l = len(d)
    div, rest_ = divmod(k-1, l)
    rest_ += 1
    if s > 0:
        cnt += div*s
    d2 = d*2
    mx = - 1<<50

    for rest in range(1,rest_+1):
        for i in range(rest,l*2):
            # print(i,d2[i-rest:i])
            c_ = [cs[j] for j in (d2[i-rest:i])]
            c = sum(c_)
            mx = max(mx, c)
    # print(d,cnt,mx)
    return cnt + mx

ans = -1 << 50
for d,s in zip(ds,sums):
    # print("aaa",d,s)
    c = calcmax(d,s,k,cs)
    ans = max(ans,c)
print(ans)

Submission status: Time Limit Exceeded

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

score_list = []
for first_pos in range(N):
  now_pos = first_pos
  score = 0
  
  for move_idx in range(K):
    now_pos = Ps[now_pos] - 1
    score += Cs[now_pos]
    score_list.append(score)
  
print(max(score_list))

Submission status: Time Limit Exceeded

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

ans = -float('inf')

for i in range(1, N+1):
    score = [0]
    alr = set()
    now = i
    while not now in alr:
        alr.add(now)
        now = P[now-1]
        score.append(score[-1] + C[now-1])
    if len(score)-1 >= K:
        for j in range(K):
            ans = max(ans, score[j+1])
    else:
        base = 0
        if score[-1] > 0:
            base = score[-1]*(K//(len(score)-1))
            L = K % (len(score)-1)
            for j in range(len(score)-1):
                ans = max(ans, (base-score[-1])+score[j+1])
            for j in range(L):
                ans = max(ans, base+score[j+1])
        else:
            for j in range(len(score)-1):
                ans = max(ans, base+score[j+1])

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()))
ans = -float("inf")
for i in range(n):
    now = i
    cnt = [0]
    for j in range(n):
        nxt = p[now]
        cnt.append(cnt[j]+c[nxt])
        now = nxt
        if now == i:
            break
    m = len(cnt)-1
    if k <= m:
        s = max(cnt[1:(k+1)])
    elif cnt[-1] < 0:
        s = max(cnt[1:])
    else:
        t = k//m
        s = (t-1)*cnt[-1]+max(cnt[1:])
        s = max(s, t*cnt[-1]+max(cnt[:(k-t*m+1)]))
    ans = max(ans,s)
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()))

score = 0
res = [-9999999999] * N

for i in range(N):
  score = 0
  start = i
  if res[i] > -9999999999:
    continue
  next = P[start] - 1
  for _ in range(K):
    score += C[next]
    next = P[next] - 1
    res[i] = max(res[i], score)
  
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
INF = 1 << 60

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

ans = -INF
for i in range(n):
    cnt = -INF
    total = 0
    cur = i
    for j in range(k):
        cur = p[cur] - 1
        total += c[cur]
        cnt = max(cnt, total)
    ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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

max_score = -10**9
for i in range(N):
    memo = [P[i]]
    score = C[P[i]]
    move = 1
    max_score = max(score, max_score)

    while move < K and P[memo[-1]] not in memo:
        memo.append(P[memo[-1]])
        score += C[memo[-1]]
        move += 1
        max_score = max(score, max_score)

    if move < K and score > 0:
        score = (K // move) * score
        move *= (K // move)
        max_score = max(score, max_score)

        cur = i
        while move < K:
            cur = P[cur]
            score += C[cur]
            move += 1
            max_score = max(score, max_score)

print(max_score)

Submission status: Time Limit Exceeded

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

for i in range(n):
    p[i] -= 1
def score(a, k):
    now = p[a]
    s = c[now]
    cnt = 1
    l = [s]
    while now != a and cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    if cnt == k:
        return max(l)
    if 2 * cnt >= k:
        s = (k // cnt - 1) * s
        k %= cnt
        k += cnt
    else:
        k -= cnt
    cnt = 0
    while cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    return max(l)
print(max(score(i, k) for i in range(n)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class doubling(object):
	def __init__(self, N, P, C, bitlen):
		self.bitlen = bitlen
		self.nex = [[None] * N for i in range(bitlen)]
		for i in range(N):
			self.nex[0][i] = P[i]
		self.score = [[None] * N for i in range(bitlen)]
		for i in range(N):
			self.score[0][i] = C[i]

		#ダブリングテーブル構築
		for i in range(1, self.bitlen):
			for j in range(N):
				self.nex[i][j] = self.nex[i - 1][self.nex[i - 1][j]]

		for i in range(1, self.bitlen):
			for j in range(N):
				self.score[i][j] = self.score[i - 1][self.nex[i - 1][j]] + self.score[i - 1][j]


	#startからK回移動後の点を求める
	def query1(self, start, K):
		self.loc = start
		self.ans = 0
		for i in range(self.bitlen):
			if K % 2 == 1:
				self.ans += self.score[i][self.loc]
				self.loc = self.nex[i][self.loc]
			K = int(K // 2)

		return self.ans

#処理内容
def main():
	N, K = getlist()
	P = getlist()
	for i in range(N):
		P[i] -= 1
	C = getlist()
	DDD = doubling(N, P, C, 40)

	ans = -INF
	# for i in range(N):
	# 	val = 0
	# 	itr = i
	# 	for j in range(N):
	# 		val += C[itr]
	# 		ans = max(ans, val)
	# 		itr = P[itr]

	for i in range(N):
		for j in range(min(N, K)):
			ans = max(ans, DDD.query1(i, K - j))

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

from collections import defaultdict

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    score = []
    c_sum = [0]
    while cnt < k:
        score.append(c[now])
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
    if k == cnt:
        ans = max(ans, sum(score), max(c_sum[1:]))
    else:
        temp = sum(score)
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += sum(score[:q])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, K, P, C):
    ans = -10**18
    for start in range(N):
        t = 1
        s = 0
        idx = start
        while P[idx] != start:
            idx = P[idx]
            s += C[idx]
            t += 1
        s += C[start]
        q, m = divmod(K, t)
        #print(R)
        score = 0
        #print(ans, s)
        if s >= 0:
            x = max(0, (q-2)*t)
            score += s * (x//t)
            #print(f"score={score}")
            idx = start
            for _ in range(x, K):
                idx = P[idx]
                score += C[idx]
                ans = max(ans, score)
        else:
            idx = start
            for _ in range(1, K+1):
                idx = P[idx]
                score += C[idx]
                ans = max(ans, score)
    print(ans)

numba_compile([
    [solve, "void(i8,i8,i8[:],i8[:])"],
])


def main():
    N, K = map(int, input().split())
    P = np.array(input().split(), dtype=np.int64)-1
    C = np.array(input().split(), dtype=np.int64)
    solve(N, K, P, C)

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

# score[i][j] = i-th score, position when start from j
score = [[(0, j) for j in range(N)] for i in range(N+1)]
T = [-1 for i in range(N)]
for i in range(1, N+1):
	for j in range(N):
		(s,p) = score[i-1][j]
		next_p = P[p]
		score[i][j] = (s + C[next_p], next_p)
		if j == next_p and T[j] < 0:
			T[j] = i

if K <= N:
	print(max([max([s[i][0] for i in range(N)]) for s in score[1:K+1]]))
	exit()

ans = -(10 ** 9)
for i in range(N):
	t = T[i]
	if score[t][i][0] > 0:
		base = score[t][i][0] * (K // t)
		ad = max([s[i][0] for s in score[:(K % t) + 1]])
		ans = max(ans, base + ad)
	else:
		ans = max(ans, max([s[i][0] for s in score[1:]]))
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()))

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

print(ans)

Submission status: Time Limit Exceeded

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

V = [0] * N
score = -float("inf")
for _ in range(K):
  V_pre = V
  V = [C[i] + V_pre[P[i]-1] for i in range(N)]
  score = max(score, *V)
print(score)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    ans = -float('inf')
    for n in range(N):
        m = n
        ans_tmp = 0
        for k in range(K):
            nxt = P[m]
            score = C[nxt-1]
            ans_tmp += score
            ans = max(ans, ans_tmp)
            m = nxt-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()))
c = list(map(int, input().split()))
ans = -1 * (10 ** 10)
for i in range(n):
    cnt = 0
    ind = i
    for j in range(k):
        ind = p[ind]-1
        #print(ind)
        cnt += c[ind]
        ans = max(ans, cnt)
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
  score_max = max(score_list)
  if score_list[-1]>0 and step<K:
    loop = K//step
    amari = K%step
    for j in range(step):
      if j<amari:
        score_max = max(score_max, score_list[-1]*loop+score_list[j])
      else:
        score_max = max(score_max, score_list[-1]*(loop-1)+score_list[j])
  answer = max(answer,score_max)

print(answer)

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(1,n+1):
    score=0
    moves=0
    poi=i
    while moves<k:
       poi=p[poi-1]
       score+=c[poi-1]
       l.append(score)
       moves+=1
print(max(l))

Submission status: Time Limit Exceeded

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

ans = -float('inf')
for i in range(N):
    score = -float('inf')
    cnt = 0
    k = 0
    while k < K:
        ni = P[i] - 1
        cnt += C[ni]
        score = max(cnt, score)
        i = ni
        k += 1
    ans = max(ans, score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = min(c)

ans = minc
for i in range(n):
    score = minc
    cur_score = 0
    pos = i
    for j in range(1, k + 1):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    ans = max(ans, 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()))

d = dict()
c = dict()

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


for i in range(N):
    ans = 0
    mans = -(10**9)
    p = i+1
    
    for _ in range(K):
        p = d[p]
        ans += c[p]
        if ans > mans:
            mans = ans
    ma[i] = mans
    
print(max(ma))

Submission status: Time Limit Exceeded

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

ans = -float('inf')
for i in range(N):
    s = 0
    for k in range(K):
        i = P[i]-1
        s += C[i]
        ans = max(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[]
  for _ in range(k):
    i=p[i]
    x.append(c[i])
  anss=-10**20
  s=x[0]
  anss=max(anss,s)
  for i in x[1:]:
    s+=i
    anss=max(anss,s)
  ans=max(ans,anss)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
def main():
    n, k = map(int, input().split())
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    if k == 1:
        print(max(c))
        sys.exit()
    seen = [0] * n
    cycles = []
    for i1 in range(n):
        if not seen[i1]:
            cycle_t = []
            koko = i1
            while True:
                if seen[koko]:
                    cycles.append(cycle_t)
                    break
                cycle_t.append(c[koko])
                seen[koko] = 1
                koko = p[koko] - 1

    score = max(c)
    for cycle in cycles:
        score_t = max(cycle)
        cycle_len = len(cycle)
        cycle_sum = sum(cycle)
        kaisu, rem = divmod(k, cycle_len)
        if rem == 0:
            kaisu -= 1
            rem = cycle_len
        if kaisu > 0:
            kaisu -= 1
            rem += cycle_len
        cycle = tuple(accumulate(cycle + cycle + cycle))
        for i1 in range(2, rem + 1):
            for i2 in range(cycle_len):
                score_t = max(score_t, cycle[i1+i2] - cycle[i2])
        if cycle_sum > 0:
            score_t += (kaisu * cycle_sum)
        score = max(score, score_t)
    print(score)

if __name__ == '__main__':
    main()

Submission status: Accepted

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]
mi=set(range(n))
g={}
# g[id]=[ary]
while mi:
  x0=mi.pop()
  ary=[c[x0]]
  x=x0
  while p[x]!=x0:
    x=p[x]
    mi.discard(x)
    ary.append(c[x])
  cnt=len(ary)
  tmp=0
  ary*=2
  cary=[tmp]
  for x in ary:
    tmp+=x
    cary.append(tmp)
  g[x0]=[cnt,cary]
ans=-float('inf')
for cnt,cary in g.values():
  x,y=divmod(k,cnt)
  tmp1=max(0,cary[cnt]*x)
  tmp2=-float('inf')
  for i in range(cnt):
    for j in range(y):
      tmp2=max(tmp2,cary[i+j+1]-cary[i])
  ans=max(ans,tmp1+tmp2)
  if x:
    tmp1=max(0,cary[cnt]*(x-1))
    tmp2=-float('inf')
    for i in range(cnt):
      for j in range(cnt):
        tmp2=max(tmp2,cary[i+j+1]-cary[i])
    ans=max(ans,tmp1+tmp2)
  

print(ans)