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:
# -*- 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 and point > 0: #1週してポイントが1以上なら
      #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 = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
cs = [int(i) for i in input().split()]

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
datp = list(map(lambda x: int(x) - 1, input().split()))
datc = list(map(int, input().split()))

# movetalbeは next, scoreの遷移
movetable = []
for i in range(35):
    movetable.append([None] * n)

for i in range(n):
    ne = datp[i]
    score = datc[ne]
    movetable[0][i] = [ne, score]

for loop in range(1, 35):
    for i in range(n):
        next1, score1 = movetable[loop - 1][i]
        next2, score2 = movetable[loop - 1][next1]
        movetable[loop][i] = [next2, score1 + score2]

# print(movetable)
kres = []
finalres = -99999999999999

for kk in range(1, min(n + 1, k)):
    #print("k", kk)
    for i in range(n):
        # i start
        cur = i
        score = 0
        for i in range(35):
            if ((kk >> i) & 1) == 1:
                cur, addscore = movetable[i][cur]
                score += addscore
        finalres = max(finalres, score)

kk = k
#print("k", kk)
for i in range(n):
    # i start
    cur = i
    score = 0
    for i in range(35):
        if ((kk >> i) & 1) == 1:
            cur, addscore = movetable[i][cur]
            score += addscore
    finalres = max(finalres, score)

print(finalres)

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 for _ in range(n)]
loopn = [0 for _ in range(n)]
for start in range(n):
    nex = -1
    j = 0
    nax = -float("inf")
    while nex != start:
        if nex == -1:
            nex = P[start]-1
        else:
            nex = P[nex]-1
        score[start] += C[nex]
        nax = max(nax, score[start])
        j += 1
    loopn[start] = j
    if score[start] < 0:
        score[start] = nax
    else:
        score[start] = (k//j)*score[start]
        nokori = k-(k//j)*j
        i = 0
        nnnnn = (k//j)
        nscore = 0
        nax = -float("inf")
        while i < nokori:
            nex = P[nex]-1
            nscore += C[nex]
            nax = max(nax, nscore)
            i += 1
        if nnnnn == 0 and nax < 0:
            score[start] += nax
        elif nax > 0:
            score[start] += nax
print(max(score))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, k = map(int, input().split())
    C = list(map(int, input().split()))
    P = list(map(int, input().split()))
    C = list(map(lambda x: x - 1, C))
    score = -10**16
    for i in range(n):
        back = []
        x = i
        s = 0
        for j in range(k):
            back.append(s)
            s += P[C[x]]
            if score < s:
                score = s
            x = C[x]
            if s in back:
                break

    print(score)

resolve()

Submission status: Time Limit Exceeded

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


inf = float("inf")


ans = max(C)  # at least one move
for pos in range(N):
    i = pos
    score = 0
    cycleLen = None
    cycleGain = None
    bestInc = 0
    for k in range(K):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        bestInc = max(bestInc, score)

        if cycleLen is not None and k == K % cycleLen:
            numCycles = (K - k) // cycleLen

            ans = max(ans, cycleGain * numCycles + bestInc)
            break

        if i == pos:
            cycleLen = k
            cycleGain = score

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


class Node:
    def __init__(self, idx, next, score):
        self.idx = idx
        self.next = next
        self.score = score


def solve():
    N, K = map(int, input().split())
    Ps = map(int, input().split())
    Cs = list(map(int, input().split()))

    nodes = []

    for i in range(N):
        p = next(Ps) - 1
        nodes.append(Node(i, p, Cs[p]))

    all_max = -10**10
    for i, node in enumerate(nodes):
        current_node = node
        next_node = nodes[current_node.next]
        count = 1
        score = next_node.score
        score_list = [score]
        max_score = score
        visited = {next_node.idx}
        while count <= K:
            next_node = nodes[next_node.next]
            if next_node.idx in visited:
                break
            score += next_node.score
            max_score = max(max_score, score)
            score_list.append(score)
            visited.add(next_node.idx)
            count += 1
        if count == K:
            all_max = max(all_max, max_score)
            continue
        else:
            if score <= 0:
                all_max = max(all_max, max_score)
                continue
            cycle, remains = divmod(K, count)
            if remains == 0:
                max_score = score * cycle
            else:
                max_score = score * cycle + max(score_list[:remains])
            all_max = max(all_max, max_score)

    return all_max


def main():
    print(solve())


if __name__ == "__main__":
    main()

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 ** 4)):
        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()))
ans=-float('inf')
for i in range(n):
    start=i
    score=0
    for l in range(k):
        start=p[start]-1
        score+=c[start]
        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()))
p = [i-1 for i in p]
c = list(map(int, input().split()))
max_s = -1000000000000000000000
for i in range(n):
  now = i
  score = [0]
  count = 0
  max_s_now=-100000000000000000
  while(1):
    now = p[now]
    score += [score[-1] + c[now]]
    count += 1
    max_s_now = max(max_s_now, score[-1])
    if(count >= k):
      break
    if(now == i):
      if(score[-1] <= 0):
        break
      else:
        t = k//count
        ama = k%count
        max_s_now1 = t*score[-1] + max(score[:ama+1])
        max_s_now2 = (t-1)*score[-1] + max_s_now
        max_s_now = max(max_s_now1, max_s_now2)
        break
  max_s = max(max_s, max_s_now)
print(max_s)

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(" ")))
count=[]
def f (i):
    count1=[]
    count2=0
    for j in range(k):
        count2+=C[i]
        count1.append(count2)
        i=P[i]-1
    return count1
for i in range(n):
    count+=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()))
for k in range(N):
  P[k] -= 1
scorelist = []
roop = []
now = 0
visited = [-1 for _ in range(N)]
for k in range(N):
  now = k
  if visited[now] == -1:
    roop.append([])
    scorelist.append([])
    start = 0 + now
    while visited[start] == -1:
      roop[-1].append(start)
      visited[start] = 1 
      start = P[start]
      scorelist[-1].append(C[start])
    scorelist[-1] = scorelist[-1] + scorelist[-1]
    
#print(roop)
#print(scorelist)

ans = - float('inf')
for l in range(len(roop)):
  #print(scorelist[l][:len(roop[l])])
  Q = K // len(roop[l])
  R = K % len(roop[l])
  if Q > 0 and R == 0:
    Q -= 1
    R = len(roop[l]) 
  #print(Q, R)
  if sum(scorelist[l][:len(roop[l])]) > 0:
    basis = sum(scorelist[l][:len(roop[l])])*Q
  else:
    basis = 0
  #print(basis)
  adv = - float('inf')
  for k in range(len(roop[l])):
    for j in range(k, k + R):
      adv = max(adv, sum(scorelist[l][k:j+1]))
  ans = max(ans, basis + adv)

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


scores=[C[P[j]-1] for j in range(N)]
ans=max(scores)
# print(scores)
for i in range(1,K):
    scores=[C[P[j]-1]+scores[P[j]-1] for j in range(N)]
    ans=max(ans,max(scores))
    # print(scores)
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()))
    
flags = [0]*n
roots = []
for i in range(n):
  if flags[i] == 1:
    continue
  root = [i+1]
  while True:
    root.append(p[root[-1]-1])
    flags[root[-1]-1] = 1 
    if root[-1] == i+1:
      root.pop(-1)
      break
  roots.append(root)

ans = max(c)
for root in roots:
  root.extend(root)
  ruisekiwa = [0]*len(root)
  ruisekiwa[0] = c[root[0]-1]
  for i in range(1, len(root)):
    ruisekiwa[i] = ruisekiwa[i-1] + c[root[i]-1]
  scoreCir = ruisekiwa[len(root)//2-1]
  #print(root)
  scoreForRoot = -10**15
  for i in range(1, min(k+1, len(root)//2+1)): #移動回数
    scoreForKaisuu = -10**15
    for j in range(0, len(root)//2):
      score = ruisekiwa[j+i] - ruisekiwa[j]
      scoreForKaisuu = max(score, scoreForKaisuu)
    #print(scoreForKaisuu)
    if scoreCir > 0 and k-i >= len(root)//2:
      #print((k-i)//(len(root)//2))
      scoreForKaisuu += (k-i)//(len(root)//2)*scoreCir
    scoreForRoot = max(scoreForKaisuu, scoreForRoot)
  ans = max(ans, scoreForRoot)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

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

que = {(P[a]-1, C[P[a]-1]) for a in range(N)}

res = -10**9-1

for i in range(K-1):
    nset = set()
    que = list(que)
    for j in range(len(que)):
        node, point = que[j]
        res = max(res, point)
        nset.add((P[node]-1, point+C[P[node]-1]))
    que = nset
que = list(que)
for j in range(len(que)):
    node, point = que[j]
    res = max(res, point)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())

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

dp = [[0 for i in range(N)] for j in range(K+1)]

for i in range(N):
    x = i
    for j in range(K):
        if dp[j][P[x]-1] == dp[j][x] + C[P[x]-1]:
            break 
        dp[j+1][P[x]-1] = max(dp[j][x] + C[P[x]-1], dp[j][P[x]-1])
        x = P[x]-1

if np.max(dp) != 0:
    print(np.max(dp[1:]))
else:
    print(max(C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

info = np.array([[P[i], C[i]] for i in range(N)])

ans = []
for n in range(N):
    k = 0
    score = 0
    next_ = info[n,0]
    while k < K:
        score += info[next_-1, 1]
        ans.append(score)
        next_ = info[next_-1, 0]
        k += 1
        if next_ == n-1:
            score *= K//k
            k *= K//k

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

P = [x-1 for x in P]

result = min(C)
for i in range(N):
    score = 0
    cell = i
    for k in range(K):
        cell = P[cell]
        score += C[cell]
        if score > result:
            result = score

print(result)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from functools import lru_cache
from math import log

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

maxs = min(C)
for p in range(1,N+1):
    q = P[p]
    s = C[q]
    x = s
    for i in range(K-1):
        q = P[q]
        s += C[q]
        x = max(s, x)
    if maxs < x:
        maxs = x
print(maxs)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

if __name__ == '__main__':
    N, K = list(map(lambda x: int(x), sys.stdin.readline().rstrip().split()))
    P = list(map(lambda x: int(x), sys.stdin.readline().rstrip().split()))
    C = list(map(lambda x: int(x), sys.stdin.readline().rstrip().split()))

    max_score = -float('inf')

    for i in range(1, N+1):
        pos = i
        score = 0
        for j in range(K):
            # 移動する
            # X 移動してきた場所が初期位置iなら終了
            # スコア計算、小さいなら代入
            pos = P[pos-1]
            score += C[pos-1]
            if score > max_score:
                max_score = score
    print(max_score)

Submission status: Time Limit Exceeded

Solution code:
#--d--#
import sys,math,collections,itertools
input = sys.stdin.readline

def solve(i):#-スタートする番号-#
    visit = set([i])
    tmp = [] #訪れた場所から飛ぶ時の得点
    #tmp_sum = [] #得点の累積和
    while True:
        tmp.append(C[i-1])
        next_point = P[i-1]
        if next_point not in visit:
            visit |=set([next_point])
            i = next_point
        else:
            break
    roopLength = len(tmp)
    roop_sum = sum(tmp)
    cum_sum = list(itertools.accumulate(tmp))
    #print(roopLength,tmp,list(cum_sum))
    #print(visit)
    #-もしループで負になるなら、roopLength or Kの小さいほうの中でcum_sumの大きいもの
    if roop_sum <=0:
        ans = -float('inf')
        for i in range(min(K,roopLength)):
            ans = max(ans,cum_sum[i])
    #ループ長さｘ２がKよりおおきいなら、Kまで足し上げる
    elif roopLength * 2 >=K:
        point = 0
        ans = -float('inf')
        for i in range(K):
            point +=  tmp[i%roopLength]
            ans = max(ans,point)
    #ループ長さｘ２がKみ満たないなら、２週分残したとこまでループさせて、足し上げる
    elif roopLength *2 < K:
        point = roop_sum*(K//roopLength-1)
        ans = -float('inf')
        for i in range(roopLength+K%roopLength):
            point += tmp[i%roopLength]
            ans = max(ans,point)
    return ans


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    point = solve(i+1)
    ans = max(point,ans)
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 = list(map(lambda x: x - 1, p))
score_max = -1 * pow(10, 15)
for start in range(n):
    score_pos_max = -1 * pow(10, 15)
    score = 0
    pos = start
    for i in range(k):
        if pos < 0 or n <= pos:
            break
        pos = p[pos]
        score += c[pos]
        score_pos_max = max(score_pos_max, score)
    score_max = max(score_max, score_pos_max)
print(score_max)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=[]
iToCpi=dict()
startToScore=dict()
for i in range(N):
    iToCpi[i]=C[P[i]-1]
    startToScore[i]=0
select=list(range(N))
for i in range(K):
    for j in range(N):
        startToScore[j]+=iToCpi[select[j]]
        select[j]=P[select[j]]-1
    ans+=[max(startToScore.values())]
print(max(ans))

Submission status: Time Limit Exceeded

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

    P_id = [p - 1 for p in P]

    scores = []
    max_ = -float('inf')

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

        # 解析

        current = start
        visited = [False] * N
        visited[current] = True

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

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

        # print('history', history)
        # print('before', before_loop_ids)
        # print('loop', loop_ids)

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

        score = 0
        current = start
        num_move = K

        # before loop

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

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

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

    print(max_)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
arr = []
for i in range(n):
  i_s = []
  s = 0
  m = p[i]
  for j in range(k):
    s += c[m - 1]
    i_s.append(s)
    m = p[m - 1]
  arr.append(max(i_s))
ans = max(arr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

info = np.array([[P[i], C[i]] for i in range(N)])

ans = []
for n in range(N):
    k = 0
    score = 0
    next_ = info[n,0]
    while k < K:
        score += info[next_-1, 1]
        ans.append(score)
        next_ = info[next_-1, 0]
        k += 1
        if next_ == n:
            score *= K//k
            k *= K//k

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
pl = list(map(int, input().split()))
cl = list(map(int, input().split()))
sc = 0
max = 0

for i in range(0,n):
  pos = i
  sc = 0
  for j in range(0,k):
    pos = pl[pos] - 1
    sc += cl[pos]
    if max < sc or max == 0:
      max = sc

print(max)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    a.append(tl)
for l in a:
    le=len(l)
    d,m=divmod(K,le)
    tc=d*sum(l)
    s.add(tc)
    for i in range(m):
        tc+=l[i]
        s.add(tc)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
#Problem D
N, K= list(map(int,input().split()))
P = list(map(int,input().split()))
C = list(map(int,input().split()))
pos = 0

sub = []
anss = []

if all([i < 0 for i in C]):
    b = sorted(C)
    print(b[-1])
    exit()

for i in range(N):
    ans = 0
    pos = i+1
    for j in range(K):
        ans += C[pos-1]
        sub.append(ans)
        pos = P[pos-1]
    anss.append(max(sub))

        
print(max(anss))

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

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

que = deque([(P[a]-1, C[P[a]-1]) for a in range(N)])

res = -10**9-1

for i in range(K-1):
    for j in range(len(que)):
        node, point = que.popleft()
        res = max(res, point)
        que.append((P[node]-1, point+C[P[node]-1]))
for j in range(len(que)):
    node, point = que.popleft()
    res = max(res, point)
print(res)

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

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 ** 5)):
        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:
int1 = lambda x: int(x) - 1

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

visited = set()
cycles = []
for i in range(N):
    if i not in visited:
        cur = P[i]
        cycle = [i]
        while cur != i:
            visited.add(cur)
            cycle.append(cur)
            cur = P[cur]
        cycles.append(cycle)

ans = -float('inf')
for cycle in cycles:
    score = [0]
    for x in cycle * 2:
        score.append(score[-1] + C[x])

    # i回進めるときのスコア最大値
    lst = [0] * (min(K, len(cycle)) + 1)
    lst[0] = -float('inf')
    for i in range(1, min(K, len(cycle)) + 1):
        tmp = -float('inf')
        for j in range(len(cycle)):
            tmp = max(tmp, score[j + i] - score[j])
        lst[i] = tmp

    lap = K // len(cycle)
    if lap == 0:
        ans = max(ans,
                  max(lst))
    else:
        around_score = lst[len(cycle)]
        ans = max(ans,
                  max(lst),
                  around_score * (lap - 1) + max(lst),
                  around_score * lap + max(lst[:K % len(cycle) + 1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, K = [int(i) for i in stdin.readline().split()]
P = [int(i) for i in stdin.readline().split()]
C = [int(i) for i in stdin.readline().split()]

max_point = 0
score_list = []
for n in range(N):
    point = 0
    position = n + 1
    for k in range(K):
        point += C[position - 1]
        position = P[position - 1]
        score_list.append(point)
print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
datp = list(map(lambda x: int(x) - 1, input().split()))
datc = list(map(int, input().split()))

# movetalbeは next, scoreの遷移
movetable = []
for i in range(35):
    movetable.append([None] * n)

for i in range(n):
    ne = datp[i]
    score = datc[ne]
    movetable[0][i] = [ne, score]


for loop in range(1, 35):
    for i in range(n):
        next1, score1 = movetable[loop-1][i]
        next2, score2 = movetable[loop-1][next1]
        movetable[loop][i] = [next2, score1 + score2]



#print(movetable)
kres = []
finalres = -99999999999999

for kk in range(1,k+1):
    for i in range(n):
        # i start
        cur = i
        score = 0
        for i in range(35):
            if ((kk >> i) & 1) == 1:
                cur, addscore = movetable[i][cur]
                score += addscore
        finalres = max(finalres, score)
print(finalres)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = [int(pn) for pn in input().split()]
c = [int(cn) for cn in input().split()]
ans = -(10**9)
for i in range(n):
  genzai = p[i] - 1
  score = c[genzai]
  better_score = score
  for _ in range(k-1):
    genzai = p[genzai] - 1
    score += c[genzai]
    if score > better_score:
      better_score = score
  if better_score > ans:
    ans = better_score
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
score = [0 for i in range(n)]
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -float('inf')
for i in range(n):
    start = i
    cur = i
    i_s_score = 0
    i_s_score_max = C[P[cur]-1]
    move_num = 0
    for j in range(n):
        cur = P[cur]-1
        i_s_score += C[cur]
        i_s_score_max = max(i_s_score, i_s_score_max)
        move_num += 1
        if cur == start:
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        temp = i_s_score*(k//move_num)
        rest = k%move_num
        ans = max(ans, temp)
        i_s_score = temp
        for j in range(rest):
            cur = P[cur]-1
            i_s_score += C[cur]
            ans = max(ans, i_s_score)
print(ans)

Submission status: Time Limit Exceeded

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

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