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 main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))

    ans=-10**18
    for i in range(n):
        start,count=i,1
        val=c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]
        start = i
        if val > 0:
            a = (k//count-1)*val
            ans=max(a,ans)
            num=count+k%count
        else:
            a=0
            num=min(k,count)
        for _ in range(num):
            a += c[start]
            start=p[start]-1
            ans=max(a,ans)
    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=-10**18
for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1 != i:
        start = p[start]-1
        count += 1
        val += c[start]
    start = i
    if val > 0:
        a = (k//count-1)*val
        ans=max(a,ans)
        num=count+k%count
    else:
        a=0
        num=min(k,count)
    for _ in range(num):
        a += c[start]
        start=p[start]-1
        ans=max(a,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split(' ')]
number = [int(i) for i in input().split(' ')]
point = [int(i) for i in input().split(' ')]
res = []


for i in range(n) :
  i += 1
  cnt = 1
  num = number[i-1]
  loop = []
  tmp = 0
  while i != num :
    tmp += point[num-1]
    loop.append(tmp)
    num = number[num-1] 
    cnt += 1
  tmp += point[i-1]
  loop.append(tmp)
  if k >= cnt :
    if tmp >= 0 :
      loopcnt = k // cnt -1
      amari = k % cnt + cnt
      result = tmp*loopcnt
      num = i
      val = 0
      for _ in range(amari) :
        p = result + point[number[num-1]-1]
        num = number[num-1]
        val = max(result, p)
        result = p
      result = val
        
    else :
      result = max(loop)
  else :
      result = max(loop[0:k])
  res.append(result)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

r = []

_max = - (sys.maxsize - 1);
for i in range(n):
    currentmax = - (sys.maxsize - 1)
    current = i
    acc = 0
    ca = 0
    costs = []
    x = 0
    while x < k:
        current = p[current] - 1
        if current == i:
            break
        acc += c[current]
        costs.append(acc)
        currentmax = max(currentmax, acc)
        x += 1
    acc += c[current]
    costs.append(acc)

    if x+1 < k:
        r = k // len(costs)
        tmp = costs[-1] * r
        _max = max(_max, currentmax, tmp)
        for j in range(k % len(costs)):
            tmp = costs[-1] * r + costs[j]
            _max = max(_max, currentmax, tmp)
    else:
        _max = max(_max, currentmax)

print(_max)

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder :: Beginner Contest 175 :: D - Moving Piece
https://atcoder.jp/contests/abc175/tasks/abc175_d
"""
import sys
from math import inf


def solve(N, K, P, C):
    """Solve puzzle."""
    soln = -inf
    for v in range(N):
        # BFS to form graph
        S = 0
        for i in range(K):
            u = v
            v = P[v]
            S += C[v]
            soln = max(soln, S)
            
    return soln


def main():
    """Main program."""
    N, K = (int(i) for i in sys.stdin.readline().split())
    P = [int(i)-1 for i in sys.stdin.readline().split()]
    C = [int(i) for i in sys.stdin.readline().split()]
    print(solve(N, K, P, C))


if __name__ == '__main__':
    main()

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()))
result=-1000000001

for i in range(n):
    nextp=p[i]-1
    score=0
    for j in range(k):
        score+=c[nextp]
        nextp=p[nextp]-1
        if result<score:
            result=score
#    print(i,result,score,nextp)
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P_list = list(map(int, input().split()))
P_list = [x-1 for x in P_list]
C_list = list(map(int, input().split()))

max_score = C_list[P_list[0]]
for i in range(N):
    score = 0
    next_i = i
    for j in range(K):
        next_i = P_list[next_i]
        score += C_list[next_i]
        max_score = max(max_score, score)
print(max_score)

Submission status: Time Limit Exceeded

Solution code:

from numba import njit,i8
import numpy as np


n,k = map(int,input().split())
p = np.array([int(i)-1 for i in input().split()],np.int64)
c = np.array(list(map(int,input().split())),np.int64)

#@njit(i8(i8,i8[:],i8[:]), cache = True)
def calc_score(x,p,c):
    n = p.size
    score = 0
    score_list = np.zeros(n,np.int64)
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_list[cnt-1] = score
        else:
            return score_list[:k].max()
    
    if score>0:
        if k%cnt>0:
            tmp_max = score_list[:k%cnt].max()
        else:
            tmp_max = 0
        return tmp_max + (k//cnt) * score
    else:
        return score_list[:cnt].max()

ans = max(calc_score(i,p,c) for i in range(n))
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()))

pos = 0

ans = 0
for i in range(n):
  pos = i
  tmp_score = 0
  tmp_score_max = 0
  for j in range(k):
    pos = p[pos-1]
    tmp_score += c[pos-1]
    if j == 0:
      tmp_score_max = tmp_score
    else:
      tmp_score_max = max(tmp_score_max, tmp_score)
  if i == 0:
    ans = tmp_score_max
  else:
    ans = max(ans, tmp_score_max)
    
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()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, K + 1):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

print(ans)

Submission status: Time Limit Exceeded

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

score = []
ans = -10 ** 10

for i in range(n):
    score.append(0)
    a = p[i] - 1
    for j in range(k):
        score[i] += c[a]
        a = p[a] -1
        if score[i] > ans:
            ans = score[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
# 先頭に0番要素を追加すれば、配列の要素番号と入力pが一致する
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -1e9*1e9
s = [None] * n
# 開始ノードをsi
for si in range(1, n+1):

    # 閉ループのスコアを取り出す
    x = si
    #s = list()  # ノードの各スコアを保存
    s_len = 0
    tot = 0     # ループ1周期のスコア
    while 1:
        x = p[x]
        #s.append(c[x])
        s[s_len] = c[x]
        s_len += 1
        tot += c[x]
        if (x == si): break # 始点に戻ったら終了
    
    # siを開始とする閉ループのスコア(s)を全探
    #s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   # i回移動したときのスコア
        if (i+1 > k): break # 移動回数の上限を超えたら終了
        # 1周期のスコアが正ならば、可能な限り周回する
        if tot > 0:
            e = (k-(i+1))//s_len # 周回数
            now = t + tot*e      # i回移動と周回スコアの合計
        else:
            now = t
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
# 先頭に0番要素を追加すれば、配列の要素番号と入力pが一致する
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -1e9*1e9
# 開始ノードをsi
for si in range(1, n+1):

    # 閉ループのスコアを取り出す
    x = si
    s = list()  # ノードの各スコアを保存
    tot = 0     # ループ1周期のスコア
    while 1:
        x = p[x]
        s.append(c[x])
        tot += c[x]
        if (x == si): break # 始点に戻ったら終了
    
    # siを開始とする閉ループのスコア(s)を全探
    s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   # i回移動したときのスコア
        if (i+1 > k): break # 移動回数の上限を超えたら終了
        # 1周期のスコアが正ならば、可能な限り周回する
        if tot > 0:
            e = (k-(i+1))//s_len # 周回数
            now = t + tot*e      # i回移動と周回スコアの合計
        else:
            now = t
        ans = max(ans, now)

print(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()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: #ループ部分
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val #一周目はループのどの部分から始めるのが最適かわからないので
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':

    n,k = map(int,input().split())

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

    point = 0
    max_point = -1*(10**9)
    POI = []
    for i in range(n):#開始位置
        point = 0#初期化
        ind = P[i] - 1#開始だけここから
        for _ in range(k):#k回移動する
            #ポイント取得位置を決定
            #開始位置iの時のCi pointを加算
            point += C[ind]
            max_point = max(max_point,point)
            #next位置
            ind = P[ind] - 1
    print(max_point)

Submission status: Time Limit Exceeded

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

r = []

for i in range(len(p)):
    r.append((p[i]-1,c[p[i]-1]))

maxmax = -99999999999
for i in range(len(p)):
    current = i
    c = 0
    msf = -99999999999
    for j in range(k):
        c += r[current][1]
        msf = max(msf, c)
        current = r[current][0]
    maxmax = max(maxmax, msf)


print(maxmax)

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

Smax = C[0]
for i in range(N):
    Ktmp = K
    itmp = i
    Stmp = 0
    ret = 0
    while(Ktmp > 0):
        Ktmp -= 1
        itmp = P[itmp]-1
        Stmp += C[itmp]
        ret += 1
        if Stmp > Smax:
            Smax = Stmp
        
        if itmp == i and Stmp <= 0:
            break
        elif itmp == i and Stmp > 0:
            Ktmp = ret + K%ret
            itmp = i # 不要
            Stmp = Stmp*(K//ret - 1)
            while(Ktmp > 0):
                Ktmp -= 1
                itmp = P[itmp]-1
                Stmp += C[itmp]
                if Stmp > Smax:
                    Smax = Stmp

print(Smax)

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

Smax = C[0]
for i in range(N):
    Ktmp = K
    itmp = i
    Stmp = 0
    while(Ktmp > 0):
        Ktmp -= 1
        itmp = P[itmp]-1
        Stmp += C[itmp]
        if Stmp > Smax:
            Smax = Stmp
        if itmp == i and Stmp <= 0:
            break

print(Smax)

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

Smax = C[0]
for i in range(N):
    Ktmp = K
    itmp = i
    Stmp = 0
    while(Ktmp > 0):
        Ktmp -= 1
        itmp = P[itmp]-1
        Stmp += C[itmp]
        if Stmp > Smax:
            Smax = Stmp

print(Smax)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

N, K = [int(i) for i in input().split()]
PS = [int(i) -1 for i in input().split()]
CS = [int(i) for i in input().split()]

ans = -10000000000000000

for i in range(N):
  l = []
  n = i
  loop_total = 0
  while True:
    n = PS[n]
    l.append(CS[n])
    loop_total += CS[n]
    if n == i:
      break

  t = 0
  for x in range(len(l)):
    t += l[x]
    if x + 1 > K:
      break
    s = t
    if loop_total > 0:
      s += (K - x - 1) // len(l) * loop_total

    ans = max(ans, s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    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

    ans = -1e18
    for i in range(N):
        n = P[i]
        score = C[n]
        t = [score]
        while n != i:
            n = P[n]
            score += C[n]
            t.append(score)

        total = t[-1]
        l = len(t)
        for i in range(min(K, l)):
            temp_score = t[i]
            if total > 0 and K > l:
                e = int((K-(i+1))/l)
                temp_score += total*e
            ans = max(ans, temp_score)

    print(ans)


if __name__ == "__main__":
    resolve()

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

check_list = [0] * (N + 1)

ans = min(C)


def search_max(p_list, n):
    result = min(p_list)
    point_list = p_list[:] + p_list[:] + p_list[:]
    for j in range(0, len(p_list)):
        total = 0
        for k in range(j, j + n):
            total += point_list[k]
            if total > result:
                result = total
    return result


for i in range(1, N + 1):
    if check_list[i] == 0:
        buf = i
        p = 0
        point = []

        while check_list[buf] == 0:
            check_list[buf] = 1
            buf = P[buf]
            p += C[buf]
            point.append(C[buf])

        len_p = len(point)
        division, mod = divmod(K, len_p)

        if p > 0:
            if len_p <= K:
                max_p_total = search_max(point, len_p + mod)
                division -= 1
            else:
                max_p_total = search_max(point, K)
            point_buf = p * division + max_p_total
        else:
            if len_p <= K:
                max_p_total = search_max(point, len_p)
            else:
                max_p_total = search_max(point, K)
            point_buf = max_p_total

        if ans < point_buf:
            ans = point_buf

print(ans)

Submission status: Time Limit Exceeded

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

d = [0 for _ in range(n)]
pos = list(range(n))

for i in range(n):
    pos[i] = p[pos[i]] - 1
    d[i] += c[pos[i]]
cnt = max(d)

for _ in range(1, k):
    for i in range(n):
        pos[i] = p[pos[i]] - 1
        d[i] += c[pos[i]]
    cnt = max(max(d), cnt)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    N, K = mis()
    P = list(map(lambda x: x-1, mis()))
    C = lmis()
    ans = -INF
    for i in range(N):
        p = i
        tmp_score = 0
        k = K
        cycle = 0
        while k:
            p = P[p]
            tmp_score += C[p]
            ans = max(ans, tmp_score)
            k -= 1
            cycle += 1
            if p==i:
                if tmp_score < 0:
                    break
                elif k > cycle*2:
                    skip_loop = (k - cycle)//cycle
                    tmp_score *= skip_loop + 1
                    k -= skip_loop * cycle
        ans = max(ans, tmp_score)
    print(ans)








main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        q = deque([])
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            q.append(j)
            score += C[j]
            cnt += 1
            j = P[j]
        for j in q:
            f_cnt[j] = cnt
            f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        q = []
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            q.append(j)
            score += C[j]
            cnt += 1
            j = P[j]
        for j in q:
            f_cnt[j] = cnt
            f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    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()))

if max(C) <= 0:
    print(max(C))
    exit()
    
ans = -10**9
for start in range(1, N+1):
    for end in range(1, N+1):
        passed = []
        c_start2end = 0
        c_start2end_len = 0
        c_loop = 0
        c_loop_len = 0

        now = start
        fin = True
        end_flg = False
        cnt = 0
        while P[now-1] not in passed:
            if cnt >= N:
                fin = False
                break
            cnt += 1
            now = P[now-1]
            passed.append(now)
            if not end_flg:
                c_start2end += C[now-1]
                c_start2end_len += 1
            if now == end:
                end_flg = True
            c_loop += C[now-1]
            c_loop_len += 1
        
        if not fin:
          continue
        if start == end:
            c_start2end = c_loop
            c_start2end_len = c_loop_len
        tmp_ans = max(0, c_loop) * (K-c_start2end_len) // c_loop_len + c_start2end
        ans = max(ans, tmp_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()))

if max(C) <= 0:
    print(max(C))
    exit()
    
ans = -10**9
for start in range(1, N+1):
    for end in range(1, N+1):
        passed = []
        c_start2end = []
        c_loop = []

        now = start
        fin = True
        end_flg = False
        cnt = 0
        while P[now-1] not in passed:
            if cnt >= N:
                fin = False
                break
            cnt += 1
            now = P[now-1]
            passed.append(now)
            if not end_flg:
                c_start2end.append(C[now-1])
            if now == end:
                end_flg = True
            c_loop.append(C[now-1])
        
        if not fin:
          continue
        if start == end:
            c_start2end = c_loop

        tmp_ans = max(0, sum(c_loop)) * (K-len(c_start2end)) // len(c_loop) + sum(c_start2end)
        ans = max(ans, tmp_ans)
print(ans)

Submission status: Time Limit Exceeded

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

def orb_decomp(P, C):
    N = len(P)
    A = []
 
    for i in range(1,N + 1):
        j = i
        a = []
        while True:
            a.append(C[j - 1])
            j = P[j - 1]
            if j == i:
                break 
        A.append(a)
    
    return A

def cycle_sum(A, K):
    S = set()

    if K == 0:
        return 0

    for i in range(K):
        S.add(sum(A[0:i + 1]))
 
    return max(S)

def cycle_sup(A, K):
    L = len(A)
    S = sum(A)

    if K <= L or S <= 0:
        return cycle_sum(A, K)
    else:
        return cycle_sum(A, K % L) + S * (K // L)

D = orb_decomp(P, C)

print(max(cycle_sup(A, K) for A in D))

Submission status: Time Limit Exceeded

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

def orb_decomp(P, C):
    N = len(P)
    A = []
 
    for i in range(1,N + 1):
        j = i
        a = []
        while True:
            a.append(C[j - 1])
            j = P[j - 1]
            if j == i:
                break 
        A.append(a)
    
    return A

def cycle_sum(A, K):
    S = set()

    if K == 0:
        return 0

    for i in range(K):
        S.add(sum(A[0:i + 1]))
 
    return max(S)

def cycle_sup(A, K):
    L = len(A)
    S = sum(A)
    Q = K // L
    R = K % L

    if K <= L or S <= 0:
        return cycle_sum(A,K)
    else:
        return S * Q + cycle_sum(A, R)

D = orb_decomp(P, C)

print(max(cycle_sup(A, K) for A in D))

Submission status: Time Limit Exceeded

Solution code:
from sys import maxsize
from itertools import product

n, k = map(int, input().split())
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))

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, j in product(range(s_len), repeat=2):
        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)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def max_from_acc(A, b):
    r = -10**9-1
    acc = [0] + list(accumulate(A + A[:b]))
    for i in range(len(A)):
        for j in range(1, b+1):
            r = max(r, acc[i+j]-acc[i])
    return r

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]

checked = [False] * n
loops = []
for i in range(n):
    if checked[i]:
        continue
    checked[i] = True
    tmp = [i]
    next = P[i]
    while next != i:
        tmp.append(next)
        checked[next] = True
        next = P[next]
    loops.append(tmp)

# print(loops)

ans = -10**9-1
for loop in loops:
    t =len(loop)
    div, mod = divmod(k, t)
    if mod == 0:
        mod = t
        div -= 1
    C_loop = [C[p] for p in loop]
    loop_score = sum(C_loop)

    if t >=k:
        ans = max(ans, max_from_acc(C_loop, k))
    else:
        if loop_score > 0:
            ans = max(ans, max_from_acc(C_loop, mod)+loop_score*div)
        else:
            ans = max(ans, max_from_acc(C_loop, t))

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()))
result = []
for i in range(0,n):
    p[i] -= 1
for j in range(1,k+1):
    for s in range(0,n):
        l = 1
        f = c[s]
        temp = s
        while l < j:
            f += c[p[temp]]
            temp = p[temp]
            l += 1
        result.append(f)
print(max(result))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,K=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
if K == 1:
    print(max(c));exit()
ans = -10**10
def cycle(k):
    mo=k
    clen=0
    cscore=0
    flg = True
    cmax=[-10**10]
    while (mo != k or flg):
        clen+=1
        cscore+=c[mo]
        mo = p[mo]
        cmax.append(max(cmax[-1],cscore))
        if mo == k:
            flg = False
    if cscore<0:
        return cmax[min(K-1,clen-1)]
    return cscore*((K-1)//clen)+cmax[(K-1)%clen+1]
for i in range(n):
    a=cycle(i)
    if a>ans:
        ans = a
print(ans)