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

# ループを見つける(5000), 一周のスコアを確認
is_visit = [0 for _ in range(n)]
loop = []

def search(i, j):
    if is_visit[i] == 0:
        is_visit[i] = j
        l.append(i)
        search(p[i]-1, j)

loop_id = 1
for i in range(n):
    l = []
    search(i, loop_id)
    if len(l) != 0:
        loop.append(l)
        loop_id += 1
# print(loop)
# print(is_visit)

ans = [0 for _ in range(n)]
for i in range(n):
    # i からはじめて最大スコア
    l = loop[is_visit[i]-1] # 所属するループ
    tmp1 = 0 # ループによるスコア
    tmp_k = k
    s = 0
    for j in range(len(l)):
        s += c[l[j]]
    if s > 0 and k > len(l):
        # 回るほどお得
        tmp1 += s*(tmp_k//len(l))
        tmp_k -= tmp_k//len(l)*len(l)
    else:
        tmp_k -= tmp_k//len(l)*len(l)
        if tmp_k == 0:
            tmp_k = len(l)
    pointer = p[i]
    tmp2 = [c[pointer-1] for _ in range(tmp_k)] # 愚直に進んだ点数
    if tmp_k != 0:
        for j in range(1, tmp_k):
            # k回目までの累積和で最大を求める
            pointer = p[pointer-1]
            tmp2[j] = tmp2[j-1] + c[pointer-1]
    # print(i, l, s, tmp_k, tmp1, tmp2)
    ans[i] = tmp1 + max(tmp2)
# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    c_sum = [0]
    s = set()
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k <= cnt:
        ans = max(ans, max(c_sum[1: min(k + 1, len(c_sum))]))
    else:
        temp = c_sum[-1]
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += max(c_sum[1:q + 1])
        ans = max(ans, temp, max(c_sum[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()))
ans = -1000000000
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  print(S, l)
  if cost > 0:
    ans = max(ans, cost * (K // l) + max(S[:K % l]))
  else:
    ans = max(ans, max(S))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#from itertools import accumulate
#from itertools import combinations
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

visited = [False]*(N+1)
loops = []
for v in range(1,N+1):
    if visited[v]:
        continue
    l = [v]
    while True:
        v = l[-1]
        visited[v] = True
        nv = P[v-1]
        if visited[nv]:
            break
        l.append(nv)
    loops.append(l)

cand = []
for loop in loops:
    temp = 0
    vals = [C[i-1] for i in loop]
    l = len(vals)
    vals2 = vals+vals[:-1]
    cumsum = [0]
    for v in vals2:
        cumsum.append(cumsum[-1] + v)
    #cumsum = [0] + list(accumulate(vals2))
    gh = []
    #print(vals)
    if K <= l:
        for left in range(0,2*l-K):
            for right in range(left+1,left+K+1):
                gh.append(cumsum[right] - cumsum[left])
        temp = max(gh)
    else:
        s = sum(vals)
        q, r = divmod(K,l)
        for left in range(0,2*l-r):
            for right in range(left+1,left+r+1):
                gh.append(cumsum[right] - cumsum[left])
        temp = max(gh)
        if s > 0:
            temp += q * s
    #print(temp)
    cand.append(temp)
print(max(cand))

Submission status: Runtime Error

Solution code:
N, K = [int(n) for n in input().split(" ")]
Ps = [int(n) for n in input().split(" ")]
Cs = [int(n) for n in input().split(" ")]

"""
N = 10
K = 58
Ps = [9, 1, 6, 7, 8, 4, 3, 2, 10, 5]
Cs = [695279662, 988782657, -119067776, 382975538, -151885171, -177220596, -169777795, 37619092, 389386780, 980092719]
"""
"""
N = 3
K = 3
Ps = [3, 1, 2]
Cs = [-1000,-2000,-3000]
"""

circles = []
already = []
for p in range(N):
    if p not in already:
        tmp = []
        nowp = p
        while nowp not in tmp:
            tmp.append(nowp)
            nowp = Ps[nowp] - 1
        circles.append(tmp)
        for a in tmp:
            already.append(a)

#print(circles)

finalResult = -100000000000

def getCircleScore(circle, start, kk):
    #print(circle, start, kk)
    s = 0
    for k in range(kk):
        index = start + k
        if index >= len(circle):
            index = index % len(circle)
        s += Cs[circle[index]]
    return s

maxCircle = []
maxCircleScore = -10000000000
maxIndex = 0
for circle in circles:
    CircleSum = sum([Cs[n] for n in circle])
    if maxCircleScore <= CircleSum:
        maxCircleScore = CircleSum
        maxCircle = circle

for circle in [maxCircle]:
    
    CircleSum = sum([Cs[n] for n in circle])
    #print(circle, CircleSum)
    score = 0
    if CircleSum > 0:
        score = K // len(circle) * CircleSum

    K = K % len(circle)
    if K == 0:
        K = len(circle)

    maxScore = -100000000000
    for start in range(len(circle)):
        #print("start", start)
        for kk in range(1, K+1):
            s = getCircleScore(circle, start, kk)
            #print(s)
            if maxScore <= s:
                maxScore = s

    final = score + maxScore

    if final >= finalResult:
        finalResult = final

print(finalResult)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Cs = list(map(int, input().split()))
scores = list()
max_list = list()
for i in range(N):
    next = Ps[i] - 1
    scores = [Cs[next]]
    while next != i:
        next = Ps[next] - 1
        scores.append(Cs[next]+scores[-1])
    l = len(scores)
    if scores[-1] < 0 or l >= K:
        max_list.append(max(scores[:K]))
    else:
        a, b = divmod(K, l)
        max_list.append(a*scores[-1] + max(scores[:b]))
print(max(max_list))

Submission status: Runtime Error

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(n):
	K=k
	score=0
	pre_score=0
	visit=[0]*n
	now=i
	cnt=0
	while visit[now]==0:
		cnt+=1
		visit[now]=1
		now=p[now]-1
		pre_score+=c[now]
		if cnt!=1:
			score=max(score,pre_score)
		else:
			score=pre_score
		K-=1
		if K==0:
			break
	ans=max(score,ans)
	if K==0:
		print(2/0)
		continue
	loop=[0]
	NOW=now
	#NOWはループ元
	for j in range(n):
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if NOW==now:
			break
	pre_score+=max(loop[-1],0)*(K//(len(loop)-1))
	K%=(len(loop)-1)
	pre_score+=max(loop[:K+1])
	score=max(score,pre_score)
	ans=max(ans,score)
print(ans)

Submission status: Runtime Error

Solution code:
n,K=list(map(int,input().split()))
ps=list(map(int,input().split()))
cs=list(map(int,input().split()))


group=[-1]*n
cnt=0
for i in range(len(ps)):
    tmp=i
    check=0
    while True:
        if group[tmp]!=-1:
            break
        check=1
        group[tmp]=cnt
        tmp=ps[tmp]-1
    if check!=0:
        cnt+=1

anses=[]
for i in range(cnt):
    position=group.index(i)
    scores=[cs[position]]
    while ps[position]-1!=group.index(i):
        position=ps[position]-1
        scores.append(cs[position])
    maxes=[]
    length=len(scores)
    scores=scores+scores
    for j in range(1,length+1):
        tmp=[]
        for k in range(length):
            tmp.append(sum(scores[k:k+j]))
        maxes.append(max(tmp))
    if maxes[-1]>0:
        ans=0
        ans+=K//length*maxes[-1]
        remain=K-K//length*length
        ans+=max(maxes[:remain])
    else:
        if K>=length:
            ans=max(maxes)
        else:
            ans=max(maxes[:K])
    anses.append(ans)
print(max(anses))

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    c_sum = [0]
    s = set()
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k <= cnt:
        ans = max(ans, max(c_sum[1: k + 1]))
    else:
        temp = c_sum[-1]
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += max(c_sum[1:q + 1])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)

Submission status: Runtime Error

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

seen = [0] * N

ans = -10**20

for i in range(N):
    if not seen[i]:
        seen[i] = 1
        loop = [C[i]]
        while True:
            i = P[i]
            if seen[i]:
                break
            seen[i] = 1
            loop.append(C[i])
        L = len(loop)
        loop = [0] + list(accumulate(loop*2))
        if loop[L] <= 0:
            move = min(L, K)
            for i in range(L):
                for j in range(1, move+1):
                    ans = max(ans, loop[i + j] - loop[i])
        else:
            if K > L:
                div, mod = divmod(K, L)
                tmp = div * loop[L]
                move = min(mod, L)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
                tmp = (div - 1) * loop[L]
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
            else:
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])

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

# ループを見つける(5000), 一周のスコアを確認
is_visit = [0 for _ in range(n)]
loop = []

def search(i, j):
    if is_visit[i] == 0:
        is_visit[i] = j
        l.append(i)
        search(p[i]-1, j)

loop_id = 1
for i in range(n):
    l = []
    search(i, loop_id)
    if len(l) != 0:
        loop.append(l)
        loop_id += 1
# print(loop)
# print(is_visit)

ans = [0 for _ in range(n)]
for i in range(n):
    # i からはじめて最大スコア
    l = loop[is_visit[i]-1] # 所属するループ
    tmp1 = 0 # ループによるスコア
    tmp_k = k
    s = 0
    for j in range(len(l)):
        s += c[l[j]]
    if s > 0 and k > len(l):
        # 回るほどお得
        tmp1 += s*(tmp_k//len(l))
        tmp_k -= tmp_k//len(l)*len(l)
    else:
        tmp_k -= tmp_k//len(l)*len(l)
        if tmp_k == 0:
            tmp_k = len(l)
    pointer = p[i]
    tmp2 = [c[pointer-1] for _ in range(tmp_k)] # 愚直に進んだ点数
    if tmp_k != 0:
        for j in range(1, tmp_k):
            # k回目までの累積和で最大を求める
            pointer = p[pointer-1]
            tmp2[j] = tmp2[j-1] + c[pointer-1]
    # print(i, l, s, tmp_k, tmp1, tmp2)
    if len(tmp2) != 0:
        ans[i] = tmp1 + max(tmp2)
    else:
        ans[i] = tmp1
# print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
n, k = [int(z) for z in input().strip().split()]
p = [int(z) - 1 for z in input().strip().split()]
c = [int(z) for z in input().strip().split()]

visited = [False for _ in range(n)]
cycle = []
for start in range(n):
    if visited[start]:
        continue
    now = start
    route = []
    while not visited[now]:
        visited[now] = True
        route.append(now)
        now = p[now]
    cycle.append(route)

min_c = min(c)
max_value = min_c
for route in cycle:
    full_value = sum([c[i] for i in route])
    double_route = route + route
    v = [c[i] for i in double_route]
    max_sum_step = []
    for step in range(1, len(route)):
        s = sum(v[:step])
        max_sum = max(s, min_c)
        for idx in range(step, step + len(route) - 1):
            s += v[idx]
            if idx >= step:
                s -= v[idx - step]
            max_sum = max(s, max_sum)
        max_sum_step.append(max_sum)
    addition = k % len(route)
    if full_value > 0:
        value1 = int(k / len(route)) * full_value + max(max_sum_step[:addition])
        value2 = (int(k / len(route)) - 1) * full_value + max(max_sum_step)
        value = max(value1, value2)
    else:
        value = max(max_sum_step[:min(k, len(max_sum_step))])
    max_value = max(max_value, value)
print(max_value)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    c_sum = [0]
    s = set()
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k <= cnt:
        ans = max(ans, max(c_sum[1: cnt + 1]))
    else:
        temp = c_sum[-1]
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += max(c_sum[1:q + 1])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)

Submission status: Runtime Error

Solution code:
N, K = [int(_) for _ in input().split()]
P = [int(_) - 1 for _ in input().split()]
C = [int(_) for _ in input().split()]
child_parent = [0] * N
ans = -float('inf')
for p, c in enumerate(P):
    child_parent[c] = p
for i in range(N):
    f = i
    i_cnt = [None] * N
    i_cnt[i] = 0
    cnt_score = [0]
    score = 0
    cnt = 0
    while True:
        i = P[i]
        cnt += 1
        score += C[i]
        cnt_score += [score]
        if cnt > K or i_cnt[i] is not None:
            break
        i_cnt[i] = cnt
    score1 = cnt_score[i_cnt[i]]
    cyclelen = cnt - i_cnt[i]
    if cyclelen:
        q, r = divmod((K - i_cnt[i]), cyclelen)
        ans1 = score1 + (score -
                         score1) * q + max([0] + cnt_score[i_cnt[i]:][:r + 1])
        ans2 = max([C[f]] + cnt_score[:i_cnt[i]])
        ans = max([ans, ans1, ans2])
    else:
        ans = max([ans] + cnt_score)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split())
P = np.array([*map(int, input().split())], dtype=int) - 1
C = np.array([*map(int, input().split())], dtype=int)

V = np.zeros(N, dtype=int)
V_max = np.zeros(K, dtype=int)
for i in range(K):
  V = C + V[P]
  V_max[i] = V.max()
print(V_max.max())

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

maxpoints=[]
points=[]

for i in range(n):
    gone=set([])
    now=i
    next=p[now]
    point=c[next]
    maxpoint=[point]
    gone.add(i)
    for j in range(min(k,n)):
        now=next
        next=p[now]
        if next in gone:
            point+=c[next]
            maxpoint.append(max(maxpoint[-1],point))
            maxpoints.append(maxpoint)
            points.append(point)
            break
        point+=c[next]
        maxpoint.append(max(maxpoint[-1],point))
#print(maxpoints)
#print(points)

ans=-float('inf')

for i in range(n):
    if k<=n:
        temp=maxpoints[i][k-1]
    elif points[i]<=0:
        temp=maxpoints[i][-1]
    else:
        times=k//len(maxpoints[i])
        odd=k%len(maxpoints[i])
        temp=points[i]*times+maxpoints[i][odd-1]
    ans=max(temp,ans)
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()))
ans = -1e9
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    ans = max(ans, cost * (K // l) + max(S[:K % l]))
  else:
    ans = max(ans, max(S))
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**12

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        while True:
            count+=1
            now=P[now]-1

            if now in st:
                count-=1
                break
    
            lst[i][count]=lst[i][count-1]+C[now]
            st.add(now)
            
            if count==K:
                break
        
        if lst[i][count]>0 and K>=count:
            if K%count:
                s=lst[i][count]*(K//count)+max(lst[i][1:K%count+1])
            else:
                s=lst[i][count]*(K//count)
        else:
            s=max(lst[i][1:count+1])
        output=max(output,s)

    print(lst)
    print(output)

main()

Submission status: Runtime Error

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,K = isRaw()
    Ps = isRaw()
    Cs = isRaw()
    ans = -INF
    for n in range(N):
        curPos = n
        cycles =[]
        visited = {}
        lastCost = 0
        vidx = 0
        loopStart = -1
        while True:
            visited[curPos] = vidx
            cycles.append(lastCost+Cs[curPos])
            curPos= Ps[curPos]-1
            lastCost = cycles[-1]
            if curPos in visited:
                loopStart = visited[curPos]
                break
        lc = len(cycles)
        divK = K//lc
        score = 0
        print(n,cycles)
        if cycles[-1]>0:
            score+=cycles[-1]*divK
        score += max(cycles[:K % lc] if K % lc != 0 else cycles)

        ans = max(score,ans)
    print (ans)

         
main()

Submission status: Runtime Error

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

seen = [0] * N

ans = -10**20

for i in range(N):
    if not seen[i]:
        seen[i] = 1
        loop = [C[i]]
        while True:
            i = P[i]
            if seen[i]:
                break
            seen[i] = 1
            loop.append(C[i])
        L = len(loop)
        loop = [0]+list(accumulate(loop*2))
        if loop[L] <= 0:
            move = min(L, K)
            for i in range(L):
                for j in range(1, move+1):
                    ans = max(ans, loop[i+j]-loop[i])
        else:
            if K > L:
                div, mod = divmod(K, L)
                tmp = div * loop[L]
                move = min(mod, K)
                for i in range(L):
                    for j in range(1, move+1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
                tmp = (div - 1) * loop[L]
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
            else:
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])

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

maxpoints=[]
points=[]

for i in range(n):
    gone=set([])
    now=i
    next=p[now]
    point=c[next]
    maxpoint=[point]
    gone.add(i)
    for j in range(max(k,n)):
        now=next
        next=p[now]
        if next in gone:
            point+=c[next]
            maxpoint.append(max(maxpoint[-1],point))
            maxpoints.append(maxpoint)
            points.append(point)
            break
        point+=c[next]
        maxpoint.append(max(maxpoint[-1],point))
#print(maxpoints)
#print(points)

ans=-float('inf')

for i in range(n):
    if k<=n:
        temp=maxpoints[i][k-1]
    elif points[i]<=0:
        temp=maxpoints[i][-1]
    else:
        times=k//len(maxpoints[i])
        odd=k%len(maxpoints[i])
        temp=points[i]*times+maxpoints[i][odd-1]
    ans=max(temp,ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from itertools import combinations
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

visited = [False]*(N+1)
loops = []
for v in range(1,N+1):
    if visited[v]:
        continue
    l = [v]
    while True:
        v = l[-1]
        visited[v] = True
        nv = P[v-1]
        if visited[nv]:
            break
        l.append(nv)
    loops.append(l)

cand = []
for loop in loops:
    temp = 0
    vals = [C[i-1] for i in loop]
    l = len(vals)
    vals2 = vals+vals[:-1]
    cumsum = [0] + list(accumulate(vals2))
    gh = []
    #print(vals)
    if K <= l:
        for right,left in combinations(range(2*l), 2):
            if left - right <= K:
                gh.append(cumsum[left] - cumsum[right])
        temp = max(gh)
        #print(vals2,cumsum,gh)
    else:
        s = sum(vals)

        q, r = divmod(K,l)
        for right,left in combinations(range(2*l), 2):
            if left - right <= r:
                gh.append(cumsum[left] - cumsum[right])
        temp = max(gh)
        if s > 0:
            temp += q * s
    #print(temp)
    cand.append(temp)
print(max(cand))

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
p = [0]*n
c = [0]*n
a = [0]*n
ans = [0]*n

p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i  in range(n):
    s = 0
    x = i
    roop =0
    for j in range(n):
        s += c[x]
        a[j] = s
        x= p[x]-1
        if x == i:
            roop = j+1
            break
    if s <0:
        ans[i] = max(a[:min(roop,n)])
    else:
        ans[i] = max(s*(k//roop)+max(a[:k%roop]),s*(k//roop-1)+max(a))
print(max(ans))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().rstrip().split(" "))
P = list(map(int,input().rstrip().split(" ")))
C = list(map(int,input().rstrip().split(" ")))
check = [False for _ in range(N)]
ans = -(10 ** 15)
for i in range(N):
    kans = 0
    score = [0]
    nex = P[i] -1
    while True:
        score.append(score[-1] + C[nex])
        nex = P[nex] - 1
        if nex == P[i] -1:
            break;
    if score[-1] > 0:
        kans = score[-1] * (K // (len(score) -1)) + max(score[1:K % (len(score) -1) + 1])
    else:
        kans = max(score[1:min(len(score) - 1,K) + 1])
    ans = max(ans,kans)
print(ans)

Submission status: Runtime Error

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

seen = [0] * N

ans = -10**20

for i in range(N):
    if not seen[i]:
        seen[i] = 1
        loop = [C[i]]
        while True:
            i = P[i]
            if seen[i]:
                break
            seen[i] = 1
            loop.append(C[i])
        L = len(loop)
        loop = list(accumulate(loop*2, initial=0))
        if loop[L] <= 0:
            move = min(L, K)
            for i in range(L):
                for j in range(1, move+1):
                    ans = max(ans, loop[i+j]-loop[i])
        else:
            if K > L:
                div, mod = divmod(K, L)
                tmp = div * loop[L]
                move = min(mod, K)
                for i in range(L):
                    for j in range(1, move+1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
                tmp = (div - 1) * loop[L]
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])
            else:
                move = min(L, K)
                for i in range(L):
                    for j in range(1, move + 1):
                        ans = max(ans, tmp + loop[i + j] - loop[i])

print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int n,k;cin>>n>>k;
  vector<int> p(n);
  vector<int> c(n);
  rep(i,n)cin>>p[i];
  rep(i,n)cin>>c[i];
  rep(i,n)p[i]-=1;
  lint res=-inf;
  vector<bool> memo(n,true);
  rep(i,n){
    if(memo[i]){
      vector<int> node;
      node.push_back(i);
      lint sm=c[i];
      lint nxt=p[i];
      memo[i]=false;
      while(nxt!=i){
        sm+=c[nxt];
        node.push_back(nxt);
        memo[nxt]=false;
        nxt=p[nxt];
      }
      lint buf=0;
      if(sm>0&&k>=node.size()){
        buf=sm*(k/node.size());
      }
      k%=node.size();
      int num=node.size();
      lint hoge=-inf;
      rep(j,num){
        lint add=0;
        lint mx=-inf;
        int cur=node[j];
        if(buf==0){
          if(sm!=0){
            mx=c[p[cur]];
          }
          else mx=0;
        }
        rep(xx,k){
          add+=c[p[cur]];
          cur=p[cur];
          mx=max(add,mx);
        }
        hoge=max(hoge,mx);
      }
      buf+=hoge;
      res=max(res,buf);
    }
  }
  cout<<res<<"\n";
  return 0;
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
CC = [[] for _ in range(n)]
p = P[0]

for idx, p in enumerate(P):
    CC[idx].append(C[p])
    pp = P[p]
    for i in range(n):
        if pp == p:
            break
        CC[idx].append(C[pp])
        pp = P[pp]
        

from itertools import accumulate
ans = -50**15
for cc in CC:
    cca = list(accumulate(cc))
    sc = sum(cc)
    if sc <= 0:
        # 1周分のmax
        ans = max(ans, max(cca))
    else:
        kk, r = divmod(k, len(cc))
        ans = max(ans, kk * sc + max(cca[:r]))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    k = kwargs["k"]
    P = kwargs["P"]
    C = kwargs["C"]
    res = -INF
    tmp = [0 for i in range(n)]
    for i in range(min(k, 10 ** 6)):
        n_tmp = [0 for i in range(n)]
        for j in range(n):
            n_tmp[j] = tmp[P[j]-1] + C[j]
        tmp = n_tmp
        print(tmp)
        res = max(res, max(tmp))

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"], kwargs["k"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["P"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["C"] = [int(i) for i in cin]

    cout = main(kwargs)
    print(cout)