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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


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

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

ans = -float('inf')
for i in range(n):
    s = []
    j = p[i]-1 
    s.append(c[j])
    while j != i:
        j = p[j]-1
        s.append(s[-1]+c[j])
    l = len(s)
    if k <= l:
        a = max(s[:k])
    elif s[-1] <= 0:
        a = max(s)
    else:
        w, r = divmod(k, l)
        a1 = s[-1]*(w-1) + max(s)
        a2 = s[-1]*w
        if r != 0:
            a2 += max(0, max(s[:r]))
        a = max(a1, a2)
    ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -1*10**9
for si in range(N):
  x = si
  total = 0
  l = 0
  s = list()
  while(1):
    x = p[x]-1
    s.append(c[x])
    l += 1
    total += c[x]
    if x == si:
      break
  t = 0
  for i in range(l):
    now = 0
    if (i+1) > K:
      break
    t += s[i]
    now += t
    if total > 0:
      e = (K-(i+1)) // l
      now += total * e
    ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
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[i] -= 1

ans = float("-inf")
for i in range(N):
    cycle = []
    pos = i
    total = 0
    while True:
        pos = P[pos]
        cycle.append(C[pos])
        total += C[pos]
        if pos == i: break

    l = len(cycle)
    t = 0
    for j in range(l):
        t += cycle[j]
        if j + 1 > K: break
        now = t

        if total > 0:
            cnt = (K-j-1) // l
            now += total * cnt
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
from numba import njit
from sys import maxsize


@njit
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: Accepted

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

if K<=N:
  ans = -10**9
  for i in range(N):
    now,last = i,0
    for _ in range(K):
      last += C[P[now]]
      ans = max(ans,last)
      now=P[now]
  print(ans)
  exit()
ans = -10**9
for i in range(N):
  tmp,now,done = [0],i,set()
  for _ in range(N+1):
  #while now not in done:
    tmp.append(tmp[-1]+C[P[now]])
    if P[now] == i:
      break
    now = P[now]
  tmp = tmp[1:]
  cnt = len(tmp)
  m = max(tmp)
  ans = max(ans,m,tmp[-1]*(K//cnt-1)+m)
  if K%cnt != 0:
    ans = max(ans, tmp[-1]*(K//cnt)+max(tmp[:K%cnt]))
    #print(i,ans,tmp)
print(ans)

Submission status: Accepted

Solution code:

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


# 順列を各サイクルに分解する
used = [0] * N
ss = []
for i in range(N):
    if used[i]: continue
    cur = i
    s = []
    while used[cur] == 0:
        used[cur] = 1
        s.append(C[cur])
        cur = P[cur] - 1 # 0-index
    ss.append(s)

# 各サイクルごとに考える
res = -float("inf")
for vec in ss:
    M = len(vec)
    
    # サイクルを2周したものの累積和
    accum = [0] * (2*M+1)
    for i in range(M*2):
        accum[i+1] = accum[i] + vec[i%M]

    # amari[r] := 連続するr個の総和の最大値
    amari = [-float("inf")] * M
    for i in range(M):
        for j in range(M):
            amari[j] = max(amari[j], accum[i+j]-accum[i])

    # あまりの長さで場合分け
    for r in range(M):
        if r > K: continue
        q = (K - r) // M # ループ回数
        if r == 0 and q == 0: continue

        if accum[M] > 0:
            res = max(res, amari[r] + accum[M] * q)
        elif r > 0:
            res = max(res, amari[r])

print(res)

Submission status: Accepted

Solution code:
from numba import jit
@jit
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: #ループ部分. iに戻る直前まで続ける.
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    # この時点でvalは1ループのスコア合計, カウントは1ループのsizeになっている
    '''
    以下の基本的な方針は
    - 1ループ分のスコア合計が正であればできるだけループしてスコアを稼ぎ、残りの余りの分の最大をとる。
    - 1ループ分のスコア合計が負であればループ回数を0にして、1ループ以内で最大となる移動を求める。
    しかし、ループ回数が最大であればいいとは限らない。
    x回ループできたとしてcount%k回の余りの分を調べても、x-1回ループし次の1回のループのなかで1周仕切らない移動が最大になる可能性がある。
    なのでx-1回分のループだけ取り切ってしまい、残りcount+k%count(＝「1周半」)の中で最大を調べる必要がある。
    また、負の場合は基本的に1周以内だが、kが極端に小さいときの処理が必要。
    '''
    if val>0:
      a=(k//count-1)*val  # 最後に余りのk%count回ぶんだけでなく1周半ぶんは試したいので(ループ余りではk%count回しか移動できないわけではない)
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)  # 1周以内におさめたい. k<countという非常に限られた場合のみk回までの移動になることを考慮。
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()

Submission status: Accepted

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

maxscore = -(10 ** 18)

for st in range(N):
	cumsum = [0]
	now = st
	while(P[now] != st):
		now = P[now]
		cumsum.append(cumsum[-1] + C[now])
	cumsum.append(cumsum[-1] + C[st])
	
	m = len(cumsum) - 1
	loopsum = cumsum[-1]
	
	if loopsum < 0:
		maxscore = max(maxscore, max(cumsum[1:min(K + 1, m + 1)]))
		continue
	
	score = (K // m - 1) * loopsum
	extended_cumsum = cumsum + [cumsum[i] + loopsum for i in range(1, K % m + 1)]
	score += max(extended_cumsum)
	maxscore = max(maxscore, score)
print(maxscore)

Submission status: Accepted

Solution code:
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[i] -= 1

ans = float("-inf")

for i in range(N):
    #iはスタートポジション
    pos = i
    #移動先のマスにかかれたポイント
    point = []
    total = 0
    while True:
        pos = p[pos]
        point.append(c[pos])
        # totalは周期の和がマイナスかプラスかで後々場合分けするために使う。(周期が負だったら一巡目で終わらせたい。周期が正だったらできる限り後の方で終わらせたい)
        total += c[pos]
        #スタートポジションに戻ってきた==サイクルを検知した
        if pos == i: break
    l = len(point)

    t = 0
    #total<0のときはif total>0以外の処理でまきとれる
    for i in range(l):
        t += point[i]
        #Kがi+1より小さい時のハンドリング
        if i+1 > K: break
        now = t
        if total > 0:
            #K-i-1の-1はポイントの一個目を獲得する時に1個動くので-1。二こ目のポイントを取る時はi=1で、K-2になり計算が合う。それをlでわり周期が何個回れるかを計算する
            #nowはtotalのセットが何個かあって、その先にpoint[i]がくっつくイメージ。[a,b,c] + [a,b,c] + [a,b,c] + ([a] or [a+b] + [a+b+c]) 
            #最初now += total * (K-i-1)//lとしていてWAしていたので書き方注意。これだとtotalと(K-i-1)をかけたものをlでわる、となってしまう。
            cnt = (K-i-1) // l
            now += total * cnt 
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
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[i] -= 1

ans = float("-inf")

for i in range(N):
    #iはスタートポジション
    pos = i
    #移動先のマスにかかれたポイント
    point = []
    total = 0
    while True:
        pos = p[pos]
        point.append(c[pos])
        # totalは周期の和がマイナスかプラスかで後々場合分けするために使う。(周期が負だったら一巡目で終わらせたい。周期が正だったらできる限り後の方で終わらせたい)
        total += c[pos]
        #スタートポジションに戻ってきた==サイクルを検知した
        if pos == i: break
    l = len(point)

    t = 0
    #total<0のときはif total>0以外の処理でまきとれる
    for i in range(l):
        t += point[i]
        #Kがi+1より小さい時のハンドリング
        if i+1 > K: break
        now = t
        if total > 0:
            #K-i-1の-1はポイントの一個目を獲得する時に1個動くので-1。二こ目のポイントを取る時はi=1で、K-2になり計算が合う。それをlでわり周期が何個回れるかを計算する
            #nowはtotalのセットが何個かあって、その先にpoint[i]がくっつくイメージ。[a,b,c] + [a,b,c] + [a,b,c] + ([a] or [a+b] + [a+b+c]) 
            cnt = (K-i-1) // l
            now += total * cnt 
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
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[i] -= 1

ans = float("-inf")

for i in range(N):
    #iはスタートポジション
    pos = i
    #移動先のマスにかかれたポイント
    point = []
    total = 0
    while True:
        pos = p[pos]
        point.append(c[pos])
        # totalは周期の和がマイナスかプラスかで後々場合分けするために使う。(周期が負だったら一巡目で終わらせたい。周期が正だったらできる限り後の方で終わらせたい)
        total += c[pos]
        #スタートポジションに戻ってきた==サイクルを検知した
        if pos == i: break
    l = len(point)

    t = 0
    #total<0のときはif total>0以外の処理でまきとれる
    for i in range(l):
        t += point[i]
        #Kがi+1より小さい時のハンドリング
        if i+1 > K: break
        now = t
        if total > 0:
            #K-i-1の-1はポイントの一個目を獲得する時に1個動くので-1。二こ目のポイントを取る時はi=1で、K-2になり計算が合う。それをlでわり周期が何個回れるかを計算する
            #nowはtotalのセットが何個かあって、その先にpoint[i]がくっつくイメージ。[a,b,c] + [a,b,c] + [a,b,c] + ([a] or [a+b] + [a+b+c]) 
            now += (total * ((K-i-1)//l))
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,K = LI()
P = LI()
C = LI()

P = list(map(lambda x:x-1,P))

res = -INF
used = [False] * N
ss = []

for i in range(N):
    # print('i',i)
    if used[i]:
        continue
    cur = i
    s = []
    while not used[cur]:
        used[cur] = True
        s.append(C[cur])
        cur = P[cur]
        # print(cur)
    ss.append(s)

# print(ss)

for vec in ss:
    M = len(vec)
    # 2周の累積和
    sum = [0]*(2*M + 1)
    for i in range(2*M):
        sum[i+1] = sum[i]+vec[i%M]
    
    # amari[r] := 連続するr個の最大値
    amari = [-INF]*M
    for i in range(M):
        for j in range(M):
            amari[j] = max(amari[j],sum[i+j] - sum[i])
    
    for r in range(M):
        if r>K:
            continue
        q = (K-r)//M
        if r==0 and q==0:
            continue
        if sum[M]>0:
            res = max(res, amari[r] + sum[M] * q)
        elif r > 0:
            res = max(res, amari[r])
print(res)

Submission status: Accepted

Solution code:
#ABC175-D
"""
1周未満で終わる時の最大値をまずもとめる
(i)k<一周なら
最大値を出力して終了
(ii)sum(lst) <= 0
1周以上する価値はないので、最大値を出力して終了
(iii)sum(lst) > 0
N%kの端数だけ愚直にもう一度最大値を求めて出力
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

ans = -10**18

for i in range(n):
    lst1 = [c[i]]
    idx = p[i]
    while idx != i:
        lst1.append(c[idx])
        idx = p[idx]
    sm = sum(lst1)
    acc = 0
    for i in range(min(len(lst1),k+2)):
        acc += lst1[i]
        a = acc
        if sm > 0:
            a += sm*((k-(i+1))//len(lst1))
        ans = max(a,ans)
print(ans)

Submission status: Accepted

Solution code:
from numba import jit
@jit
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: Accepted

Solution code:
N, K = map(int, input().split())
moves = [0] + list(map(int, input().split()))
points = [0] + list(map(int, input().split()))
INF = 10**10

arrived = [0 for _ in range(N+1)]
answer = -INF
for move in range(1, N+1):
  if arrived[move] == 1:
    continue
  else:
    arrived[move] = 1
    komas = [move]
    next = moves[move]
    while(arrived[next] == 0):
      arrived[next] = 1
      komas.append(next)
      next = moves[next]
    len_k = len(komas)
    sum_k = [0 for _ in range(len_k*2)]
    sum_k[0] = points[komas[0]]
    for i in range(1, len_k*2):
      sum_k[i] = sum_k[i-1] + points[komas[i%len_k]]
    scores = [-INF for _ in range(len_k+1)]
    for j in range(len_k):
      for k in range(1, len_k+1):
        scores[k] = max(scores[k], sum_k[j+k] - sum_k[j])
    if K > len_k and scores[len_k] > 0:
      max_s = -INF
      max_k = -INF
      for m in range(1, len_k+1):
        if m <= K%len_k:
          max_k = max(max_k, scores[m])
        max_s = max(max_s, scores[m])
      answer = max(answer, max_k+scores[len_k]*(K//len_k), max_s+scores[len_k]*(K//len_k-1))
    else:
      max_s = -INF
      for m in range(1, min(K, len_k)+1):
        max_s = max(max_s, scores[m])
      answer = max(answer, max_s)
print(answer)

Submission status: Accepted

Solution code:
"""
1. マス同士は有効グラフの一本道になっている。で、必ずどこかでループが発生している。

2. 各点から各点に移動する場合のスコアの合計とステップ数(ループ内の場合は一周以内のもの)を前処理(dfs)で求めておく。dp[i][j] => iからjまでのスコアとステップ数

3. K > N の場合、ループを通るとスコアがマイナスになるなら（dp[i][i]がマイナスになるようなiが存在するなら）、ループを一周しない方がよい。
ループを通るとスコアがプラスになるなら、

各iに対して地点iからスタートする場合というのをシミュレートすると実装が楽そう。
K <= Nの場合はi番目からスタートして、dfsでstep数がKに到達するまで進み続けて、スコアの最大値を図る。
Kが大きい場合は、dfsで道をたどっていってループを検出したら、その時点でループスコアがマイナスかプラスかを判断して、マイナスなら終了。
プラスならループスコア*(K//ループstep)を加算してできる限りKを減らす。そこからstep数がKに到達するまでdfsで道をたどっていって最大値を求める。
各スタート地点ごとにO(N)で処理可能なので、全体ではO(N^2)で処理できる
"""
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float("INF")

for i in range(1,N+1):
    scores = [None]*(N+1)
    steps = [None]*(N+1)
    cur = i
    score = 0
    step = 0
    loopFlag = False
    while step <= K:
        if scores[cur]!=None and not loopFlag:
            loopFlag = True
            loopScore = score - scores[cur]
            loopStep = step - steps[cur]
            ans = max(ans,score)
            restLoop = (K-step)//loopStep
            if restLoop > 0:
                restLoop -= 1
            score += restLoop*loopScore
            step += restLoop*loopStep
        scores[cur] = score
        steps[cur] = step
        if step != 0:
            ans = max(ans,score)
        p = P[cur-1]
        c = C[p-1]
        cur = p
        score += c
        step += 1

print(ans)

Submission status: Accepted

Solution code:
# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

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 = int(-1e14)
for i in range(n):
    tmp = []
    cycle = 0
    index = i
    while True:
        index = p[index]
        tmp.append(c[index])
        cycle += c[index]
        if i == index:
            break
    
    l = len(tmp)
    t = 0
    for j in range(l):
        t += tmp[j]
        if j >= k:
            break
        cur = t
        if cycle > 0:
            e = int((k-j-1) / l)
            cur += e * cycle
        ans = max(cur, ans)
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:],i8[:]), cache=True)
def main(N,K,P,C):
  INF = 1<<30
  ans = -INF
  for i in range(N):
    score = 0
    now = i
    visited = np.full(N,-1,np.int64)
    scores = np.zeros(N,np.int64)
    visited[now] = 0
    for j in range(1,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
      if visited[now]>=0:
        cyc = j - visited[now]
        up = score - scores[now]
        break
      scores[now] = score
      visited[now] = j
    else:
      continue
    if up<=0:
      continue
    cnt = j+1
    if K-cyc>=j:
      score += (K-cyc-j)//cyc * up
      ans = max(ans, score)
      cnt += (K-cyc-j)//cyc*cyc
    for j in range(cnt,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
  return ans

N, K = map(int, input().split())
P = np.array(list(map(lambda x:int(x)-1, input().split())))
C = np.array(list(map(int, input().split())))

print(main(N,K,P,C))

Submission status: Accepted

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

max_score = -(1 << 64)
cycles = []
cycled = [False] * n
for i in range(n):
    if cycled[i]:
        continue

    cycle = [i]
    cycled[i] = True
    while p_list[cycle[-1]] != cycle[0]:
        cycle.append(p_list[cycle[-1]])
        cycled[cycle[-1]] = True

    cycles.append(cycle)

for cycle in cycles:
    cycle_len = len(cycle)

    accum = [0]
    for i in range(cycle_len * 2):
        accum.append(accum[-1] + c_list[cycle[i % cycle_len]])

    cycle_score = accum[cycle_len]

    max_series_sums = [max([accum[i + length] - accum[i]
                            for i in range(cycle_len)])
                       for length in range(cycle_len + 1)]

    if cycle_len >= k:
        score = max(max_series_sums[1:k + 1])
    elif cycle_score <= 0:
        score = max(max_series_sums[1:])
    else:
        max_cycle_num, cycle_rem = divmod(k, cycle_len)
        score = max(cycle_score * (max_cycle_num - 1) + max(max_series_sums),
                    cycle_score * max_cycle_num + max(max_series_sums[:cycle_rem + 1]))

    max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

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

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, MAX)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    else:
        score = MAX

    ans = max(ans, score)


print(int(ans))

Submission status: Accepted

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


ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-i-1)//l
            now += tot*e
        ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
 
cycles, check = [], [False]*n
for pi in p:
    if not check[pi-1]:
        curr, cycle = pi, []
        check[pi-1] = True
        while pi != p[curr-1]:
            check[curr-1] = True
            cycle.append(c[curr-1])
            curr = p[curr-1]
        check[curr-1] = True
        cycles.append(cycle + [c[curr-1]])

scores = []
for cycle in (np.array(cycle) for cycle in cycles):
    for i in range(cycle.size):
        cum = np.roll(cycle, i).cumsum()
        if cum[-1] > 0 and k > cycle.size:
            scores.append(cum[-1]*(k//cycle.size-1) + np.concatenate([cum, cum[:k % cycle.size]+cum[-1]]).max())
        else:
            scores.append(cum[:min(k, cum.size)].max())

print(max(scores))

Submission status: Accepted

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

ans = -float('inf')
v = []
for n in range(N):
    loop, score = 0, 0
    t = n
    for i in range(min(N,K)):
        n = P[n] - 1
        score += C[n]
        ans = max(ans,score)
        if n == t:
            loop = i + 1
            break
    v.append((loop,score))
    
    
for n in range(N):
    loop,score = v[n]
    if loop > 0 and score > 0:
        r = (K-1)//loop
        nscore = r*score
        for i in range(K - r*loop):
            n = P[n] - 1
            nscore += C[n]
            ans = max(nscore, ans)
            
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
from numba import jit
@jit
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: Accepted

Solution code:
from numba import jit
@jit
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)
main()

Submission status: Accepted

Solution code:
from typing import List

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


def solve(N: int, K: int, P: List[int], C: List[int]):
    ans = max(C)
    visited = [False] * N
    for i in range(N):
        if visited[i]:
            continue

        cycle = []
        to = i
        while not visited[to]:
            visited[to] = True
            cycle.append(C[to])
            to = P[to] - 1

        ans = max(ans, partial_solve(len(cycle), K, cycle))

    return ans


def partial_solve(N: int, K: int, A: List[int]):
    ret = max(A)
    B = [0] * (3 * N + 1)
    for i in range(1, 3 * N + 1):
        B[i] = B[i - 1] + A[(i - 1) % N]

    if N > K:
        for l in range(1, N + 1):
            for r in range(l, l + K):
                ret = max(ret, B[r] - B[l - 1])

    else:
        if B[N] < 0:
            K = N
            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])
        else:
            cnt = K // N - 1

            K = K % N + N

            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])

            ret += cnt * B[N]

    return ret

print(solve(N, K, P, C))

Submission status: Accepted

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:
        tmp = np.arange(cnt)
        return (score_list[tmp] + ((k-1-tmp)//cnt) * score).max()
    else:
        return score_list[:cnt].max()

ans = max(calc_score(i,p,c) for i in range(n))
print(ans)

Submission status: Accepted

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, min(K + 1, len(loop) + 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)