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 sys
import numpy as np
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

G = [0] * N

d = -10 ** 9
j = 0

i = 0
# for j in range(N):
#     print(i)
#     G[j] = C[i]
#     i = P[i] - 1

s = 0

for l in range(N):
    s = 0
    j = l
    for i in range(K):
    

        s += C[j]        
        
        if s > d:
            d = s
        j = P[j] - 1
print(d)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
INT_MIN=-10**13
import bisect as B
###############################################################################\
n,p=INPUT()
P=INPUT()
C=INPUT()
ans=-10**100
for k in range(1,p+1):
    for start in range(n):
        bool=[False]*n
        stage=[]
        i=start
        while(bool[i] is False):
            stage.append(C[P[i]-1])
            bool[i]=True
            i=P[i]-1
        #print(stage)
        s=(k//len(stage))*sum(stage)+sum(stage[0:k%len(stage)])
        ans=max(s,ans)
        #print(stage," ",ans)
    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
解説動画のコードを参考にしました
https://atcoder.jp/contests/abc175/submissions/15945829
"""

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

ans = int(-1e18)

for start in P:
    pos = start
    scores = [] # スコア格納用

    while True:
        pos = P[pos-1] # 移動
        scores.append(C[pos-1]) # スコアの格納
        # 1周したかどうか
        if pos == start: break

    # 周期途中のどこでやめるか判定
    L = len(scores)
    S = sum(scores)
    period_score = 0
    for i in range(L):
        period_score += scores[i] # スコアの加算
        # 試行回数を超えていないか
        if i+1 > K: break
        total_score = period_score
        # 1周期の合計スコアが正なら、周期を重ねるごとにスコア増
        if S > 0:
            total_score += S * ((K-(i+1)) // L)
        ans = max(ans, total_score)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
p=lnii()
c=lnii()

ans=-10**18
for i in range(n):
  ini_x=i
  x=i
  point=[]

  t_ans=0
  cnt=0
  t_max=-10**18
  while True:
    x=p[x]-1
    t_point=c[x]
    point.append(t_point)
    t_ans+=t_point
    t_max=max(t_max,t_ans)
    cnt+=1
    if x==ini_x:
      break

  if t_ans<0:
    ans=max(ans,t_max)
  else:
    num=k//cnt
    num-=1
    c_ans=t_ans*num
    c_max=c_ans
    zan=k-(num*cnt)
    for j in range(zan):
      x=p[x]-1
      c_ans+=c[x]
      c_max=max(c_max,c_ans)
    ans=max(ans,c_max)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    used = [False] * len(P)
    for index in range(1, len(P)):
        if used[index]:
            continue
        used[index] = True
        graph = [C[index]]
        index = P[index]
        while not used[index]:
            graph.append(C[index])
            used[index] = True
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def next(i):
    return p[i]

x=-10000000000
for i in range(n):
    m=i
    cn=[]
    cnt=0
    for _ in range(k):
        m=p[m]-1
        cnt+=c[m]
        cn.append(cnt)
    x=max(x,max(cn))
print(x)

Submission status: Time Limit Exceeded

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

g = dict()
a = set()
gi = 0
for i in range(n):
    if i in a:
        continue
    next_p = i
    g[gi] = deque()
    while True:
        if next_p in g[gi]:
            break
        g[gi].append(next_p)
        a.add(next_p)
        next_p = p[next_p]-1
    gi += 1

score = dict()
for i in g.keys():
    for j in g[i]:
        if i not in score.keys():
            score[i] = c[j]
        else:
            score[i] += c[j]

ans = []
for i in range(n):
    for key, v in g.items():
        if i in v:
            group = key
    s = len(g[group])
    r = deepcopy(g[group])
    r.rotate(-g[group].index(i))
    amari = k%s
    num = k//s
    if score[group] > 0:
        tmp = score[group] * num
        for j in range(amari):
            tmp += c[r[j]]
        ans.append(tmp)
    else:
        ans.append(c[r[0]])
        tmp = c[r[0]]
        for j in range(1, s):
            tmp += c[r[j]]
            if ans[-1] < tmp:
                ans[-1] = tmp
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# from pathlib import Path

"""
解説動画のコードを参考にしました
https://atcoder.jp/contests/abc175/submissions/15945829
"""


stdin = iter(
    map(int, l.split()) for l in
    # Path('./test/sample-4.in').read_text().split('\n')
    open(0).read().split('\n')
)

N,K = next(stdin)
*P, = next(stdin)
*C, = next(stdin)

ans = int(-1e18)

for start in P:
    pos = start
    scores = [] # スコア格納用

    while True:
        pos = P[pos-1] # 移動
        scores.append(C[pos-1]) # スコアの格納

        # 1周したかどうか
        if pos == start: break

    # 周期途中のどこでやめるか判定
    L = len(scores)
    S = sum(scores)
    period_score = 0
    for i in range(L):
        period_score += scores[i] # スコアの加算
        # 試行回数を超えていないか
        if i+1 > K: break
        total_score = period_score
        # 1周期の合計スコアが正なら、周期を重ねるごとにスコア増
        if S > 0:
            total_score += S * ((K-(i+1)) // L)
        ans = max(ans, total_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()))
P = [p-1 for p in P]

# 1,ループを検出
# 2,ループごとの最大値の計算
# 3,結果の出力

visited = set() #探索済みのものを格納する

ans = 0
for i in range(N):
  if i in visited: #探索済みの場合
    continue
  
  # 1,ループを検出
  j = i
  C_tmp = [] #たどる順番にコストを格納
  while j not in visited:
    C_tmp.append(C[j])
    visited.add(j)
    j = P[j] #次のjへ
    
  # 2,ループごとの最大値の計算
  N_tmp = len(C_tmp) #ループ長さ
  tmp = 0 #何も足さないときは0(これが最大になる可能性もあるので注意)
  
  # N_tmp < K の場合には注意が必要
  # C_tmpの全要素の和が正になるときには、できるだけループを多く回したい
  # C_tmpの全要素の和が負になるときには、１周以内に収めたい
  loop_sum = max(0, sum(C_tmp)) #負の場合にはなかったことにすればよい
  #ただし、これらのうち番号が負になるものや、範囲外のものは当然のぞく
  
  #調べたいのは、
  #  sum(C)が正のとき  操作の回数が K-N_tmp+1 から K まで
  #  sum(C)が負のとき  操作の回数が 0 から N_tmp-1 まで
  #　  例1：N_tmp = 5, K = 8, ループ１周の和が正の時
  #       0 　 1 　 2 　 3 　 4 ◯ （「上段」）
  #       5 ◯ 6 ◯ 7 ◯ 8 ◯   　 （「下段」）
  #　  例2：N_tmp = 5, K = 8, ループ１周の和が負の時
  #       0 ◯ 1 ◯ 2 ◯ 3 ◯ 4 ◯ 
  #       5 　 6 　 7 　 8 　
  #    ただし、ループを１周ごとになかったことにするなら、結局次のように考えて良い
  #       0 　 1 　 2 　 3 　 4 ◯ （「上段」）
  #       5 ◯ 6 ◯ 7 ◯ 8 ◯   　 （「下段」）
  #　  例3：N_tmp = 5, K = 3, ループ１周の和が正の時
  #       0 ◯ 1 ◯ 2 ◯ 3 ◯   　 （「上段」）
  
  #ひとまず、回すことができる最大のループ回数を計算し、その和を求めておく
  base = loop_sum * (K // N_tmp)
  
  #はみ出した部分について和を求める。（「下段」については、loop_sumを一回引くことで対処）
  # (操作回数) % N_tmp を lとして、連続したl個の要素の和を調べる
  ans = max(ans, base) # l = 0 のとき
  behind = False #下段を調べているときにTrueとする
  for l in range(1,min(N_tmp, K+1)): # l > 1 のとき
    if (not behind) and l > K % N_tmp: #下段に移るとき、ループを１週戻す
      behind = True
      base -= loop_sum
    summ = sum(C_tmp[0:l]) + base
    for j in range(N_tmp):
      ans = max(ans, summ) #最大値の更新
      summ += C_tmp[(j+l)%N_tmp] - C_tmp[j] #始点を1ずらす
      
      
#3,結果の出力
# K > 1に注意
print(max(C) if max(C) < 0 else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    p = set(P[1:])
    while p:
        index = p.pop()
        graph = [C[index]]
        index = P[index]
        while index in p:
            graph.append(C[index])
            p.remove(index)
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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()))
from collections import deque
toku=[0]*(n+1)
for i in range(1,n+1):
  ans=[0]
  d=deque()
  visit=[0]*(n+1)
  d.append(i)
  while d:
    now=d.pop()
    if visit[now]==0:
      visit[now]=1
      ans.append(ans[-1]+c[p[now-1]-1])
      d.append(p[now-1])
  syuki=sum(visit)
  if ans[-1]>=0:
    if k%syuki==0:
      toku[i]=max((k//syuki)*ans[-1],(k//syuki-1)*ans[-1]+max(ans))
      
    else:
      toku[i]=(k//syuki)*ans[-1]+max(ans[1:k%syuki+1])
  else:
    if k//syuki==0:
      toku[i]=max(ans[1:k%syuki+1])
    else:
      toku[i]=max(ans[1:])
print(max(toku[1:]))

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 si in range(N):
	x=si
	score=[]
	while True:
		x=p[x]-1
		score.append(c[x])
		if x==si:
			break
	l_total=sum(score)
	l=len(score)
	t=0
	for i in range(l):
		t+=score[i]
		if i+1>K:
			break
		now_score=t
		if l_total>0:
			e=int((K-(i+1))/l)
			now_score+=l_total*e
		ans=max(ans,now_score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
cell = list(map(int, input().split()))
score = list(map(int, input().split()))

score_list = sorted(score)

for c in range(len(cell)): 
  new_score = 0
  new_cell  = cell[c]

  for k in range(K): 
    new_score += score[new_cell -1]
    if new_score >  score_list[-1]:
      score_list.append(new_score)
    new_cell = cell[new_cell -1]

print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
cell = list(map(int, input().split()))
score = list(map(int, input().split()))

score_list = score

for c in range(len(cell)): 
  new_score = 0
  new_cell  = cell[c]

  for k in range(K): 
    new_score += score[new_cell -1]
    score_list.append(new_score)
    new_cell = cell[new_cell -1]

print(max(score))

Submission status: Time Limit Exceeded

Solution code:
import math

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

Plist = []
for i in range(N):
    tmp = [i]
    for j in range(N+1):
        tmp.append(P[tmp[j]]-1)
        if tmp[j+1] == tmp[0]:
            Plist.append([tmp ,j+1])
            break


ans = -6000 * 10**9

for i in range(N):
    numroop = Plist[i][1]
    scoremax = -6000 * 10**9
    
    if numroop > K:
        tmp=[0]
        for j in range(1, K+1):
            tmp.append(tmp[j-1] + C[Plist[i][0][j]])
        scoremax = max(scoremax, max(tmp[1:]))
        
        
    
    else:
        tmp=0
        for j in range(1, numroop+1):
            tmp += C[Plist[i][0][j]]

        if tmp >= 0:
            scoremax = tmp * (math.floor(K/numroop)-1)
            
            tmp = [0]
            for j in range(1, K - numroop * (math.floor(K/numroop)-1) +1 ):
                tmp.append(tmp[j-1] + C[Plist[i][0][j%numroop]])
            scoremax = max(scoremax, scoremax + max(tmp[1:]))
            
        else:
            tmp=[0]
            for j in range(1, numroop+1):
                tmp.append(tmp[j-1] + C[Plist[i][0][j]])
            scoremax = max(scoremax, max(tmp[1:]))

    ans = max(ans, scoremax)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]
cycle = []


ans = -float('inf')
for sn in range (N):
    cost = []
    nn = sn
    while True:
        cost.append(C[nn])
        nn = P[nn]
        if sn == nn:
            break
    total = sum(cost)
    l = len(cost)

    t = 0
    for i in range(l):
        t += cost[i]
        if i+1 > K: break
        now = t
        if total > 0:
            e = (K-i-1)//l
            now += total * e
        ans = max(ans,now)


print(int(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 = []
for i in range(N):
  pos = P[i]-1
  s = [C[i]]
  j = 1
  while j < K and pos != i:
    s.append(s[-1]+C[pos])
    pos = P[pos]-1
    j += 1
  smax = max(s)
  length = len(s)
  if length < K and s[-1] > 0:
    if K%length != 0:
      smod = s[:K%length]
      smodmax = max(smod)
    else:
      smodmax = 0
    scores.append(max(s[-1] * ((K//length)-1) + smax, s[-1] * (K//length), s[-1] * (K//length) + smodmax))
  else:
    scores.append(smax)
print(max(scores))

Submission status: Time Limit Exceeded

Solution code:
def calc_max(p):
    p=p
    l=[]
    S=0
    max_range=0
    tmpM=0
    for _ in range(K):
        l.append(C[p])
        S+=C[p]
        if tmpM<S:
            tmpM=S
            max_range=_
        p=P[p]
        if p==P:
            break
    if S>0:
        t=len(l)
        tmpK=K-max_range
        return S*(tmpK//t)+tmpM
    else:
        return tmpM

N,K=map(int,input().split())
P=list(map(lambda x:int(x)-1,input().split()))
C=list(map(int,input().split()))
ans=max(map(calc_max,range(N)))
if ans==0:
    print(max(C))
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

checked_list = [0 for _ in range(N)]
min_INF = -1 * 10 ** 10
max_score = min_INF
for i in range(N):
    if checked_list[i] == 1:
        continue
    posit = i
    loop_list = [posit]
    score_list = []
    for j in range(N):
        posit = P_list[posit] - 1
        if j == 0:
            score_list.append(C_list[posit])
        else:
            score_list.append(score_list[-1] + C_list[posit])
        if posit in loop_list:
            break
        loop_list.append(posit)

    len_loop = len(loop_list)
    for k in range(len_loop):
        # print("loop", loop_list)
        # print("score", score_list)
        checked_list[loop_list[k]] = 1
        temp_max_score = 0
        rest_score = min_INF
        if score_list[-1] > 0 and K // len_loop > 0:
            temp_max_score += (K // len_loop - 1) * score_list[-1]
            # 最後に1周すべきか
            rest_score = max(max(score_list), max(score_list[:K % len_loop], default=min_INF) + score_list[-1])
            # print(loop_list[k], temp_max_score, K, len_loop, K // len_loop)
        rest_score = max(max(score_list[:min(K, len_loop)]), rest_score)
        temp_max_score = temp_max_score + rest_score
        # print(loop_list[k], temp_max_score, rest_score)
        max_score = max(max_score, temp_max_score)
        # ループ内でずらす
        now_score = score_list.pop(0)
        len_score = len(score_list)
        score_list = [score_list[l] - now_score for l in range(len_score)]
        score_list.append(score_list[-1] + now_score)

print(max_score)

Submission status: Time Limit Exceeded

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

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

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

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

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        # Rewrite [1, K] as form q * L + r, :
        # 0L + 1, 0L + 2, ..., 0L + L
        # 1L + 1, 1L + 2, ..., 1L + L
        # ⋮ 
        # tL + 1, tL + 2, ... (t = floor((K - r) / L))

        # We can ignore 1L + r, 2L + r, ..., (t - 1) * L + r
        # since the total cost of loop is either positive or negative
        # When positive, 0L + r < 1L + r < 2L + r < tL + r
        # When negative, the answer should be 0L + r

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

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)


    def calc_score(start):
        order = [None] * n
        accum = [None] * n
        order[start] = 0
        accum[start] = 0
        place = start
        cnt = 0
        current_score = 0
        M = -inf

        while cnt < k:
            place = P[place]    # 移動
            cnt += 1    # 移動回数
            current_score += C[place]    # 移動後の index でスコアに追加
            M = max(M, current_score)    # [スタートの次点, 現在地] まで任意の場所をゴールに選ぶときのスコア最大値
            if order[place] is None:
                # 未訪問
                order[place] = cnt
                accum[place] = current_score
            else:
                # 訪問ずみ。loop
                head_len = order[place]
                loop_len = cnt - head_len
                head_score = accum[place]
                loop_gain = current_score - accum[place]
                if loop_gain <= 0:
                    # debug('encountered loop, but non-positive loop.')
                    return M
                else:
                    # debug('encountered positive loop.')
                    loop_times, res = divmod(k - head_len, loop_len)
                    # place からスタートして "0 以上" res 以下だけ進むときの
                    res_score = 0    # 稼ぐ最大スコア
                    tmp_score = 0    # 現在の累積スコア
                    tmp_place = place    # 現在地
                    for i in range(res):
                        tmp_place = P[tmp_place]
                        tmp_score += C[tmp_place]    # 移動後の index でスコアに追加
                        res_score = max(res_score, tmp_score)
                    loop_score = head_score + loop_times * loop_gain + res_score
                    return loop_score

        # debug('never encountered loop.')
        return M
            

    n, k = mi()
    P = lmi_0()
    C = lmi()

    ans = -inf
    for i in range(n):
        # debug(ans)
        ans = max(ans, calc_score(i))
    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 = -float("INF")
for i in range(n):
    pi = p[i]
    x = c[pi-1]
    a = x
    for j in range(k-1):
        pi = p[pi-1]
        a = max(a,x+c[pi-1])
        x += c[pi-1]
    ans = max(ans,a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    INF = 10 ** 18
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))

    visited = [0] * N
    cycles = []

    for i in range(N):
        if visited[i]:
            continue
        score = []
        v = i
        visited[v] = True
        score.append(C[v])
        while not visited[P[v]]:
            v = P[v]
            visited[v] = True
            score.append(C[v])
        cycles.append(score)

    ans = -INF
    for cy in cycles:
        length = len(cy)
        c_num = max(0, (K - 1) // length - 1)
        total = max(0, sum(cy) * c_num)
        rest = K - (c_num * length)
        l_cy = cy + cy + cy
        for l in range(length):
            total_rest = 0
            for diff in range(rest):
                total_rest += l_cy[l + diff]
                ans = max(ans, total + total_rest)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    dp[i][-1] = 0
    pos = i
    for j in range(K):
        pos = P[pos]-1
        dp[i][j] = dp[i][j-1] + C[pos]

print(max(chain(*dp)))

Submission status: Time Limit Exceeded

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

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

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

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


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

print(max(score_array))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    score = deque([0])
    while j < k:
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if now == i:
            break
    ans = max(ans, max(list(score)[1:]))
    if j < k and score[-1] > 0:
        loop_num = k//j
        rest = k%j
        ans = max(ans, max(list(score)[:rest+1])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-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()))


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

def score(a, k):
    now = p[a]
    s = c[now]
    cnt = 1
    ans = s
    while now != a and cnt < k:
        now = p[now]
        s += c[now]
        ans = max(ans, s)
        cnt += 1
    if cnt == k:
        return ans
    if k % cnt == 0:
        return (k // cnt - 1) * s + ans
    s = (k // cnt) * s
    k %= cnt
    cnt = 0
    while cnt < k:
        now = p[now]
        s += c[now]
        ans = max(ans, s)
        cnt += 1
    return ans

print(max(score(i, k) for i in range(n)))