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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(3000)
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 11
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in nei:
      points = [0]
      count = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(nei)
      s_l.append(points)
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      points = s_l[loop]
    #print(points)
    #print(count)
    loop_num = dic[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point and a != 0:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    #print(point)
    if b > 0:
      t_max = -10 ** 11
      if loop_num - count + 1 >= b:
        for j in range(b):
          t = points[j + count] - s
          #print(t)
          if t > t_max:
            t_max = t
      else:
        for j in range(count, loop_num + 1):
          t = points[j] - s
          #print(t)
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + count):
          t = points[j] + m
          #print(t)
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in nei:
      points = [0]
      count = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      points = s_l[loop]
    loop_num = dic[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    if b > 0:
      t_max = -10 ** 10
      if loop_num - count + 1 >= b:
        for j in range(b):
          t = points[j + count] - s
          if t > t_max:
            t_max = t
      else:
        for j in range(count, loop_num + 1):
          t = points[j] - s
          if t > t_max:
            t_max = t
        if b != loop_num and count != 1:
          for j in range(1, b - loop_num + count):
            t = points[j] + m
            if t > t_max:
              t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Submission status: Runtime Error

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

g = [ [] for _ in range(N) ]
for i in range(N):
  g[i].append(P[i])

def dfs(i):
  global cycle
  nei = g[i][0]
  if nei in cycle: return
  cycle.append(nei)
  dfs(nei)

cycles = []

for i in range(N):
  cycle = []
  dfs(i)
  c = [ C[j] for j in cycle ]
  cycles.append(c) 

ans = -float('inf')
for i in range(N):
  c = cycles[i]
  cum = c[::]
  for j in range(1,len(c)):
    cum[j] = cum[j-1] + cum[j]

  if cum[-1] < 0:
    ans = max(ans, max(cum[0:K]))
  else:
    t = K//len(c)
    r = K - t*len(c)
    cum = [0]+cum[::]
    ans = max(ans, cum[-1]*t+max(cum[:r+1]))

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    p[i] -= 1
ans = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    for i in range(l):
        now += s[i]
        if i + 1 > k:
            break
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
            ans = max(ans, now)
            pass
        else:
            pass

Submission status: Runtime Error

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    pos = n
    ans = []

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans.append(tmp)
    
    pos =
    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans.append(tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)

    return max(ans)

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

ans = -1e20
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)


def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        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)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        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)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
TO = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(TO)
# print(C)

vis = [False]*(n+1)
def dfs(i, t):
    if vis[i]: return t
    vis[i] = True
    t.append(i)
    return dfs(TO[i], t)

INF = 1*((10**9)*5000 + 1)
score = -INF
for f in range(n):
    T = dfs(f, [])
    len_t = len(T)
    if len_t == 0: continue
    costs = [0] * (len_t)
    for i in range(len_t): costs[i] = C[T[i]]
    loops = k // len_t
    cost = sum(costs)
    # print(len_t, T, 'costs',costs, cost, loops)
    # if cost >= 0:
    #     k -= loops * len_t
    #     cost = cost * loops

    if cost >= 0:
        k -= loops * len_t
    else:
        pass

    peak_cost = -INF
    for i in range(len_t):
        sum_cost = 0
        for j in range(k):
            sum_cost += costs[(i+j)%len_t]
            peak_cost = max(peak_cost, sum_cost)
    # print(k,'peak_cost',peak_cost, cost)
    cost = max({cost, cost + peak_cost, cost*loops + peak_cost, peak_cost})
    # print('cost',cost)
    score = max(score, cost)
print(score)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
TO = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

# print(n,k)
# print(TO)
# print(C)

vis = [False]*(n+1)
def dfs(i, t):
    if vis[i]: return t
    vis[i] = True
    t.append(i)
    return dfs(TO[i], t)

INF = 1*((10**9)*5000 + 1)
score = -INF
for f in range(n):
    T = dfs(f, [])
    len_t = len(T)
    if len_t == 0: continue
    costs = [0] * (len_t)
    for i in range(len_t): costs[i] = C[T[i]]
    loops = k // len_t
    cost = sum(costs)
    # print(len_t, T, 'costs',costs, cost, loops)
    if cost >= 0:
        k -= loops * len_t
        cost = cost * loops

    peak_cost = -INF
    for i in range(len_t):
        sum_cost = 0
        for j in range(k):
            sum_cost += costs[(i+j)%len_t]
            peak_cost = max(peak_cost, sum_cost)
    # print(k,'peak_cost',peak_cost, cost)
    cost = max({cost, cost + peak_cost, peak_cost})
    # print('cost',cost)
    score = max(score, cost)
print(score)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
c = list(map(int, input().split()))
c = [0] + c
score = [[0] * (n + 1) for _ in range(n + 1)]
# score[i][j]: iからstartしてj回移動した時のスコア
l_cycle = [0] * (n + 1)
for i in range(1, n + 1):
    start = i
    move_cnt = 0
    nxt = i
    while move_cnt < n:
        nxt = p[nxt]
        score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
        move_cnt += 1
        if nxt == start:
            l_cycle[start] = move_cnt
            break
# for i in range(1, n + 1):
#     print(score[i])
# print('l_cycle', l_cycle)
ans = -float('inf')
for s in range(1, n + 1):
    if k <= l_cycle[s]:
        # サイクルを回らないので
        temp = max(score[s][1:k + 1])
        ans = max(ans, temp)
        continue
    # 以降は一周以上出来る時

    # 一周以下でやめる場合を探索
    temp = max(score[s][1:l_cycle[s] + 1])
    ans = max(ans, temp)
    if score[s][l_cycle[s]] <= 0:
        # 周回する意味がない
        continue
    sk = k // l_cycle[s]  # 何周出来るか
    remk = k % l_cycle[s]
    temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
    temp += max(score[s][1:remk + 1])
    ans = max(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [0] + p
c = list(map(int, input().split()))
c = [0] + c
score = [[0] * (n + 1) for _ in range(n + 1)]
# score[i][j]: iからstartしてj回移動した時のスコア
l_cycle = [0] * (n + 1)
for i in range(1, n + 1):
    start = i
    move_cnt = 0
    nxt = i
    while move_cnt < n:
        nxt = p[nxt]
        score[i][move_cnt + 1] += score[i][move_cnt] + c[nxt]
        move_cnt += 1
        if nxt == start:
            l_cycle[start] = move_cnt
            break
# for i in range(1, n + 1):
#     print(score[i])
# print('l_cycle', l_cycle)
ans = -float('inf')
for s in range(1, n + 1):
    if k <= l_cycle[s]:
        # サイクルを回らないので
        temp = max(score[s][1:k + 1])
        ans = max(ans, temp)
        continue
    # 以降は一周以上出来る時

    # 一周以下でやめる場合を探索
    temp = max(score[s][1:l_cycle[s] + 1])
    ans = max(ans, temp)
    if score[s][l_cycle[s]] <= 0:
        # 周回する意味がない
        continue
    sk = k // l_cycle[s]  # 何周出来るか
    remk = k % l_cycle[s]
    temp = sk * score[s][l_cycle[s]]  # 周回によるスコア
    temp += max(score[s][1:remk + 1])
    ans = max(ans, temp)

print(ans)

Submission status: Runtime Error

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

# Pが1,2,...Nの順列なので、1,2,3,4,5,3,4,5,...のような途中からのループは起こり得ない
# スタートの点数が入らないのは面倒なので、スタートの次のマスから考える

ans = -(10**9)
# どのマスから始めるか
for i in range(1, N + 1):
    # ループに入るまでの経路(iの次から)
    route = []
    visit = [False] * (N + 1)
    visit[i] = True
    now = i
    while True:
        next = P[now]
        # まだ訪れていないマスの場合
        if visit[next] == False:
            visit[next] = True
            route.append(next)
            now = next
        # 既に訪れたマスの場合
        else:
            break
    # iに戻ってくる
    route.append(i)

    cumsum = [0]
    for x in route:
        cumsum.append(cumsum[-1] + C[x])
    # print(cumsum)

    # ループするほど損する場合
    if cumsum[-1] <= 0:
        tmp = max(cumsum[1:])
        ans = max(ans, tmp)
    # ループするほど得する場合
    else:
        loop_size = len(route)
        loop_cnt = K // loop_size
        spare_cnt = K % loop_size
        tmp = cumsum[-1] * loop_cnt + max(cumsum[1:spare_cnt + 1])
        ans = max(ans,tmp)

print(ans)

Submission status: Runtime Error

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

# 順列のループを見つける → 各ループの最大値(周回できる? or 周回できない?)
used = []
sets = []
nowP = []
j = 0

for i in range(len(P)) : # ~5000
    start_position = i
    j = start_position
    sets_buf = []
    while True : # ~ 5000
        if P[j] in used :
            break
        used.append(P[j])
        sets_buf.append(P[j])
        j = P[j] - 1
    if len(sets_buf) >= 1 :
        sets.append(sets_buf)

score = []
for i in range(len(sets)) : # i番目の集合
    now_set = sets[i]
    buf = [] # 現在のループネットワークにおけるスコアを格納
    for j in range(len(now_set)) : # ~5000 i番目の集合の中のj要素目をnow_setのスタートとする
        P_usiro = now_set[:j]
        per_now_set = now_set[j:]
        per_now_set.extend(P_usiro) # now_setのj番目(0~len(now_set))をスタートとするlen(now_set)の順列の配列生成
        now_C = [C[k-1] for k in per_now_set] # 現在のjからの得点配列
        value_buf = [0]

        if (len(now_set) < K) and sum(now_C) >= 0 : # 例外
            for k in range(K % len(now_set)) : # 余りの分の中における最大を探す ~?
                value_buf.append(value_buf[k]+now_C[k])
            del value_buf[0]
            buf.append((K // len(now_set)) * sum(now_C) + max(value_buf))
            continue

        if (len(now_set) < K) :
            for k in range(len(now_set)) :
                value_buf.append(value_buf[k]+now_C[k])
            del value_buf[0]
            buf.append(max(value_buf))
        else :
            for k in range(K) :
                value_buf.append(value_buf[k]+now_C[k])
            del value_buf[0]
            buf.append(max(value_buf))
    score.append(max(buf))

print(max(score))

Submission status: Runtime Error

Solution code:
def read_input():

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

    return n, k, p, c

def solve_i(i, k, p, c, n):
    
    points = 0
    maxi = float('-Inf')

    s = i
    i = p[i]
    t = 0
    while i != s and t < k:
        
        points += c[i]
        i = p[i]
        t += 1
        maxi = max(maxi, points)

    points += c[i]
    maxi = max(maxi, points)

    if k == t or points <= 0:
        return maxi
    else:
        cycles = k // t
        remainder = k % t

        potential = points * cycles
        if remainder != 0:
            tmp_max = float('-Inf')
            i = s
            tmp_points = 0
            for _ in range(remainder):
                tmp_points += c[i]
                i = p[i]
                tmp_max = max(tmp_max, tmp_points)
            potential += max(tmp_points)

        return max(maxi, potential)

def solve(n, k, p, c):

    maxi = float('-Inf')
    for i in range(n):
        maxi = max(maxi, solve_i(i, k, p, c, n))

    return maxi


print(solve(*read_input()))

Submission status: Runtime Error

Solution code:
import itertools as it

def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    # 累積和
    scores = it.accumulate([0]+[C[i] for i in cycle])
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    # 1cycle以下の場合は全て調べればよし
    if K <= len(cycle):
        max_score = max(scores[1:K+1])
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがマイナスならサイクルを回らないのがハイスコア
    if score_per_cycle <= 0:
        max_score = max(scores[1:])
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがプラスなら限界までサイクルを回るのがハイスコア
    # ラスト1cycleのスコアを調べる
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        # 何周したか
        loop_cnt = move // cycle_len
        # あまり
        rest_move = move % cycle_len
        # スコア = 1周ごとのスコア * 何周したか + あまり
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
pn = list(map(int,input().split()))
cn = list(map(int,input().split()))
ans = -float("inf")


for i in range(n): 
    start=i
    now=start
    total = 0 #ループ計
    ls = [0]

    for j in range(1, k+1):
        now = pn[now]-1
        total += cn[now]
        ans = max(ans, total)
        ls.append(total)
        if now == start:
            rp = j
            break
    else:
        continue  #roopなし

    if total <= 0:
        continue
    else:
        if k % rp == 0:
            ans2 = total * (k // rp-1) + max(ls)
            ans = max(ans, ans2)
        else:

            ans2 = total * (k//rp) + max(ls[:s+1])
            ans = max(ans, ans2)
print(ans)

Submission status: Runtime Error

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

sumlist1 = [[0]*N for _ in range(N)]
walist = [[0]*N for _ in range(N)]
loopcount = [0]*N

for h in range(N):
    sumlist1[h][0] = C[h]
    walist[h][0] = C[h]
    now = h
    l = 0
    for i in range(1,N):
        now = P[now]-1

        if sumlist1[h][i-1] < 0:
            sumlist1[h][i] = C[now]
        else:
            sumlist1[h][i] += sumlist1[h][i-1] + C[now]
        walist[h][i] += walist[h][i-1] + C[now]
        
        l += 1
        if now == h:
            break
    else:
        l += 1
    loopcount[h] = l
#print(sumlist1)

maxlist = [0]*N
for i in range(N):
    T = loopcount[i]
    wa = walist[i][T-1]
    #print(wa)

    loop = K//T
    amari = K%T

    if wa >= 0:
        if loop == 0:
            if amari != 0:
                maxlist[i] = wa*loop + max(sumlist1[i][:amari])
            else:
                maxlist[i] = wa*loop
        else:
            if amari != 0:
                maxlist[i] = max(wa*loop + max(sumlist1[i][:amari], wa*(loop-1) + max(sumlist1[i])))
            else:
                maxlist[i] = max(wa*loop, wa*(loop-1) + max(sumlist1[i]))
            

    else:
        if loop == 0:
            maxlist[i] = max(sumlist1[i][:amari])
        else:
            maxlist[i] = max(sumlist1[i])

print(max(maxlist))
#print(sumlist1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

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

seen = [False]*n
ans = -float('inf')
for i in range(n):
    if not seen[i]:
        sc = []
        stop = i
        while True:
            seen[i] = True
            sc.append(c[i])
            if p[i] == stop:
                break
            i = p[i]

        lens = len(sc)
        for j in range(lens):
            if j != 0:
                sc = sc[1:] + [sc[0]]
            ac = list(accumulate(sc))

            if sum(sc) <= 0:
                ans = max(ans, max(ac[:min(k, lens)]))
            else:
                if k%lens == 0:
                    ans = max(ans, ac[-1]*(k//lens-1) + max(ac))
                else:
                    ans = max(ans, ac[-1]*(k//lenc) + max(ac[:k%lenc]+[0]))
print(ans)

Submission status: Runtime Error

Solution code:
def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

def get_cycle_scores(cycle):
    score = 0
    scores = [score]
    for i in cycle:
        score += C[i]
        scores.append(score)
    return scores

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    scores = get_cycle_scores(cycle)
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    # 1cycle以下の場合は全て調べればよし
    # または、1サイクルごとのスコアがマイナスならサイクルを回らないのがハイスコア
    if K <= len(cycle) or score_per_cycle <= 0:
        max_score = max(scores[move] for move in range(1, K+1))
        max_scores.append(max_score)
        continue
    # 1サイクルごとのスコアがプラスなら限界までサイクルを回るのがハイスコア
    # ラスト1cycleのスコアを調べる
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        # 何周したか
        loop_cnt = move // cycle_len
        # あまり
        rest_move = move % cycle_len
        # スコア = 1周ごとのスコア * 何周したか + あまり
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))

Submission status: Runtime Error

Solution code:
def li():
    return [int(x) for x in input().split()]

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

def get_cycle_scores(cycle):
    score = 0
    scores = [score]
    for i in cycle:
        score += C[i]
        scores.append(score)
    return scores

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    scores = get_cycle_scores(cycle)
    # 1cycle以下の場合は全て調べればよし
    if K <= len(cycle):
        max_score = max(scores[move] for move in range(1, K+1))
        max_scores.append(max_score)
        continue
    # 1サイクルの長さ
    cycle_len = len(cycle)
    # 1サイクルごとのスコア
    score_per_cycle = scores[cycle_len]
    # 1サイクルごとのスコアがマイナスならサイクルを回らないのがハイスコア
    if score_per_cycle < 0:
        continue
    # 1サイクルごとのスコアがプラスなら限界までサイクルを回るのがハイスコア
    # ラスト1サイクルのスコア
    scores_last_cycle = []
    # 最後の1cycleの値を調べる
    for move in range(K-cycle_len+1, K+1):
        # 何周したか
        loop_cnt = move // cycle_len
        # あまり
        rest_move = move % cycle_len
        # スコア = 1周ごとのスコア * 何周したか + あまり
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 100


def run():
    N, K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    C = list(map(int, sysread().split()))
    P = [p-1 for p in P]

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    #print(loops)
    #print(loopSums)
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] <= 0 or len(loop)-1 > K:
                j = i
                max_val = -INF
                iter = 0
                done = False
                while iter <= K:
                    if j >= len(loop):j=0
                    if (i != j and j) or done:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    if not j ==1:
                        iter += 1
                    if done : break
                    if i == j: done = True
                ans = max(ans, max_val)
                continue


            rest = K
            #if K <= len(loop) - i - 1:
            #    val += loopSum[i + K - 1] - loopSum[i]
            #    ans = max(ans, val)
            #    continue
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            val += (rest // (len(loop)-1)) * loopSum[-1]
            rest = rest % (len(loop) - 1)
            if not rest:
                val += max(loopSum[1:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 100


def run():
    N, K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    C = list(map(int, sysread().split()))
    P = [p-1 for p in P]

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    #print(loops)
    #print(loopSums)
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] <= 0 or len(loop)-1 > K:
                j = i
                max_val = -INF
                iter = 0
                done = False
                while iter <= K:
                    if j >= len(loop):j=0
                    if (i != j and j) or done:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    if not j ==1:
                        iter += 1
                    if done : break
                    if i == j: done = True
                ans = max(ans, max_val)
                continue


            rest = K
            #if K <= len(loop) - i - 1:
            #    val += loopSum[i + K - 1] - loopSum[i]
            #    ans = max(ans, val)
            #    continue
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            val += (rest // (len(loop)-1)) * loopSum[-1]
            rest = rest % (len(loop) - 1)
            val += max(loopSum[1:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

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

sumlist1 = [[0]*N for _ in range(N)]
walist = [[0]*N for _ in range(N)]
loopcount = [0]*N

for h in range(N):
    sumlist1[h][0] = C[h]
    walist[h][0] = C[h]
    now = h
    l = 0
    for i in range(1,N):
        now = P[now]-1

        if sumlist1[h][i-1] < 0:
            sumlist1[h][i] = C[now]
        else:
            sumlist1[h][i] += sumlist1[h][i-1] + C[now]
        walist[h][i] += walist[h][i-1] + C[now]
        
        l += 1
        if now == h:
            break
    else:
        l += 1
    loopcount[h] = l
#print(sumlist1)

for i in range(N):
    T = loopcount[i]
    wa = walist[i][T-1]
    #print(wa)

    loop = K//T
    amari = K%T

maxlist = [0]*N
if wa >= 0:
    for i in range(N):
        maxlist[i] = max(sumlist1[i][:amari])
    print(wa*loop + max(maxlist))
else:
    for i in range(N):
        maxlist[i] = max(sumlist1[i])
    print(max(maxlist))