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:
#0:N, 1:K
line = list(map(int, input().split( )))
#next pos
P = list(map(int, input().split( )))
#score pos
C = list(map(int, input().split( )))

def nextpos(n):
  global P
  global C
  return [P[n]-1, C[P[n]-1]]
score = C[0]
for i in range(line[0]):
  #countがline[1]になったら終了
  count = 0
  pos, s = i, 0
  while count < line[1]:
    nex = nextpos(pos)
    pos = nex[0]
    s += nex[1]
    count += 1
    if score < s:
      score = s
print(score)

Submission status: Time Limit Exceeded

Solution code:
#D - Moving_piece
N,K = map(int,input().split())
P =[]
C =[]
P = list(map(int,input().split()))
C = list(map(int,input().split()))

score_output = -1000000010
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = 0
    loop  = 0
    score_max = -1000000010
    while True:
        step  += 1
        score += C[ichi]
        ichi   = (P[ichi] -1)
        if i ==  (P[ichi] -1):
            score += C[ichi]
            break
        
    path = 0
    cnt  = 0
    
    while True:
        cnt  += 1
        path += C[ichi]
        
        if cnt > K:
            break
        
        loop = int((K - cnt) / (step+ 1))
        if score > 0:
            score_max = path + loop * score
        else:
            score_max = path
        if score_max > score_output:
            score_output = score_max

        ichi   = P[ichi]-1
        if i == (P[ichi] -1):
            break
# 出力
print(score_output)

Submission status: Time Limit Exceeded

Solution code:
n,K=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
if K == 1:
    print(max(c));exit()
ans = -10**10
def cycle(k):
    mo=k
    clen=0
    cscore=0
    flg = True
    cmax=[-10**10]
    while (mo != k or flg):
        clen+=1
        cscore+=c[mo]
        mo = p[mo]
        cmax.append(max(cmax[-1],cscore))
        if mo == k:
            flg = False
    if cscore<0:
        return cmax[min(K-1,clen-1)],cmax
    return cscore*((K-1)//clen)+cmax[(K-1)%clen+1],cmax
for i in range(n):
    a,l=cycle(i)
    if a>ans:
        ans = a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split(' ')]
number = [int(i) for i in input().split(' ')]
point = [int(i) for i in input().split(' ')]

def main(number, point, tmp, i, k, cnt) :
  tmp += point[number[i-1]-1]
  cnt += 1
  next = number[i-1]
  if k > cnt :
    return main(number, point, tmp, next, k, cnt)
  else :
    return tmp  
result = []
for m in range(k) :
  m += 1 
  res = []
  for i in number :
    tmp = 0
    cnt = 0
    res.append(main(number, point, tmp, i, m, cnt))
  result.append(max(res))
print(max(result))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split(' ')]
number = [int(i) for i in input().split(' ')]
point = [int(i) for i in input().split(' ')]

def main(number, point, tmp, i, k, cnt) :
  tmp += point[number[i-1]-1]
  cnt += 1
  next = number[i-1]
  if k > cnt :
    return main(number, point, tmp, next, k, cnt)
  else :
    return tmp  
result = []
for m in range(k+1) :
  res = []
  for i in number :
    tmp = 0
    cnt = 0
    res.append(main(number, point, tmp, i, m, cnt))
  result.append(max(res))
print(max(result))

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 = [i for i in range(1,n)]

"""
print(d)
print(p)
print(c)
"""

t = []
f = []
for i in d:
    e = 0
    l = p[i]
    for j in range(k):
        e += c[l-1]
        l = p[l-1]
        f += [e]
    t += [max(f)]
print(max(t))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
 
def main():
    readline = stdin.readline
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))
    C = list(map(int, readline().split()))
    P = [i-1 for i in P]
    Position_list=[P]
    Score_list=[[0 for i in range(N)]]
    Max_list=[]
 
    for j in range(K):
        Updated_Position=[]
        Updated_Score=[]
        Current_Position=Position_list[j]
        Current_Score=Score_list[j]
        for i in range(N):
            Position=P[i]
            Updated_Position.append(Current_Position[Position])
            Updated_Score.append(Current_Score[i]+C[Current_Position[i]])
        Position_list.append(Updated_Position)
        Score_list.append(Updated_Score)
        Max_list.append(max(Score_list[j+1]))
   
    print(max(Max_list))
main()

Submission status: Time Limit Exceeded

Solution code:
import math
 
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
r = max(C)
for start_index in range(N):
    temp_sum = C[start_index]
    if temp_sum <= 0:
        continue
    index = start_index
    for j in range(K-1):
        index = P[index]-1
        temp_sum += C[index]
        r = temp_sum if temp_sum > r else r
 
print(r)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase    

# %% input phase
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# %% process phase
for i in range(n):
    p[i] -= 1

ans = -1e14
# スタートは全部確認
for si in range(n):
    np = si
    ts = 0
    s = []
    while 1:
        np = p[np]
        s.append(c[np])
        ts += c[np]
        if np == si: break
    
    l = len(s)
    
    sc1 = 0
    for i in range(l):
        sc1 += s[i]
        if i+1 > k: break
        if ts > 0:
            e = (k - (i+1))//l
            sc2 = ts*e
        else:
            sc2 = 0
        sc = sc1 + sc2
        ans = max(ans, sc)

# %%output phase
print(ans)

Submission status: Time Limit Exceeded

Solution code:
Neg_INF=-10**10

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

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

dp=[[0 for i in range(K+1)] for i in range(N)]

ans=Neg_INF
for i in range(1,K+1):
    for j in range(N):
        dp[j][i]=dp[P[j]-1][i-1]+C[P[j]-1]
        if ans<dp[j][i]:
            ans=dp[j][i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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


max_points = []
heapq.heapify(max_points)
for start_point in range(1, N+1):
    flg1 = False
    flg2 = False
    C_point = 0
    max_point = []
    heapq.heapify(max_point)
    now_point = start_point
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        
        heapq.heappush(max_point, -C_point)
#        max_point.append(C_point)
        now_point = next_point
    
        if next_point == start_point:
            flg1 = True
            l = _ + 1
            last_point = C_point
            if C_point > 0:
                flg2 = True
            break
        
    if flg1 and flg2:
#        print("l",l)
        q, r = divmod(K, l)
#        print(q,r)
        now_point = start_point
        C_point = 0
        for _ in range(r+l):
            next_point = Ps[now_point-1]
            C_point += Cs[next_point-1]
            ins = last_point * (q-1) + C_point
            heapq.heappush(max_point, -ins)
#            max_point.append(ins)
            
            now_point = next_point        
#    print("2nd", max_point)
    max_point_ = heapq.heappop(max_point)
    heapq.heappush(max_points, max_point_)
#    max_points.append(max(max_point))
    
print(-heapq.heappop(max_points))
#print(max(max_points))

Submission status: Time Limit Exceeded

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()))
ANS=-float('inf')
for i in range(n):
    snp=P[i]
    r=C[snp]
    L=[r]
    c=0
    np=P[snp]
    while True:
        if c==k-1:
            ANS=max(max(L),ANS)
            break
        if np==snp:
            y=k%(c+1)
            m=k//(c+1)
            if y==0:
                ANS=max(max(L),max(L)+(m-1)*L[-1],ANS)
                break
            else:
                ANS=max(max(L),max(max(L[:y]),0)+m*L[-1],ANS)
                break
        r+=C[np]
        L.append(r)
        np=P[np]
        c+=1
print(ANS)

Submission status: Time Limit Exceeded

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

def mymax(max_variable, candidate):
    if max_variable is None:
        return candidate
    else:
        return max(max_variable, candidate)

max_cost = None
for start in range(n):
    seen = []
    next_ = p[start]
    cost_sum = []
    cost = 0
    while next_ != start:
        seen.append(next_)
        cost += c[next_]
        cost_sum.append(cost)
        next_ = p[next_]

    seen.append(start)
    cost += c[start]
    cost_sum.append(cost)

    l = len(seen)
    s = cost_sum[-1]
    for end in range(len(seen)):
        moves = end + 1
        remain_moves = k - moves
        if remain_moves < 0:
            continue
        cand_cost = cost_sum[end] + max(0, s) * int(remain_moves / l)
        max_cost = mymax(max_cost, cand_cost)
print(max_cost)

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()))
AllCList = []
SamList = []
for s in range(0, N):#配列のインデックスでループ
    i = s
    count = 1
    PList = []
    CList = []
    while i < N and count <= K:
        CList.append(C[i])
        i = P[i]-1
        count += 1
    AllCList.append(CList)

for t in range(0, N):
    for i in range(1, len(AllCList[t])+1):
        SamList.append(sum(AllCList[t][0:i]))

print(max(SamList))

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource
sys.setrecursionlimit(10000)
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
result=-10000000000
for i in range(1,n+1):
    m=find(i,i,n,c[p[i-1]-1],0,0,0)
    if m[2]>=k:
        m=find(i,i,k,c[p[i-1]-1],0,0,0)
        if m[0]>result:
            result=m[0]
    elif m[1]<=0:
        if m[0]>result:
            result=m[0]
    else:
        w=k%m[2]
        if w==0:
            w=m[2]
        spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
        if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>result:
            result=m[1]*(k-w)//m[2]+spe
        elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>result:
            result=m[1]*((k-w)//m[2]-1)+m[0]
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
p=[int(i)-1for i in input().split()]
c=list(map(int,input().split()))
ans=-10**9
for i in range(n):
    start=i
    cycle=[0]
    for _ in range(n):
        i=p[i]
        cycle+=[cycle[-1]+c[i]]
        if i==start:break
    S,L=cycle[-1],len(cycle)-1
    if S<=0:ans=max(ans,max(cycle[1:k+1]))
    else:ans=max(ans,max(0,k//L-1)*S+max(max(cycle[:k+1]),max(cycle[:k%L+1])+S*(k>L))) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource
sys.setrecursionlimit(10000)
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
kara=[-10000000000]
for i in range(1,n+1):
    m=find(i,i,n,c[p[i-1]-1],0,0,0)
    if m[2]>=k:
        m=find(i,i,k,c[p[i-1]-1],0,0,0)
        if m[0]>kara[0]:
            kara[0]=m[0]
    elif m[1]<=0:
        if m[0]>kara[0]:
            kara[0]=m[0]
    else:
        w=k%m[2]
        if w==0:
            w=m[2]
        spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
        if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>kara[0]:
            kara[0]=m[1]*(k-w)//m[2]+spe
        elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>kara[0]:
            kara[0]=m[1]*((k-w)//m[2]-1)+m[0]
print(kara[0])

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()))
for i in range(n):
    p[i]-=1
ans=-10**18

for si in range(n):
    score=[]
    x=si
    while(1):
        x=p[x]
        score.append(c[x])
        if(x==si):
            break
    l=len(score)
    accum=[score[0]]
    for i in range(1,l):
        accum.append(score[i]+accum[i-1])
    total=sum(score)
    z=k//l
    if(total>0):
        for i in range(l):
            if(((z-1)*l+i)>=0):
                tmp=accum[i]+total*(z-1)
                ans=max(ans,tmp)
            if((z*l+i)<k):
                tmp=accum[i]+total*z
                ans=max(ans,tmp)
    else:
        for i in range(l):
            if(i<k):
                tmp=accum[i]
                ans=max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = min(C)
for i in range(N):
  score = 0
  pos = i+1
  #print(i, score, pos)
  for j in range(1, K+1):
    #print(j)
    p_ = P[pos-1]
    score += C[p_-1]
    pos = p_
    #print('score', score)
    if(ans < score):
      ans = score

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
from typing import List

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


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

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

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

    return ans


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

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

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

            K = K % N + N

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

            ret += cnt * B[N]

    return ret

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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase

import math
def main():
    
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))
    maxv = -math.inf
    m  = -math.inf
    for i in range(n):
        count = 0
        it = i
        
        for j in range(k):
            
            count+=c[p[it]-1]
            it = p[it]-1
            m = max(m,count)
        maxv = max(maxv,m)
        
    print(maxv)
     
    
        
    
    
            
        
    

##
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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

# endregion



import collections
if __name__=='__main__':
    main()
##    
##

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(" ")))
maxscore = -float("inf")
for i0 in range(n):
    i = i0
    score = 0
    for t in range(k):
        i = p[i] - 1
        score += c[i]
        maxscore = max(maxscore, score)
print(maxscore)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
    
visited = [False] * n
ans = max(c)

for i in range(n):
    if visited[i]:
        continue
    arr = []
    u = i
    while not visited[u]:
        arr.append(c[u])
        visited[u] = True
        u = p[u]
    s = sum(arr) * (k // len(arr))
    rem = k % len(arr)
    arr += arr
    for f in range(len(arr) // 2):
        ans = max(ans, s + sum(arr[f:f + rem]))
        for g in range(f + 1, len(arr) + 1):
            if g - f > k:
                break
            ans = max(ans, sum(arr[f:g]))
print(ans)

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=[]
for i in range(1,N+1):
    point=0
    add=i
    ans1=[]
    for _ in range(K):
        add=P[add-1]
        point+=C[add-1]
        ans1.append(point)
    ans.append(max(ans1))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def d_moving_piece():
    N, K = [int(i) for i in input().split()]
    P = [int(i) - 1 for i in input().split()]  # マスの番号は 0-indexed とする
    C = [int(i) for i in input().split()]

    # 順列をサイクルごとに分解
    is_visited = [False] * N
    cycles = []  # サイクルごとのスコアを記録
    for i in range(N):
        if is_visited[i]:
            continue

        current = i
        t = []
        while not is_visited[current]:
            is_visited[current] = True
            t.append(C[current])
            current = P[current]
        cycles.append(t)

    ans = -float('inf')
    for s in cycles:
        m = len(s)

        # サイクルを 2 周したものの累積和
        total = [0] * (2 * m + 1)
        for i in range(2 * m):
            total[i + 1] = total[i] + s[i % m]

        reminder = [-float('inf')] * m  # [r]: 連続する r 個の和の最大値
        for i in range(m):
            for j in range(m):
                reminder[j] = max(reminder[j], total[i + j] - total[i])

        # 「余り」の長さで場合分け
        for r in range(m):
            if r > K:
                continue  # 移動できる回数より多く動いたことになり、矛盾

            q = (K - r) // m  # この回数だけサイクルを 1 周する
            if r == 0 and q == 0:
                continue  # 動いていないので、除外

            if total[m] > 0:
                # 周回したほうが得なので、可能な限り周回する
                ans = max(ans, reminder[r] + total[m] * q)
            elif r > 0:
                # 周回すると損なので、必要なだけ (r 回) 移動したら終わる
                ans = max(ans, reminder[r])
    return ans

print(d_moving_piece())

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=-float("inf")

#数列内の周期とスコアを取る
#sをスタート地点とする
for s in range(n):
  #累積輪の数列、各点のスコアの列ではない
  sum=[]
  #xを現在の座標とする
  x=p[s]-1 #初期位置
  sum.append(c[x]) #1回目の移動のスコアを追加？

  #2回目以降スタートに戻るまで
  while True:
    x=p[x]-1
    sum.append(sum[-1]+c[x])
    if x==s:
      break
  
  if k<=len(sum):
    #sumの長さはそのまま移動階数＝周期になる。移動階数が周期よりも少ない場合
    score=max(sum[:k]) 
    #累積和の最大値

  #1周していく場合
  #1周するけど特典が減る場合
  elif sum[-1]<=0:
    score=max(sum)
  
  #1周して特典が増えるとき
  else:
    score1=sum[-1]*(k//len(sum) - 1)
    score1+=max(sum)

    score2=sum[-1]*(k//len(sum))
    r=k%len(sum)

    if r!=0:
      score2+=max(0,max(sum[:r]))
    
    score=max(score1, score2)

  ans=max(ans, score)

print(ans)

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=-1e18

#数列内の周期とスコアを取る
#sをスタート地点とする
for s in range(n):
  #累積輪の数列、各点のスコアの列ではない
  sum=[]
  #xを現在の座標とする
  x=p[s]-1 #初期位置
  sum.append(c[x]) #1回目の移動のスコアを追加？

  #2回目以降スタートに戻るまで
  while True:
    x=p[x]-1
    sum.append(sum[-1]+c[x])
    if x==s:
      break
  
  if k<=len(sum):
    #sumの長さはそのまま移動階数＝周期になる。移動階数が周期よりも少ない場合
    score=max(sum[:k]) #累積和の最大値

  #1周していく場合
  #1周するけど特典が減る場合
  elif sum[-1]<=0:
    score=max(sum)
  
  #1周して特典が増えるとき
  else:
    score1=sum[-1]*(k//len(sum) - 1)
    score1+=max(sum)

    score2=sum[-1]*(k//len(sum))
    r=k%len(sum)

    if r!=0:
      score2+=max(0,max(sum[:r]))
    
    score=max(score1, score2)

  ans=max(ans, score)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


class Solution:
    def find_loop(self, idx):
        self.st.append(idx)
        self.vis[idx] = True
        
        ndx = self.parr[idx]
        if not self.vis[ndx]:
            self.find_loop(ndx)

    def dp(self, idx, k):
        if k == 0:
            self.rcd[idx][k] = 0
            return 0
        elif self.rcd[idx][k] != -1:
            return self.rcd[idx][k]
        else:
            maxv = max(0, self.dp(self.parr[idx], k - 1) + self.carr[self.parr[idx]])
            self.rcd[idx][k] = maxv
            return maxv

    def run(self):
        self.n, self.k = map(int, input().split())
        self.parr = list(map(int, input().split()))
        self.carr = list(map(int, input().split()))

        # make sure parr is 0-indexed
        self.parr = [val - 1 for val in self.parr]

        self.cycle_size = [-1 for _ in range(self.n)]
        self.cycle_sum = [0 for _ in range(self.n)]
        self.vis = [False for _ in range(self.n)]
        
        # find out the size of closed loop
        for idx in range(self.n):
            while self.cycle_size[idx] < 1:
                pass
            if not self.vis[idx]:
                self.st = []
                self.find_loop(idx)
                sval = sum([self.carr[jdx] for jdx in self.st])
                for jdx in self.st:
                    self.cycle_size[jdx] = len(self.st)
                    self.cycle_sum[jdx] = max(0, sval)

        # print(self.cycle_size)
        # print(self.cycle_sum)

        # try starting point at different index
        self.rcd = [[-1 for _ in range(self.n + 1)] for _ in range(self.n)]
        maxv = -sys.maxsize
        for idx in range(self.n):
            maxv = max(
                maxv,
                self.dp(self.parr[idx], (self.k - 1) % self.cycle_size[idx]) + self.carr[self.parr[idx]] + (self.k - 1) // self.cycle_size[idx] * self.cycle_sum[idx]
            )
        print(maxv)

if __name__ == '__main__':
    solution = Solution()
    solution.run()

Submission status: Time Limit Exceeded

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

r = [None for _ in range(n)]

for i in range(n):
    a = c[p[i] - 1]
    r[i] = a

maximum = -1 * (10 ** 9) - 1

for i in range(n):
    next = p[i] - 1
    tMax = -1 * (10 ** 9) - 1
    total = 0
    
    for j in range(m):
        total = total + r[next]
        tMax = max(total, tMax)
        next = p[next] - 1
        
    maximum = max(maximum, tMax)
        
print(maximum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate 
#acumulate [a[0], a[0]+a[1], a[0]+...]
 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(ans)