Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
n, limit = list(map(int, input().split()))
permute = list(map(int, input().split()))
score = list(map(int, input().split()))

visited = [False] * n

ans = -10 ** 16

for i in range(n):
    if visited[i]:
        continue

    score_circle = []
    now = i
    while True:
        visited[now] = True
        score_circle.append(score[now])

        next_ = permute[now] - 1
        if visited[next_]:
            # 円環のできあがり
            break
        now = next_
    
    period = len(score_circle)

    score_circle *= 2
    # 累積和
    cumsum = [0] * (2 * period + 1)
    for j in range(1, 2*period+1):
        cumsum[j] = cumsum[j-1] + score_circle[j-1]
    
    p_sum_max = [-(10**15)] * (period + 1)
    for k in range(period):
        for ll in range(period):
            p_sum_max[ll] = max(p_sum_max[ll], cumsum[k+ll] - cumsum[k])
    
    ans = max([ans] + p_sum_max[1:min(period+1, limit+1)])

    q, resi = divmod(limit, period)

    if q >= 1:
        ans = max(ans, cumsum[period] * (q-1) + max(p_sum_max[1:]))
        ans = max(ans, cumsum[period] * (q) + max(p_sum_max[:resi + 1]))

        # print(p_sum_max[:resi + 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
p=list(map(int,input().split()))
p=[i-1 for i in p]
c=list(map(int,input().split()))
m=-10**19
for i in range(n):
	tmp=i
	cos=0
	for j in range(k):
		cos+=c[tmp]
		if cos>m:
			m=cos
		tmp=p[tmp]
print(m)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy


def main():
    n,k = map(int, input().split())
    plist = list(map(int, input().split()))
    clist = list(map(int, input().split()))

    max_num = max(clist)
    if n<k:
        max_num = sum(clist)

    for i in range(len(plist)):
        ans = 0
        a = plist[i]
        for j in range(k):
            ans += clist[a-1]
            a = plist[a-1]
            if ans >= max_num:
                max_num = ans

    print(max_num)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

ps = [int(s) for s in input().split()]
cs = [int(s) for s in input().split()]

best_scores = []

for n in range(N):
  x = n
  scores = [0 for _ in range(K)]
  for k in range(K):
    x = ps[x] - 1
    scores[k] = scores[k-1] + cs[x]
  best_scores.append(max(scores))
print(max(best_scores))

Submission status: Time Limit Exceeded

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

for i in range(n):
  b=0
  d=p[i]-1
  for j in range(k):
    b+=c[d]
    d=p[d]-1
    a.append(b)

print(max(a))

Submission status: Time Limit Exceeded

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

visited = [False for _ in range(n)]
lp = []
lp_cum = []
lp_sum = []
range_s = []
for i in range(n):
	if not visited[i]:
		lp.append([i])
		lp_cum.append([0, c[i]])
		visited[i] = True
		while not visited[p[lp[-1][-1]]]:
			lp[-1].append(p[lp[-1][-1]])
			lp_cum[-1].append(lp_cum[-1][-1] + c[lp[-1][-1]])
			visited[lp[-1][-1]] = True
		lp_sum.append((lp_cum[-1][-1], len(lp[-1])))
		range_s.append(set())
		for x in range(1, len(lp_cum[-1])):
			for y in range(x):
				range_s[-1].add((lp_cum[-1][x] - lp_cum[-1][y], x-y))
				if x < len(lp_cum[-1])-1 or y > 0:
					range_s[-1].add((lp_cum[-1][-1] - lp_cum[-1][x] + lp_cum[-1][y], len(lp[-1])-x+y))

ok, ng = -10**9, 10**18+1

while ng-ok > 1:
	x = (ok+ng)//2
	flg = False
	for i in range(len(lp)):
		s_sum, s_num = lp_sum[i]
		if s_sum <= 0:
			for r_sum, r_num in range_s[i]:
				if r_sum >= x and r_num <= k:
					flg = True
					break
		else:
			for r_sum, r_num in range_s[i]:
				if r_num > k:
					continue
				if r_sum >= x:
					flg = True
					break
				rep = (x-1-r_sum) // s_sum + 1
				if rep * s_num + r_num <= k:
					flg = True
					break
	if flg:
		ok = x
	else:
		ng = x

print(ok)

Submission status: Time Limit Exceeded

Solution code:
def n_sum_max(L):
    v=list()
    n = len(L)
    LL = L + L 
    for k in range(n):
        sk = None
        for i in range(n):
            s = LL[i]
            for j in range(i+1,i+k+1):
                s += LL[j]
        
            if sk == None:
                sk=s
            else:
                sk=max(sk,s)
        if k==0:
            v.append(sk)
        else:
            v.append(max(sk,v[k-1]))

    return v

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

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

check=[1 for i in range(N)]

rings = list()
ring_sum = list()
ring_n = list()
ring_n_sum_max = list()

for i in range(N):
    D=list()
    ni = i
    while check[ni]==1:
        check[ni] = 0
        D.append(C[ni])
        ni = P[ni]-1

    if len(D)>0:
        rings.append(D)
        ring_sum.append(sum(D))
        ring_n.append(len(D))

        ring_n_sum_max.append(n_sum_max(D))

# print(P)
# print(C)
# print(rings)
# print(ring_sum)
# print(ring_n)
# print(ring_n_sum_max)

ring_scores=list()
for i in range(len(rings)):
    if K >= ring_n[i]:
        a = max(ring_n_sum_max[i])
        b = ring_sum[i]
        if b > 0:
            m = int(K/ring_n[i])
            left = K % ring_n[i]
            b = ring_sum[i]*m
            # print("b=",b)
            if left > 0:
                    b += ring_n_sum_max[i][left-1]
            # print("b=",b)
        ring_scores.append(max(a,b))
    else:
        ring_scores.append(ring_n_sum_max[i][K-1])


print(max(ring_scores))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
from collections import Counter
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():
    n, k = geta(int)
    p = [0] + list(geta(int))
    c = [0] + list(geta(int))

    inf = 1 << 32

    used = [False] * (n + 1)

    ans = -inf

    for i in range(1, n + 1):

        if used[i]:
            continue
        else:
            used[i] = True

        c_loop = []
        j = p[i]
        c_loop += [c[j]]

        while j != i:
            used[j] = True
            j = p[j]
            c_loop += [c[j]]

        n_loop = len(c_loop)
        c_loop = np.array(c_loop + c_loop)
        cs_loop = np.cumsum(c_loop)
        tot_loop = cs_loop[n_loop - 1]

        _jmax = k if k < n_loop else n_loop

        _ans = -inf
        _len = 0
        for _i in range(n_loop):
            for _j in range(1, _jmax + 1):
                _tmp = cs_loop[_j + _i] - cs_loop[_i]
                if _ans < _tmp:
                    _ans = _tmp
                    _len = _j

        if tot_loop > 0:
            _ans += tot_loop * ((k - _len) // n_loop)

        if ans < _ans:
            ans = _ans

        _ans = -inf
        _len = 0
        if tot_loop > 0 and k > n_loop:
            score_base = tot_loop * (k // n_loop)
            _jmax = k % n_loop
            for _i in range(n_loop):
                for _j in range(1, _jmax + 1):
                    _tmp = cs_loop[_j + _i] - cs_loop[_i]
                    if _ans < _tmp:
                        _ans = _tmp
                        _len = _j

            _ans += score_base

        if ans < _ans:
            ans = _ans

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#input = raw_input

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

ps= map(int, input().split(" "))
graph = {}
for i, out in enumerate(ps):
    in_ = i+1
    graph[in_] = out

cs= list(map(int, input().split(" ")))
pos_points = [None] + cs


def f(si):
    points = [None] * (n+1)
    points[si] = 0

    times = [None] * (n+1)
    times[si] = 0

    cur_pos = si
    cur_point = 0
    loop_len = None
    cur_max_point = None
    for cur_time in range(1, k+1):
        next_pos = graph[cur_pos]

        cur_point += pos_points[next_pos]
        cur_max_point = cur_point if cur_time == 1 else max(cur_max_point, cur_point)

        if times[next_pos] is not None:
            loop_len = cur_time - times[next_pos]
            loop_sum_point = cur_point - points[next_pos]
            loop_start_pos = next_pos
            break

        times[next_pos] = cur_time
        points[next_pos] = cur_point

        cur_pos = next_pos

    if loop_len is None:
        return cur_max_point

    if loop_sum_point <= 0:
        return cur_max_point


    loop_points = []
    cur_point = 0
    cur_pos = loop_start_pos
    while True:
        next_pos = graph[cur_pos]
        cur_point += pos_points[next_pos]
        loop_points.append(cur_point)
        if next_pos == loop_start_pos:
            break
        cur_pos = next_pos

    assert loop_sum_point == loop_points[-1]
    #assert len(loop_points) == loop_len
    #print("loop_points", loop_points)

    loop_made_point = points[loop_start_pos]

    x = k-times[loop_start_pos]
    r = x // loop_len
    q = x % loop_len
    ret = loop_made_point + r * loop_sum_point + (0 if q == 0 else max( loop_points[:q] ) )

    ret = max(cur_max_point, ret)
    return ret



for si in range(1, n+1):
    if si == 1:
        out = f(si)
    else:
        out = max(out, f(si))
print(out)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

ans = -((10)**10)

for sp in range(N):
    if K <= N:
        # 愚直にやる
        nextp = P[sp]
        score = C[sp]
        ans = max(ans, score)
        rest = K - 1
        while rest > 0:
            score += C[nextp]
            nextp = P[nextp]
            ans = max(ans, score)
            rest -= 1
    else:
        
        # K の方がNより大きい
        cache = set([sp])
        nextp = P[sp]
        score = C[sp]
        l = 1
        ans = max(ans, score)

        while not nextp in cache:
            cache.add(nextp)
            score += C[nextp]
            nextp = P[nextp]
            ans = max(ans, score)
            l += 1
        
        if score > 0:
            # print("l:", l)
            # print("sc:", score)
            rest = 0
            if K >= l:
                loop = K // l
                score *= loop
                ans = max(ans, score)
                # rest = K - (l*loop)
                rest = K % l
            
            if rest > 0:
                nextp2 = P[sp]
                score += C[sp]
                rest -= 1
                ans = max(ans, score)

                while rest > 0:
                    score += C[nextp2]
                    nextp2 = P[nextp2]
                    rest -= 1
                    ans = max(ans, score)

print(ans)

Submission status: Time Limit Exceeded

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

ans = -10**10
for n_i in range(1, n+1):
  counter=1
  score=0
  max_score=-10**10
  m=n_i
  
  while counter<=k:
    m = P[m]
    score += C[m]
    max_score = max(max_score, score)
    counter += 1
    
  ans = max(ans, max_score)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, K = list(map(int, input().split()))
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))

    return N, K, P, C


def main(N: int, K: int, P: list, C: list) -> None:
    """
    メイン処理

    Args:\n
        N (int): マスの数
        K (int): 移動回数上限
        P (list): 移動場所
        C (list): 得点
    """
    # 求解処理
    ans = -sys.maxsize
    for i in range(N):
        length = 0
        pos = i
        S = [0 for n in range(N)]
        score = 0
        while True:
            pos = P[pos] - 1
            score += C[pos]
            S[length] = score
            length += 1
            if pos == i:
                break
        S = S[:length]

        if K <= length:
            ans = max(ans, max(S[:K]))
        else:
            circ_S = S[-1]
            circ_cnt = int(K / length)
            if circ_S > 0:
                if K % length == 0:
                    ans = max(ans, (circ_cnt - 1) * circ_S + max(S))
                else:
                    ans = max(ans, circ_cnt * circ_S + max(S[:(K % length)]))
            else:
                ans = max(ans, max(S))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, K, P, C = get_input()

    # メイン処理
    main(N, K, P, C)

Submission status: Time Limit Exceeded

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

# N, K = 5, 2
# P = list(map(int, '2 4 5 1 3'.split()))
# C = list(map(int, '3 4 -10 -8 8'.split()))

res = -10 ** 10

for n in range(N):
    index = n

    step = []
    score_list = []
    score = 0
    for i in range(K):
        step.append(index)
        score += C[P[index] - 1]
        score_list.append(score)
        index = P[index] - 1

        if index in step and score > 0:
            loop_score = score
            step_num = len(step)
            # print(loop_score, step_num)

            score = loop_score * (K // step_num)
            # print('score', score)
            index = step[0]
            for j in range(K % step_num):
                score += C[P[index] - 1]
                index = P[index] - 1
            break
        if index in step and score <= 0:
            score = max(score_list)
            break
    else:
        score = max(score_list)
    res = max(res, score)


print(res)

Submission status: Time Limit Exceeded

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

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

c = C[P[0]-1]

for i in range(n):
    t = 0
    
    L = []
    S = set()
    for j in range(k):
        if j == 0:
            now = P[i]-1
        else:
            now = P[now]-1
        if now in S:
            print(now)
            a = L.index(now)
            alen = len(L)-a+1
            
            b = k-j +1
            l = b%alen
            x = 0
            c2 = 0
            for i in range(a,len(L)):
                c += 1
                x += C[P[i]-1]
                if c == l:
                    t += x
            t += x
            if c < t:
                c = t           
#            print(x)
            break
        else:
            t += C[now]
            if c < t:
                c = t
            
        #print(i,j,c)
#    print(L)
print(c)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
p=list(map(int, input().split()))
c=list(map(int, input().split()))
ans = -999999999999999
z = 0

#if k >= n:
#    a = sum(c)
#    if a > 0:
#        z = a * int(k/n)
        #k = k%n

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

print(ans+z)

Submission status: Time Limit Exceeded

Solution code:
N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
DispP = [0]*N
for TN in range(0,N):
    Now   = Next[TN]
    Point = GetP[Now]
    MAXP  = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        if Now==TN and Point>=0:
            RoopFlag = True
            break
        elif Now==TN and Point<0:
            RoopFlag = False
            break
        if MAXP<Point:
            MAXP = Point
            MInd = TK
    if RoopFlag:
        Omit = K-RoopC*(K//RoopC)
        PointO = 0
        MAXO = 0
        for TO in range(0,Omit):
            Now = Next[Now]
            PointO += GetP[Now]
            if MAXO<PointO:
                MAXO = PointO
        if Point*(K//RoopC)+MAXO>=Point*((K//RoopC)-1)+MAXP:
            DispP[TN] = Point*(K//RoopC)+MAXO
        else:
            DispP[TN] = Point*((K//RoopC)-1)+MAXP
    else:
        DispP[TN] = MAXP
print(max(DispP))

Submission status: Time Limit Exceeded

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

p = list(map(int,input().split()))
c = list(map(int,input().split()))

con = -1000000000;

for x in range(n):
    s = []
    i = x;
    while True:
        i = p[i]-1;
        s.append(c[i])
        if i == x:
            break;
    ss = len(s);
    t = [0]*ss
    t[0] = s[0]
    for y in range(1,ss):
        t[y]=t[y-1]+s[y];
        
    
    roop = t[ss-1]
    maxt = max(t);
    if roop <= 0:
        point = maxt;
    else:
        roopa = k // ss
        roopb = k % ss
        if roopb == 0:
            roopc = (roop * roopa)
        else:
            roopc = (roop * roopa) + max(t[0:roopb])
        roopd = (roop *(roopa-1)) + maxt
        if roopc >= roopd:
            point = roopc
        else:
            point = roopd
    if point > con:
        con = point

print(con);

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
d=[0]*5001
score_max=min(C)
for L in range(n):
  score=0
  for i in range(k):
    score+=C[P[L]-1]
    score_max=max(score,score_max)
    L=P[L]-1
print(score_max)

Submission status: Time Limit Exceeded

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

k = 0
score_list = []
for i in range(N):
  start_position = i
  position = i
  score = 0
  for k in range(K):
    position = P[position] - 1
    score += C[position]
    score_list.append(score)

    if start_position == position:
      if score < 0:
        break
        
print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for n in range(1,N+1): #startを選ぶ
  s = 0
  i = n
  for k in range(K): #何回やるか
    i = P[i]
    s = s + C[P[i]]
    if(n == 1):
      m_s = s
    if(s > m_s):
      m_s = s
print(m_s)

Submission status: Time Limit Exceeded

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

has_visited = [False]*N
score_max = -float('inf')

for i in range(N):
    if has_visited[i]:
        continue
    
    loop_val = []

    j = i
    while True:
        loop_val.append(C[j])
        has_visited[j] = True
        j = P[j] - 1
        if loop_val[0] == C[j]:
            break
    
    # sum_arr = [0]
    # loop_length = len(loop_val)

    # for k in range(1, loop_length + K):
    # sum_arr.append(sum_arr[k-1] + loop_val[(k - 1) % loop_length])

    # print(loop_val)

    sm = 0
    for p in range(len(loop_val)):
        sm += loop_val[p]
    
    # print(sm)
    
    loop_length = len(loop_val)

    for l in range(loop_length):
        res = -1
        s = 0
        for k in range(K):
            s = max([s + loop_val[(k+l) % loop_length], loop_val[(k+l) % loop_length]])
            res = max([res, s])
        
        if res == -1:
            res = max(loop_val)
        
        # print(res)

        if score_max < res:
            score_max = res

print(score_max)

Submission status: Time Limit Exceeded

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

# N, K = 5, 2
# P = list(map(int, '2 4 5 1 3'.split()))
# C = list(map(int, '3 4 -10 -8 8'.split()))

res = -10 ** 10

for n in range(N):
    index = n

    step = []
    score_list = []
    score = 0
    for i in range(K):
        step.append(index)
        score += C[P[index] - 1]
        score_list.append(score)
        index = P[index] - 1

        if index in step and score > 0:
            loop_score = score
            step_num = len(step)
            # print(loop_score, step_num)

            score = loop_score * (K // step_num)
            # print('score', score)
            index = step[0]
            for j in range(K % step_num):
                score += C[P[index] - 1]
                index = P[index] - 1
            break
    else:
        score = max(score_list)
    res = max(res, score)


print(res)

Submission status: Time Limit Exceeded

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

# score[i][j] = i-th score, position when start from j
score = [[(-(10**9) if i > 0 else 0, j) for j in range(N)] for i in range(N+1)]
M = [[-(10**13) for j in range(N)] for i in range(N+1)]
T = [0 for i in range(N)]
for i in range(1, N+1):
	for j in range(N):
		if T[j] > 0:
			continue
		(s,p) = score[i-1][j]
		next_p = P[p]
		M[i][j] = max(M[i-1][j], s + C[next_p])
		score[i][j] = (s + C[next_p], next_p)
		if j == next_p:
			T[j] = i

if K <= N:
	print(max([max([s[i][0] for i in range(N)]) for s in score[1:K+1]]))
	exit()

ans = -(10 ** 9)
for i in range(N):
	t = T[i]
	S = score[t][i][0]
	if S > 0:
		base = S * (K // t)
		r = K % t
		ad = max(0, M[r][i])
		ans = max(ans, base + ad)
	else:
		ans = max(ans, M[N][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

N, K = li()
P = [0] + li()
C = [0] + li()
max_scores = [-10**12] * (N+10)
for init_i in range(1, N+1):
    i = init_i
    scores = [0]
    for l in range(1, K+1):
        i = P[i]
        score = scores[l-1] + C[i]
        scores.append(score)
    scores[0] = -10**9
    max_scores[i] = max(scores)
print(max(max_scores))

Submission status: Time Limit Exceeded

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])
p = list(map(int,input().split()))
c = list(map(int,input().split()))
score = 0
score_list = []
prepare = []
for i in range(1,n+1):
    a = i
    for j in range(k):
        a = p[a-1]
        score += c[a-1]
        prepare.append(score)
    score_list.append(max(prepare))
    score = 0
    prepare = []
print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
(n, k), p, c = [[*map(int, i.split())] for i in open(0)]
visit = [0] * n
visit[0] = 1
loop = [0] * n
count = a = 0
while True:
    a = p[a] - 1
    if visit[a]:
        if loop[a]:
            break
        count += c[a]
        loop[a] = 1
    visit[a] = 1

ln = sum(loop)


def solve(x, t):
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        if loop[x] and l:
            if count > 0 and t > ln:
                sub += (t // ln - 1) * count
                t -= (t//ln-1)*ln
            l = False
        if t < 1:
            ans = max(sub, ans)
            return ans
        x = p[x] - 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)


print(max(solve(i, k) for i in range(n)))

Submission status: Time Limit Exceeded

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

s = [0] * n
now = [i for i in range(n)]
ans = max(c)
for _ in range(k):
   next = [p[now[i]]-1 for i in range(n)]
   s = [s[i]+c[next[i]] for i in range(n)]
   now = [next[i] for i in range(n)]
   ans = max(ans, max(s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np

def main():
    n, k = map(int, input().split())
    p_array = np.array(list(map(int, input().split())))
    c_array = np.array(list(map(int, input().split())))
    
    ans = -float("inf")
    for start in p_array:
        tmp = -float("inf")
        tmp_sum = 0
        for i in range(k):
            tmp_sum += c_array[start - 1]
            start = p_array[start - 1]
            if tmp_sum > tmp:
                tmp = tmp_sum
        if tmp > ans:
            ans = tmp
    print(ans)

main()

Submission status: Time Limit Exceeded

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

p = input().split(' ')
c = input().split(' ')

maxpoint = []

for j in range(n):
    next = int(p[j])-1
    temp = 0
    point = []
    for i in range(k):
        temp += int(c[next])
        point.append(temp)
        next = int(p[next])-1
    maxpoint.append(max(point))

print(max(maxpoint))