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()))
c = [1] * N
s = [C[P[i]-1] for i in range(N+1)]
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        s[i] += C[P[j]-1]
        if  c[i] <= K:
            if s[i] > m[i][c[i]-1]:
                m[i][c[i]] = s[i]
            else:
                m[i][c[i]] = m[i][c[i]-1]
ans = min(C)
for i in range(N):
    if s[i] > 0:
        if  s[i] * (K//c[i]) + m[i][K%c[i]] > ans:
            ans = s[i] * (K//c[i]) + m[i][K%c[i]]
    else:
        if max(m[i][1:min(c[i],K+1)]) > ans:
            ans = max(m[i][1:min(c[i],K+1)])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7


def solve(array):
    best_sum = float('-inf')
    best_start = best_end = -1
    current_sum = 0
    current_start = 0
    cnty = 0
    for current_end, num in enumerate(array):
        if current_sum <= 0:
            current_start = current_end
            current_sum = num
            cnty = 0
        else:
            current_sum += num
        if current_end-current_start+1 > K:
            current_start += 1
            current_sum -= array[cnty]
            cnty += 1
        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end

    return best_sum

N,K = I()
P = l()
C = l()
L = [[] for _ in range(N)]
a = [0]*N
cnt = 0
ans = 0
for j in range(N):
    if a[j] == 0:
        cnt += 1
        Pi = j+1
        for i in range(N):
            Pi = P[Pi-1]
            a[Pi-1] = 1
            L[cnt-1].append(C[Pi-1])
            if Pi == j+1:
                break
for i in range(N):
    if L[i]:
        L[i] = L[i]*(K//len(L[i])+3)
        ans = max(ans,solve(L[i]))
        if ans == 0 and i == 0:
            ans = solve(L[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()))

ume = [True] + [False] * N
loop = []
for i in range(1,N+1):
    if ume[i]:
        continue
    else:
        ll = [C[i-1]]
        ume[i] = True
        ne = P[i-1]
        while ume[ne] == False:
            ume[ne] = True
            ll.append(C[ne-1])
            ne = P[ne-1]
        loop.append(ll)
    if False not in ume:
        break

def maxSubArraySum(a,size): 
      
    max_so_far = 0
    max_ending_here = 0
      
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if max_ending_here < 0: 
            max_ending_here = 0
          
        # Do not compare for all elements. Compare only    
        # when  max_ending_here > 0 
        elif (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
              
    return max_so_far 

lP = []
for i in loop:
    t = sum(i)
    lP.append([t,len(i)])

ans = 0
cnt = -1
for i in lP:
    cnt += 1
    if i[0] > 0:
        tim = K // i[1]
        nok = K - tim * i[1] 
        wl = loop[cnt] + loop[cnt]
        tmp = tim * i[0] + maxSubArraySum(wl,nok)
    else:
        tmp = maxSubArraySum(loop[cnt],1)
        for j in range(2,max(len(loop[cnt],K+1)):
            tmp2 = maxSubArraySum(loop[cnt],j)
            tmp = max(tmp,tmp2)
    ans = max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    P=LIST()
    C=LIST()
    lp=np.array([])
    sc=np.array([])
    check=[False]*n
    ans=-(10**9+1)
    le=0
    for i in range(n):
        #print(i)
        tl=[]
        tc=[]
        if check[i]==False:
            templ=P[i]-1
            tempc=C[i]
            check[i]=True
            while not(templ in tl):
                check[templ]=True
                np.append(tl,templ)
                np.append(tc,tempc) 
                #tl.append(templ)
                #tc.append(tempc)
                tempc=C[templ]
                templ=P[templ]-1
                
        else:
            continue
        np.append(lp,tl)
        np.append(sc,tc)
    l=lp.size
    
    for i in range(l):
        loop=lp[i]
        score=sc[i]
        cycle=np.sum(score)
        np.append(score,score)
        #print(lp,sc)
        aa=loop.size
        if cycle>=0:
            #flg=1
            remain = k %aa
            cym=0
            for j in range(aa):
                if score[j]<=0:
                    continue
                for ii in range(remain):
                    #print(score[j:j+ii+1])
                    cym=max(np.sum(score[j:j+ii+1]),cym)
            ans=max(k//aa*cycle+cym,ans)
        else:
            #remain = k %len(loop)
            #flg=2
            cym=-(10**9+1)
            for j in range(aa):
                if score[j]<=0:
                    continue
                for ii in range(min(k,aa):
                    #print(score[j:j+ii+1])
                    cym=max(np.sum(score[j:j+ii+1]),cym)
            ans=max(cym,ans)
            
        #print(ans)
    
    if ans<=0:
        ans=max(C)
    print(ans)
    
    
if __name__ == '__main__':
    do()

Submission status: Runtime Error

Solution code:
nk = [int(s) for s in input().split()]
n = nk[0]
k = nk[1]

P = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]

loop = {}
score = {}

for num in range(n):
  if num+1 not in loop:
    l = []
    s = []
    numloop = -1
    
    while numloop-1 != num:
      if numloop == -1:
        numloop = P[num]
      else:
        numloop = P[numloop-1]
      l.append(numloop)
      scoreloop = C[numloop-1]
      s.append(scoreloop)
      
    loop[num+1] = l
    score[num+1] = s
    
    for nums in range(len(l)-1):
      loop[l[nums+1]] = l[nums:] + l[:nums]
      score[l[nums+1]] = s[nums:] + s[:nums]

print(loop)
print(score)

value = []

for cand in loop:
  if len(loop[cand]) < k:
    value.append(max([sum(score[cand][:ind+1])
                     for ind in list(range(len(loop[cand])))]))
  elif sum(score[cand]) <= 0:
    value.append(max([sum(score[cand][:ind+1])
                     for ind in list(range(len(loop[cand])))]))
  else:
    value.append(sum(score[cand]) * (k//len(loop[cand])) +
                 max([sum(score[cand][:ind+1])
                     for ind in list(range(len(loop[cand])))]))
print(max(value))

Submission status: Runtime Error

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

def big(m,l,init=-10**9):
    ret = -10**9
    ll = l + l + l
    for i in range(1,m+1):
        ret_ = sum(ll[:i])
        su = ret_
        for j in range(len(l)):
            su += ll[i+j] - ll[j]
            ret_ = max(ret_,su)
        ret = max(ret,ret_)
    return max(ret,init)

visited = [False]*n

def dfs(l,v):
    if visited[v]:
        return l
    visited[v] = True
    return dfs(l + [c[v]],p[v])

ret = -10**9
for i in range(n):
    l = dfs([],i)
    #print(l)
    if len(l) == 0:
        continue
    if k//len(l) > 0:
        ret = max(ret,sum(l)*(k//len(l))+big(k%len(l),l,0))
        ret = max(ret,big(len(l),l))
        ret = max(ret,sum(l)*(k//len(l)-1)+big(len(l),l))
    else:
        ret = max(ret,big(k,l))

print(ret)

Submission status: Runtime Error

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

n=0
loops=[]
loops_score=[]
searched=[False]*N
sum_len=0

for _ in range(N):
    n=searched.index(False)
    l=[]
    ls=[]
    for i in range(N):
        n=P[n]-1
        searched[n]=True
        if n in l:
            break
        l.append(n)
        ls.append(C[n])
    
    loops.append(l)
    loops_score.append(ls)
    sum_len+=len(l)
    if sum_len==N:
        break
    
#print(loops)
#print(loops_score)

ans=-1*float('inf')

for scores in loops_score:
    ans_=0
    ls=len(scores)
    scores_sum=sum(scores)
    
    if K>ls and scores_sum>0:
        ans_loop=scores_sum*(K//ls)
    else:
        ans_loop=0
        
    maxlen=min(K,ls)
    #print(maxlen)
    ex_scores=scores+scores[:-1]
    #print(ex_scores)
    le=ls*2-1
    
    ruiseki=[0]*(le+1)
    for i in range(1,le+1):
        ruiseki[i]=ruiseki[i-1]+ex_scores[i-1]
    #print(ruiseki)
    
    ans_=max(scores)
    
    if K>=2:
        for d in range(2,maxlen):
            #for j in range(le+1-d):
            for j in range(ls):
                ans_=max(ans_,ruiseki[j+d]-ruiseki[j])
                #print(scores[j:j+d])
                print(le,d,j,ans_+ans_loop)
                if d==maxlen-1:
                    break
    ans=max(ans,ans_+ans_loop)
        
print(ans)

Submission status: Runtime Error

Solution code:
#d
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
newlist = [0 for i in range(k)]
maxlist = []

k1 = k//n
k2 = k%n

for i in range(n):
    score = 0
    Max = float("-inf")
    num1 = i
    num2 = 0
    for j in range(n):
        newlist[j] = p[num1-1]
        num1 = p[num1-1]
    for j in newlist:
        score += c[j-1]
        if Max < score :
            Max = score
    maxlist.append(Max)
Max = max(maxlist)
        
if Max<Max+k1*sum(c):
    Max = Max+k1*sum(c)
print(Max)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,k;
	cin >> n >> k;
	vector<int> p;
	vector<int> c;
	p.push_back(0);
	c.push_back(0);
	for(int i=0;i<n;i++){
		int inp;
		cin >> inp;
		p.push_back(inp);
	}
	for(int i=0;i<n;i++){
		int inp;
		cin >> inp;
		c.push_back(inp);
	}
	vector<vector<int> >  cycles;
	int itr=0;
	int ind=1;
	vector<int> vis;
	for(int i=0;i<=n;i++) vis.push_back(0);
	while(itr!=n){
		vector<int> here;
		here.push_back(ind);
		itr++;
		vis[ind]=1;
		int tmp=ind;
		int nxt=p[tmp];
		while(nxt!=ind){
			vis[nxt]=1;
			here.push_back(nxt);
			nxt=p[nxt];
			itr++;
		}
		cycles.push_back(here);
		for(int i=ind;i<=n;i++){
			if(vis[i]==0){
				ind=i;
				break;
			}
		}
	}

	long long ans=-9223372036854775805;
	for(auto cyc: cycles){
		int sz=cyc.size();
		int stp=k%sz;
		long long mx=0;
		for(int i=0;i<sz;i++){
			long long sm=0;
			for(int j=i;j<i+stp;j++){
				sm+=c[cyc[j%sz]];
			}
			mx=max(sm,mx);
		}
		long long sum=0;
		for(int i: cyc) sum+=i;
		ans=max(ans,mx+(long long)(sum*(long long)(k/sz)));
	}
	cout << 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()))

roots = []

# どのマスから始めるか
for i in range(1, N + 1):
    root = [i]
    visit = [False] * N
    visit[i - 1] = True
    now = i
    for j in range(K):
        next = P[now - 1]
        if visit[next - 1] == True:
            root.append(next)
            break
        else:
            visit[next - 1] = True
            root.append(next)
            now = next
    roots.append(root)
print(roots)

ans = 0
for root in roots:
    head = root[-1]
    head_idx = root.index(head)
    tail = root[-2]
    tail_idx = root.index(tail)
    roop_l = tail_idx - head_idx + 1
    roop = []
    for i in range(head_idx, tail_idx + 1):
        roop.append(root[i])
    # print(roop,"roop")
    if roop == []:
        cumsum = [0]
        for i in range(1, len(root)):
            cumsum.append(cumsum[-1] + C[root[i] - 1])
        # print(cumsum,"cumsum")
        m = max(cumsum)
        # print(m)
        ans = max(ans, m)
    else:
        cumsum = [0]
        for item in roop:
            cumsum.append(cumsum[-1]+C[item-1])
        m = max(cumsum)
        max_idx = cumsum.index(m)
        # print(cumsum,"else",max_idx)
        #
        cumsum2 = [0]
        for i in range(1,len(root)-1):
            cumsum2.append(cumsum2[-1]+C[root[i]-1])
        # print(cumsum2)
        if cumsum[-1]<=0:
            for item in root:
                cumsum2.append(cumsum[-1]+C[item-1])
            ans = max(cumsum2)
        else:
            K -= len(cumsum2)
            roop_cnt = K//len(roop)
            cumsum2.append(cumsum2[-1]+ cumsum[-1]*roop_cnt + m)
            ans = max(cumsum2)
print(ans)

Submission status: Runtime Error

Solution code:
X, K, D  = map(int, input().split())
shou = X//D
amari = X%D 

if D * K <= X:
    print(abs(X) - D*K)
elif K - abs(shou) % 2 == 0:
    print(amari)
else:
    print(abs(amari - D))

Submission status: Runtime Error

Solution code:
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
p = na()
c = na()

visited = [0 for _ in range(n)]

def move(now):
    position = p[now]-1
    point = c[position]
    return point, position


def start_move(start):
    points = []
    point = 0
    now = start
    poi, now = move(now)
    point += poi
    points.append(point)
    visited[now] = 1
    while start!=now:
        poi, now = move(now)
        point += poi
        points.append(point)
        visited[now] = 1
    return point, points

def calc(start):
    point, points = start_move(start)
    steps = len(points)

    res = min(points)
    if steps < k:
        amari = point*(k//steps)
        amari_step = k%steps
        amari_max = min(points)
        for i in range(len(points)):
            amari_max = max(amari_max, points[(i+amari_step)%amari_step]-points[i%amari_step])
        res = max(amari + amari_max, res)

    vmin = min(points)
    vmax = max(points)
    return max(res, vmax+vmin)

res = calc(0)
for i in range(n):
    if visited[i]==0:
        poi = calc(i)
        res = max(poi, res)

print(res)

Submission status: Runtime Error

Solution code:
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))
c = list(map(int,input().split()))
was = [False]*n
sums = []
for i in range(n):
    if not was[i]:
        iWas = [False]*n
        pos = i
        sumn = [c[i]]
        while not iWas[pos]:
            iWas[pos] = True
            was[pos] = True
            pos = p[pos]-1
            sumn+=[c[pos]]
        sumn = sumn[:-1]
        sums.append(sumn)
m = -99999999999999999999999
for i in range(len(sums)):
    totS = sum(sums[i])
    l = len(sums[i])
    for g in range(len(sums[i])):
        arr = []
        s = 0
        for j in range(l):
            s+=sums[i][(g+j)%l]
            arr.append(s)

        if totS > 1:
            m = max(m,totS*(k//l)+max(arr[:k%l]))
        else:

            m = max(m, max(arr[:min(l,k)]))
print(m)

Submission status: Runtime Error

Solution code:
def main():
    n,k=map(int,input().split())
    p=list(map(lambda x:int(x)-1,input().split()))
    c=list(map(int,input().split()))
    ans = -10**9-1
    for i in range(n):
        now = i
        score = [0]
        e = set()
        for j in range(k):
            if p[now] in e:
                if score[-1] < 0:
                    break
                else:
                    nokori = k-j
                    if nokori >= j:
                        add = score[-1]*(nokori//j)
                        added = [x+add for x in score[1:]]
                        nokori %= j
                    else:
                        added = score[1:]
                    #print("added", added)
                    score.append(max(x+score[-1] for x in added[:nokori]))
                    #print(score)
                    break
            else:
                now = p[now]
                e.add(now)
                score.append(score[-1]+c[now])
                #print("k=%s, now:%s"%(j+1,now),score)
        ans = max(ans, *(score[1:]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list((map(lambda a: int(a)-1, input().split())))
C = list(map(int,input().split()))
checked = [True] * N
scores = []
res = - 10 ** 60
for i in range(N):
    if checked:
        current = i
        score = []
        while checked[current]:
            checked[current] = False
            Next = P[current]
            score.append(C[Next])
            current = Next
        if len(score) > 0:
            scores.append(score)
for s in scores:
    l = len(s)
    Sum = sum(s)
    s = s+s
    wa = [0] * (l+1)
    kukan = K % l
    loop = K // l
    wa = [0] * (l+kukan+1)
    for kkk in range(kukan)
        for i in range(l+kkk):
            wa[i+1] = wa[i] + s[i]
        Max = - 10 ** 60
        for i in range(l):
            Max = max(Max,wa[i+kkk]-wa[i])
        res = max(res, Sum * loop + Max,Max)
print(res)

Submission status: Runtime Error

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

R = [0 for _ in range(N)]
S = [0 for _ in range(N)]
q=0

for i in range(N):
  a = 1
  if R[i] ==0:
    b = P[i] - 1
    for j in range(N):
      if b != i:
        a += 1
        b = P[b] - 1
      else:
        R[i] = a
        break
        
for i in range(N):
  if R[i] >= K:
    s = [0 for _ in range(K)]
    p = P[i] - 1
    s[0] = C[p]
    for j in range(K-1):
      s[j+1] = s[j] + C[P[p]-1]
      p = P[p]
      S[i] = max(s)
      
  else:
    q = P[i] -1
    r = C[q]
    for j in range(R[i]-1):
      q = P[q] - 1
      r += C[q]
      
    s = [0 for _ in range(R[i])]
    p = P[i] - 1
    s[0] = C[p]
    for j in range(R[i]-1):
      s[j+1] = s[j] + C[P[p]-1]
      p = P[p]
      S[i] = max(s)

      if q > 0:
        k = K // R[i]
        S[i] = S[i] + r * k

print(S)
print(max(S))

Submission status: Runtime Error

Solution code:
import numpy as np
N,K = list(map(int, input().split()))
input_list = list(map(int, input().split()))
input_list = list(np.array(input_list)-1)
c_list = list(map(int, input().split()))

#for i in range(N):
def roop_func(l, i, start, return_list=[]):
    return_list.append(l[i])
    if l[i] == start:
        return return_list 
    return roop_func(l, l[i],start, return_list)

total_best = -100000000000000000000
for start in range(N):
    p_list = roop_func(input_list, start, start,[])
    epoc = sum([c_list[i] for i in p_list])
    if epoc <= 0: # 回るごとに下がる場合
        best = c_list[p_list[0]]
        current_score = c_list[p_list[0]]
        for i in range(1, min(K, len(p_list))):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    else: #回るごとに上がる場合
        syo,amari = divmod(K, len(p_list))
        base = (syo-1) * epoch
        p_list = p_list.append(p_list[:amari])
        best = c_list[p_list[0]] + base
        current_score = c_list[p_list[0]] + base
        for i in range(1, len(p_list)):
            current_score += c_list[p_list[i]]
            if best < current_score:
                best = current_score
    if best > total_best:
        total_best = best
        
print(total_best)

Submission status: Runtime Error

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

    P_id = [p - 1 for p in P]

    max_ = -float('inf')

    for start in range(N):
        # print("#loop{}".format(start))

        # 解析

        current = start
        visited = [-1] * N
        visited[current] = 0

        history = [current]
        before_loop_ids = []
        loop_ids = []

        for step in range(1, N):  # 高々N回で抜ける
            next_ = P_id[current]
            if visited[next_] != -1:
                # loop_start = history.index(next_)
                loop_start = visited[next_]
                loop_ids = history[loop_start:]
                before_loop_ids = history[:loop_start]
                history.append(next_)
                break
            else:
                history.append(next_)
                current = next_
                visited[current] = step

        score_per_loop = sum([C[i] for i in loop_ids])
        # print('history', history)
        # print('before', before_loop_ids)
        # print('loop', loop_ids)
        # print('score_per_loop', score_per_loop)

        score = 0
        current = start
        num_move = K

        # before loop

        for _ in range(min(len(before_loop_ids), K)):
            current = P_id[current]
            score += C[current]
            # print(score)
            max_ = score if score > max_ else max_
            # max_ = max(max_, score)
            num_move -= 1

        # loop
        n = num_move // len(loop_ids)
        # after = num_move % len(loop_ids)
        if score_per_loop > 0:
            score += n * score_per_loop
            # print(score)
            # max_ = max(max_, score)
            max_ = score if score > max_ else max_
            num_move -= n * len(loop_ids)

        # after loop
        for i in range(max(num_move, len(loop_ids))):
            current = P_id[current]
            score += C[current]
            # print(score)
            # max_ = max(max_, score)
            max_ = score if score > max_ else max_
            num_move -= 1

        # assert num_move == 0, 'expected:{} actual:{}'.format(0, num_move)

    print(max_)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def score(i):
    log = [-1 for i in range(N)]
    score = []
    now = i
    count = 0
    while log[now] == -1:
        log[now] = count
        count += 1
        now = P[now]-1
        before = 0
        ne = before + C[now]
        score.append(ne)
        before = ne
    n = len(score)
    if log[now] == 0:
        lag = 0
        lag_score = 0
        roop_score = score
        roop = n - lag
    else:
        lag = log[now]
        lag_score = score[lag]
        roop_score = score[lag:]
        roop = n - lag
    if K <= n:
        ans = max(score)
    else:
        num_roop = (K - lag)//roop
        amari = (K - lag)%roop
        sa = max(lag_score)
        ans = max(num_roop*(roop_score[-1] - sa) + max(roop_score[:amari] - sa) + lag_score,max(score))
    return ans
print(max([score(i) for i in range(N)]))

Submission status: Runtime Error

Solution code:
def max_score(_l, n):
  _l = _l + _l
  if n == 0:
    return 0
  ans = -(10 ** 100)
  for i in range(1, len(_l) // 2 + n):
    _l[i] += _l[i - 1]
  for i in range(len(_l) // 2):
    for j in range(1, n + 1):
      ans = max(ans, _l[i + j] - _l[i])
  return ans

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
check = [False for i in range(n)]

ans = -(10 ** 100)
for i in range(n):
  if check[i]:
    continue
  _i = i
  l = []
  while not check[_i]:
    check[_i] = True
    _i = p[_i] - 1
    l.append(c[_i])
  if sum(l) < 0:
    _ans += max_score(l, len(l))
  elif k % len(l) != 0:
    _ans = k // len(l) * sum(l)
    _ans += max_score(l, k % len(l))
  else:
    _ans = (k // len(l) - 1) * sum(l)
    _ans += max_score(l, len(l))
  ans = max(ans, _ans)

print(ans)

Submission status: Runtime Error

Solution code:
import math
N,K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
rooplist = []
alreadydone = []
startijlist = []
for i in range(N):
  startijlist.append([0,0])
i = 0
while(len(alreadydone)<N):
  oneroop = [i]
  recordi = len(rooplist)
  recordj = -1
  while(1):
    recordj += 1
    startijlist[i] = [recordi , recordj]
    alreadydone.append(i)
    if(P[i]-1 == oneroop[0]):
      i = 0
      while(1):
        if(i in alreadydone):
          i += 1
        else:
          break
      break
    else:
      oneroop.append(P[i]-1)
      i = P[i] - 1
  rooplist.append(oneroop)
#print("rooplist  =",rooplist)

roopClist = []
for i in range(len(rooplist)):
  oneroopC = []
  for j in range(len(rooplist[i])):
    oneroopC.append(C[rooplist[i][j]])
  roopClist.append(oneroopC)
#print("roopClist =",roopClist)
#print("startijlist =",startijlist)

sumlist = []
for i in range(len(roopClist)):
  sumlist.append(sum(roopClist[i]))

maxClist = []
for i in range(N):
  k = 0
  nowClist = []
  nowC = roopClist[startijlist[i][0]][startijlist[i][1]]
  while(k < len(roopClist) and k < K):
    nowClist.append(nowC)
    k += 1
    if(startijlist[i][1] + k >= len(roopClist[startijlist[i][0]])):
      nowC += roopClist[startijlist[i][0]][startijlist[i][1] + k - len(roopClist[startijlist[i][0]])]
    else:
      nowC += roopClist[startijlist[i][0]][startijlist[i][1] + k]
  maxClist.append(max(nowClist))
  numcango = len(roopClist[startijlist[i][0]]) - startijlist[i][1] - 1
  if(sumlist[startijlist[i][0]] > 0 and K-numcango > 0):
    numremaincango = (K-numcango)%len(roopClist[startijlist[i][0]])
    numroop = math.floor((K-numcango)/len(roopClist[startijlist[i][0]]))
    x = startijlist[i][1]
    nowClist = []
    for x in range(numcango):
      nowClist.append(sum(roopClist[startijlist[i][0]][startijlist[i][1]:startijlist[i][1]+x]))
    nowClist.append(sum(roopClist[startijlist[i][0]][startijlist[i][1]:] + numroop*sumlist[startijlist[i][0]]))
    for x in range(numremaincango):
      nowClist.append(numClist[-1] + roopClist[startijlist[i][0]][startijlist[i][1]+x])
    maxClist.append(max(nowClist))
#print("maxClist =",maxClist)
print(max(maxClist))

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')
if k > n:
    m = k // n-1
    k = k - n*m

for i in range(n): #start
    now = i
    total = 0
    for j in range(1, k+1):
        now = pn[now]-1
        total += cn[now]
        ans = max(ans, total)

if sum(cn) >0:
    ans += sum(cn)*m

print(ans)

Submission status: Runtime Error

Solution code:
def get_e(now, times):
  if times == 1:
    return e[now - 1][0]
  else:
    point = get_e(e[now - 1][1], times -1)
    return max(e[now - 1][0], point)
  
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

e = [0] * n
for i in range(n):
  e[i] = (c[p[i] - 1], p[p[i] - 1])

for i in range(n):
  if i == 0:
    max_point = get_e(i, k)
  else:
    point = get_e(i, k)
    if point > max_point:
      max_point = point
      
print(max_point)

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

def f(x):
    num_list = []
    score_list = []
    while True:
        if p[x] in num_list:
            return score_list
        score_list.append(c[x])
        num_list.append(p[x])
        x = p[x]
ans = 0
for i in range(n):
    score_list = f(i)
    score = (k // len(score_list)) * sum(score_list)
    for j in range(k % len(score_list)):
        if score_list[i] > 0:
            score += score_list[i]
    if ans < score:
        ans = score

print(ans)

Submission status: Runtime Error

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

cycle = [[] for i in range(N)]
loop = [0 for i in range(N)]
imax = [0 for i in range(N)]

for i in range(N):
  loop[i] += C[i]
  j = P[i]
  cycle[i] += [j]
  while(j != i):
    loop[i] += C[j]
    j = P[j]
    cycle[i] += [j]

for i in range(N):
  if K > len(cycle[i]) and loop[i] > 0:
    q = int(K/len(cycle[i]))
    r = K % len(cycle[i])
    iscore = [0 for k in range(len(cycle[i]))]
    for j in range(len(cycle[i])):
      for k in range(len(cycle[i]))[j:]:
        iscore[k] += C[cycle[i][j]]
    imax[i] = max(max(iscore), max(iscore[:r])+loop[i]) + loop[i]*(q-1)
  else:
    iscore = [0 for i in range(len(cycle[i]))]
    for j in range(len(cycle[i])):
      for k in range(len(cycle[i]))[j:]:
        iscore[k] += C[cycle[i][j]]
    imax[i] = max(iscore)
print(max(imax))