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:
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
    p = start
    for _ in range(L):
        front.append(p)
        p = lift(p)
    if L != N:
        for _ in range(L,R):
            cycle.append(p)
            p = lift(p)
        for _ in range(N-(N-L)%period,N):
            end.append(p)
            p = lift(p)
        cnt = (N-L)//period
    return front, cycle, end, cnt

################################################################################


import sys
input = sys.stdin.readline
from itertools import accumulate

def lift(x): return P[x-1]

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
res = -float("inf")
for i in range(1,N+1):
    front, cycle, end, cnt = cycle_getter(K,i)
    S = sum(C[j-1] for j in front)
    T = sum(C[j-1] for j in cycle)
    if cycle+end:
        U = max(0, max(accumulate(C[j-1] for j in cycle+end)))
    else: U=0
    if front:
        R = max(accumulate(C[j-1] for j in front))
    else: R=0
    res = max(res, S+T*(cnt-1)+U, S+U, R)
print(res)

Submission status: Time Limit Exceeded

Solution code:
first = input().split()
n = int(first[0])
k = int(first[1])

per = input().split()
per = [int(per[i]) for i in range(len(per))]
cells = input().split()
cells = [int(cells[i]) for i in range(len(cells))]

point_roop = []
for i in range(n):
  x = i
  point = 0
  count = 0
  while (x != i):
    x = per[x-1]
    point += cells[x-1]
    count += 1
  point_roop.append({"p": point,"c":count})
  
rank = []
result = []
for i in range(n):
  x = i
  point = 0
  count = 0
  tmp = []
  
  s = point_roop[i]
  if s["p"] > 0:
    if s["c"] < k:
      point += int(k/s["c"])*s["p"]
      count += int(k/s["c"])
      tmp.append(point)
      
  for i in range(k-count):
    x = per[x-1]
    point += cells[x-1]
    tmp.append(point)
  
  tmp.sort(reverse = True)
  rank.append(tmp[0])

rank.sort(reverse = True)
print(rank[0])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
m=C[P[0]-1]
for i in range(N):
    buf = 0
    k=i
    for _ in range(K):
        k = P[k] - 1
        buf += C[k]
        if m < buf:
            m = buf
print(m)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N+1):
    v = i
    score = 0
    size = 0
    while True:
        size += 1
        score += C[v]
        if i == P[v]:
            break
        v = P[v]

    if score > 0:
        tmp = score*(K//size-1)
        num = K%size+size
    else:
        tmp = 0
        num = min(K, size)
    
    v = i
    for _ in range(num):
        tmp += C[v]
        v = P[v]
        ans = max(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from sys import maxsize
 

def solve(n, k, p, c):
    used = [0] * n
    ss = []
    for i in range(n):
        if used[i]:
            continue
        now = i
        s = []
        while not used[now]:
            used[now] = 1
            s.append(c[now])
            now = p[now]
        ss.append(s)
 
    res = -maxsize
    for s in ss:
        s_len = len(s)
        cumsum = [0]
        # 2周分の累積和
        for i in range(2*s_len):
            cumsum.append(cumsum[-1] + s[i%s_len])
 
        max_sum = [-maxsize] * s_len
        for i in range(s_len):
            for j in range(s_len):
                max_sum[j] = max(max_sum[j], cumsum[i+j] - cumsum[i])
 
        for i in range(s_len):
            if i > k:
                continue
            v = (k - i) // s_len
            if i == 0 and v == 0:
                continue
            if cumsum[s_len] > 0:
                res = max(res, max_sum[i] + cumsum[s_len] * v)
            elif i > 0:
                res = max(res, max_sum[i])
    print(res)
 
 
if __name__ == '__main__':
    n, k = map(int, input().split())
    p = list(map(lambda x: int(x)-1, input().split()))
    c = list(map(int, input().split()))
    solve(n, k, p, c)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

@jit
def solve():
    n, k = map(int,input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split())) 
    max_score = -10000000000
    for i in range(len(p)):
        score = 0
        nx = i
        for _ in range(k):
            score = score + c[p[nx]-1]
            nx = p[nx] -1 
            max_score = max(max_score, score)
    
    print(max_score)
 
solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

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

def solve():
    max_score = -10**10

    for i in range(n):
        count = 1
        val = c[i]

        next_i = p[i] -1
        while next_i != i:
            count += 1
            val += c[next_i]
            next_i = p[next_i] - 1
        
        if val > 0:
            loop_num = (k//count -1)
            tmp_score = loop_num * val
            max_score = max(tmp_score, max_score)
            num = k%count+count

        else:
            tmp_score = 0
            num = min(k, count)

        next_i = i
        for _ in range(num):
            next_i = p[next_i] - 1
            tmp_score += c[next_i]
            max_score = max(tmp_score, max_score)
    
    print(max_score)

solve()

Submission status: Time Limit Exceeded

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

    max_score = max(C)
    score = C
    P_now = P
    P_ci = P
    for _ in range(K-1):
        score = [score[i]+C[num-1] for i, num in enumerate(P_now)]
        if max_score < max(score):
            max_score = max(score)
            P_ci = P_now
        P_now = [P[i-1] for i in P_now]
        if P_ci == P_now:
            break
    print(max_score)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    max_score = max(C)
    score = C
    P_now = P
    for _ in range(K-1):
        score = [score[i]+C[num-1] for i, num in enumerate(P_now)]
        max_score = max(score) if max_score < max(score) else max_score
        if score == C:
            break
        P_now = [P[i-1] for i in P_now]
    print(max_score)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

readline = stdin.readline

def inp():
    return int(readline())
def inpl():
    return list(map(int, readline().split()))

INF = 1001001001

# ---------------------------------------

def main():
    n, k = inpl()
    p = [0] + inpl()
    c = [0] + inpl()

    ans = - INF

    for i in range(1, n + 1):
        cycle_cnt = 0
        cycle_sum = 0
        v = i

        while True:
            v = p[v]
            cycle_cnt += 1
            cycle_sum += c[v]
            if v == i: break
        
        cnt = 0
        path = 0

        while True:
            v = p[v]
            cnt += 1
            path += c[v]

            if cnt > k: break

            num = (k - cnt) // cycle_cnt
            score = path + max(0, cycle_sum) * num
            ans = max(ans, score)

            if v == i: break

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

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

INF = 1001001001

# ---------------------------------------



n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
p = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))
 
ans = -float("inf")
def helper(index):
    visited  = {index}
    looplen = 1
    looptotal = c[index]
    while p[index]-1 not in visited:
        nextindex = p[index] - 1
        looplen += 1
        looptotal += c[nextindex]
        visited.add(nextindex)
        index = nextindex
    return (looplen,looptotal)
 
for i in range(n):
    looplen,looptotal = helper(i)
    if looptotal >= 0:
        cur = looptotal*((k//looplen)-1) if k >= looplen else 0
        remain = looplen + (k%looplen) if k >= looplen else k
    else:
        cur = 0
        remain = looplen
    curmax = -float("inf")
    curindex = i
    for _ in range(remain):
        nextindex = p[curindex]-1
        cur += c[nextindex]
        curmax = max(curmax,cur)
        curindex = nextindex
    ans = max(ans,curmax)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

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

INF = 1001001001

# ---------------------------------------

n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    loop = 0
    nxt = p[i]
    cost = [0]
    for j in range(1, k + 1):
        loop += c[nxt]
        ans = max(ans, loop)
        nxt = p[nxt]
        cost.append(loop)
        if nxt == p[i]:
            if loop > 0:
                cnt = k % j
                score = loop * (k // j)
                ans = max(ans, score + cost[k % j])
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc175/tasks/abc175_d
# ダブリングで解く
# K>ループ長の場合、累積の最後の値が負ならmaxを取ればいいし、正ならば 累積の最後の値*周数をかけてから計算
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations, accumulate
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N, K = ints()
P = mina(*ints())
C = ints()

next = [[-1] * N for _ in range(32)]  # next[k][i] ノードiから2^k回移動するときのノード
score = [[0] * N for _ in range(32)]  # score[k][i] ノードiから2^k回移動するときに加算されるスコア
# nextの構築
next[0] = P
for k in range(31):
    for i in range(N):
        next[k + 1][i] = next[k][next[k][i]]
# scoreの構築
for i in range(N):
    score[0][i] = C[P[i]]
for k in range(31):
    for i in range(N):
        score[k + 1][i] = score[k][i] + score[k][next[k][i]]


# これじゃ道中がわからない...
# 一点しか求まらない
def get_score(i, k):
    now = i
    ret = 0
    for j in range(k.bit_length()):
        if (k >> j) & 1:
            ret += score[j][now]
            now = next[j][now]
    return ret


# 各ノードからK回移動したときのscoreを計算する
ans = -10**10
for i in range(N):
    for j in range(1, N + 1):
        ans = max(ans, get_score(i, j))
        # print(get_score(i, j))

    for j in range(max(K - N, 1), K + 1):
        ans = max(ans, get_score(i, j))
        # print(get_score(i, j))

# O(5*10^7 * log K)だけど、更に高速にするのは実装が面倒だなぁ

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1回以上K回以下
ansF=-1000000000000000000
for i in range(n):
    #すでに辿ったもの
    check=[False]*n
    #辿った順番
    turns=[]
    #今
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    #答え(今の)
    ans=0
    #kのうち何回分
    #更新を毎回行う
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    #サイクルの長さ
    l=len(turns)
    #サイクルの和(あまりも)
    #サイクルどこで止めるか
    x=0
    for j in range(l):
        x+=c[turns[j]]
    #そもそもサイクル回らない場合
    if spare<=l:
        for j in range(spare):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    #サイクル回した方が良い場合もある
    #最後のサイクルは回さない方が良いパターンも
    if x>=0:
        ans+=(x*(spare//l-1))
        ansF=max(ans,ansF)
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    #サイクル回さない方がいい場合
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)

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()))
point_start_with = [0 for i in range(n)]
roop_count = [1 for i in range(n)]
for i in range(n):
    now = (i + 1)
    now_score = 0
    while p[now - 1] != (i + 1):
        now = p[now - 1]
        now_score += c[now - 1]
        roop_count[i] += 1
    point_start_with[i] = now_score
# 多分0でいい
ans = -(10**9 * 5000)
for i in range(n):
    # iからスタートする場合
    score = 0
    remain_move = 0
    cand_score = 0
    if point_start_with[i] + c[i] > 0 and k > roop_count[i]:
        # 一周以上する可能性がある場合
        # n週して、残りの動ける回数
        # print("Yes")
        round_count = (k // roop_count[i]) - 1
        remain_move = k - round_count * roop_count[i]
        cand_score = round_count * ( point_start_with[i] + c[i] )
    else:
        remain_move = k
        score = -(10**9 * 5000)
        cand_score = 0
    now = i
    for j in range(remain_move):
        now = p[now] - 1
        cand_score += c[now]
        score = max(score, cand_score)
    # print("start : {}  score : {}".format(i,score))
    ans = max(score, ans)
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()))
route_list = [[] for i in range(n)]
for i in range(n):
    now = (i + 1)
    now_score = 0
    while p[now - 1] != (i + 1):
        route_list[i].append(now_score)
        now = p[now - 1]
        now_score += c[now - 1]
    route_list[i].append(now_score)
# 多分0でいい
ans = -(10**9 * 5000)
for i in range(n):
    # iからスタートする場合
    score = 0
    remain_move = 0
    cand_score = 0
    if route_list[i][-1] + c[i] > 0 and k > len(route_list[i]):
        # 一周以上する可能性がある場合
        # n週して、残りの動ける回数
        # print("Yes")
        round_count = (k // len(route_list[i])) - 1
        remain_move = k - round_count * len(route_list[i])
        cand_score = round_count * ( route_list[i][-1] + c[i] )
    else:
        remain_move = k
        score = -(10**9 * 5000)
        cand_score = 0
    now = i
    for j in range(remain_move):
        now = p[now] - 1
        cand_score += c[now]
        score = max(score, cand_score)
    # print("start : {}  score : {}".format(i,score))
    ans = max(score, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

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

def solve():
    max_score = -10000000000
    for i in range(len(p)):
        score = 0
        nx = i
        for _ in range(k):
            score = score + c[p[nx]-1]
            nx = p[nx] -1 
            max_score = max(max_score, score)
    
    print(max_score)

solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Pn=list(map(int,input().split()))
Cn=list(map(int,input().split()))
Score=0
m=min(Cn)
ScoreList=m
ScoreMAX=m
for i in range(N):
    Score=0
    ScoreList=m
    t=i
    j=0
    while j <=K-1:
        Score=Score+Cn[t]
        ScoreList=max(ScoreList,Score)
        t=Pn[t]-1
        j=j+1
    ScoreMAX=max(ScoreMAX,ScoreList)
print(ScoreMAX)

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
  pos=i
  for j in range(k):
    pos = P[pos]-1
    tmp += C[pos]
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Ps = [i - 1 for i in Ps]
Cs = list(map(int, input().split()))
max_score = -float("inf")


for i in range(N):
    scores = []
    idx = i  # starting index
    while True:
        idx = Ps[idx]  # point to the next index
        scores.append(Cs[idx])  # fetch a score to add
        if idx == i:  # when the cycle is closed
            break

    len_cycle = len(scores)
    sum_cycle = sum(scores)

    if sum_cycle <= 0:  # when each cycle reduces the total score
        score = 0
        for j in range(min(K, len_cycle)):
            score += scores[j]
            max_score = max(max_score, score)
    else:
        if K // len_cycle > 0:
            num_multiply = (K // len_cycle) - 1
            score = sum_cycle * num_multiply
            for j in range(K % len_cycle + len_cycle):
                score += (scores*2)[j]
                max_score = max(max_score, score)
        else:
            num_multiply = 0  # len_cycle > K
            score = sum_cycle * num_multiply
            for j in range(K):
                score += scores[j]
                max_score = max(max_score, score)

print(max_score)

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


def calcScore(C_list, P_list, idx, num_operation):
    score = 0
    scores = []
    for i in range(num_operation):
        idx = P_list[idx] - 1
        score += C_list[idx]
        scores.append(score)
    return max(scores)


max_scores = [calcScore(Cs, Ps, i, K) for i in range(N)]

print(max(max_scores))

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

def calcScore(C_list, P_list, idx, num_operation):
  score = 0
  for i in range(num_operation):
    idx = P_list[idx] - 1
    score += C_list[idx]
    if i == 0:
      max_score = score
    else:
      max_score = max(max_score, score)
  return max_score

max_scores = [calcScore(Cs, Ps, i, K) for i in range(N)]

print(max(max_scores))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
#for i in range(len(P)): #Pの中身は次の動く先の位置なのでデクリメントする
#    P[i] -= 1

ans = -99999999999999

for i in range(N):
    x = i
    total = 0
    s=[]
    while(1):#サイクルごとに長さをまず求める，
        x = P[x]-1
        s.append(C[x])
        total += C[x]
        if x == i:
            break
    l = len(s)#サイクルの長さ
    t = 0
    for i in range(l):#サイクルの中でどこで終わるのがベストか探す
        t += s[i]
        if i+1> K:#Kがサイクルより短かったらそこで終わる
            break
        now = t
        if total > 0:
            cycle = int((K-i-1)/l)
            now += total*cycle

        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(len(P)): #Pの中身は次の動く先の位置なのでデクリメントする
    P[i] -= 1

ans = -99999999999999

for i in range(N):
    x = i
    total = 0
    s=[]
    while(1):#サイクルごとに長さをまず求める，
        x = P[x]
        s.append(C[x])
        total += C[x]
        if x == i:
            break
    l = len(s)#サイクルの長さ
    t = 0
    for i in range(l):#サイクルの中でどこで終わるのがベストか探す
        t += s[i]
        if i+1> K:#Kがサイクルより短かったらそこで終わる
            break
        now = t
        if total > 0:
            cycle = int((K-i-1)/l)
            now += total*cycle

        ans = max(ans, now)

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()))
r=[]

for i in range(n):
  number=0
  count=0
  s=p[i]
  while number<k:
    s=p[s-1]
    count+=c[s-1]
    number+=1
    r.append(count)
r.sort()
print(r[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
from itertools import product
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def LF(): return list(map(float, input().split()))
def LC(): return [c for c in input().split()]
def LLI(n): return [LI() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]

def array2d(N, M, initial=0):
    return [[initial]*M for _ in range(N)]

def copy2d(orig, N, M):
    ret = array2d(N, M)
    for i in range(N):
        for j in range(M):
            ret[i][j] = orig[i][j]
    return ret


INF = float("inf")
MOD = 10**9 + 7


def main():
    N, K = MAP()
    P = LI_()
    C = LI()

    # サイクルとは閉路のことである。順列の性質として、有向グラフで記述した時、必
    # ずサイクルの集合となる。
    ans = -INF
    for i in range(N):
        v = i
        cycle_sum = 0
        cycle_cnt = 0

        # iを始点とし、閉路の和と長さを求める
        while True:
            cycle_cnt += 1
            cycle_sum += C[v]
            v = P[v]
            if v == i:
                break

        path = 0
        cnt = 0

        while True:
            cnt += 1
            path += C[v]
            if cnt > K:
                break

            # サイクルを可能な限りまわる。サイクルの総和が負の場合は回らない
            num = (K-cnt)//cycle_cnt
            score = path + max(0, cycle_sum)*num
            ans = max(ans, score)

            v = P[v]
            if v == i:
                break

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  dic = {}
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in dic:
      point_loop = 0
      loop = 0
      pos_set = set([f_pos])
      while True:
        f_pos = positions[f_pos]
        point_loop += scores[f_pos]
        #print('pos', f_pos)
        #print(point)
        loop += 1
        if f_pos in pos_set:
          for j in pos_set:
            dic[j] = [loop, point_loop]
          break
        pos_set.add(f_pos)
    else:
      loop, point_loop = dic[f_pos]
    #print(loop, point)
    loop_c = k // loop
    r = k % loop
    if loop_c == 0 or point_loop <= 0:
      if point_loop <= 0:
        if loop_c > 0:
          r = loop
      point = 0
      for _ in range(r):
        f_pos = positions[f_pos]
        point += scores[f_pos]
        max_point = max(max_point, point)
    else:
      point1, point2 = 0, 0
      point1 = loop_c * point_loop
      max_point1 = point1
      for _ in range(r):
        f_pos = positions[f_pos]
        point1 += scores[f_pos]
        max_point1 = max(point1, max_point1)
      f_pos = i
      point2 = (loop_c - 1) * point_loop
      max_point2 = point2
      for _ in range(loop):
        f_pos = positions[f_pos]
        point2 += scores[f_pos]
        max_point2 = max(point2, max_point2)
      max_point = max(max_point, max(max_point1, max_point2))
  print(max_point)

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 s in range(N):
    ### Step1
    S = []  # 累積和S. ただし, 初項は0ではなく1回目の移動後の得点とする.
    # 1回目の移動
    i = P[s] - 1
    S.append(C[i])
    # 2回目以降の移動. スタート地点に戻ってくるまで繰り返し.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2: KとSの長に応じて場合分けして, 得点の最大値を求める.
    # 1周未満しか移動できない場合:
    if K <= len(S):
        score = max(S[:K])
    # 1周以上回ることができるが, ループを1周したときに得点が減る場合:
    elif S[-1] <= 0:
        score = max(S)
    # 1週以上回ることができ, かつループを1週するごとに得点が増える場合:
    else:
        # ループを (K // len(S) - 1)回 廻る場合:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        # ループを (K // len(S))回 廻る場合:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        # score1 と score2 の大きい方がこの場合の得点の最大値
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)