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

def sim(start,mx): # simulate mx step from start, returns max_score
    if mx==0:
        return 0
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]

    while True:
        nxt=p[nxt]-1
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==mx:
            break

    return max(p_lis)

visited_p=set() # already checked flag
cycle_score=[] # cycle loop score
cycle_points=[]
now_cycle=0

for i in range(n):
    if i in visited_p:
        continue
    visited_p.add(i)
    now_p=0
    nxt=p[i]-1
    visited=set()
    while True:
        nxt=p[nxt]-1
        visited_p.add(nxt)
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    cycle_score.append(now_p)
    cycle_points.append(list(visited))

ans=-float('inf')

for c_num in range(len(cycle_score)):
#    print(c_num,cycle_score[c_num],cycle_points[c_num])
    cycle_len=len(cycle_points[c_num])
    for start in cycle_points[c_num]:

        if cycle_score[c_num]<0: # no loop, just check min(loop_len,k)
            score = sim(start,min(cycle_len,k))
            ans=max(ans,score)

        else: # loop as many as possible
            loop_num = k % cycle_len
            nokori=k-(loop_num*cycle_len)

            score = sim(start,nokori) + loop_num*cycle_score[c_num]
            ans=max(ans,score)

print(ans)

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)
 
        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(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
ans = -10**18
for i in range(n):  # 開始点を全通り
  x = i
  sc = []
  tot = 0
  while True:
    x = P[x]
    sc.append(C[x])
    tot += C[x]
    if x == i: break  # 開始点に戻ってきて循環に入った
  #print(i, sc, tot)
  l = len(sc)
  cum = 0
  for j in range(l):  # 何ステップ進むとよいか
    cum += sc[j]
    if j+1 > k: break  # k=1は最初の1周のみ
    val = cum  # 循環ループ考慮するスコア
    if tot > 0:
      cyc = (k-(j+1)) // l  # 残りステップで循環できる数
      val += tot * cyc
    ans = max(ans, val)
    #print(j, cum, cyc, val)
print(ans)

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

res = -10**10

for i in range(N):
    j = i
    total = 0
    loop_values = []

    while True:
        j = P[j] - 1
        loop_values.append(C[j])
        total += C[j]
        if j == i:
            break
    
    loop_length = len(loop_values)
    point_sum = 0

    for j in range(loop_length):
        point_sum += loop_values[j]
        result_cand = point_sum

        if j+1 > K:
            break

        if total > 0:
            loop_num = (K - j - 1) // loop_length
            result_cand += total * loop_num
        
        if res < result_cand:
            res = result_cand

print(res)

Submission status: Time Limit Exceeded

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

    par = [i for i in range(N)]
    size = [1 for i in range(N)]

    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            size[x] = size[par[x]]
            return par[x]

    def same(x, y):
        return find(x) == find(y)

    def union(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if size[x] < size[y]:
            x, y = y, x
        size[x] += size[y]
        par[y] = x

    def get_size(x):
        return size[find(x)]

    for i, p in enumerate(P):
        union(i, p)

    cycle = [0]*N
    cycle_len = [0]*N
    dist = [[[0, 0] for _ in range(N)] for _ in range(N)]
    for i in range(N):
        p = find(i)
        cycle[p] += C[i]
        cycle_len[p] += 1

    for i in range(N):
        p = find(i)
        pre = i
        for _ in range(cycle_len[p]-1):
            dist[i][P[pre]][0] = dist[i][pre][0] + C[P[pre]]
            dist[i][P[pre]][1] = dist[i][pre][1] + 1
            pre = P[pre]
    ans = -(10**10)
    for i in range(N):
        for j in range(N):
            if i == j or not same(i, j):
                continue
            p = find(i)
            s, d = dist[i][j]
            cur = s
            if cycle[p] >= 0:
                if K - d > 0:
                    cur += cycle[p]*((K-d)//cycle_len[p])
            ans = max(ans, cur)
    print(ans)
    # for i in range(N):
    #     print(dist[i])
    # print(cycle)


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

#if max(C) < 0:
#  print(min(C))
#  quit()
  
A = [0] * N

for i in range(N):#スタート地点
  q = [i + 1]
  now = i + 1
  score = []
  point = 0
  T = True
  while T:
    now = P[now - 1]
    point += C[now - 1]
    score.append(point)
    if now in q:
      T = False
    else:
      q.append(now)
  #print(q)#ループのルート
  #print(score)#ループ中のスコア
  if len(q) >= K:#一周未満
    score = score[:K]
    A[i] = max(score)
  else:#一周以上
    if score[-1] <= 0:#周回しない方がいいケース
      A[i] = max(score)
    else:#周回すべきケース
      ll = -float("inf")
      for j in range(len(q)):
        roop = int((K - (j + 1)) / len(q))
        ll = max(ll, roop * score[-1] + score[j])
        #print(i, ll, roop * score[-1] + score[j])
      A[i] = ll
      
      
#print(A)      
print(max(A))

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

max_score = -float('inf')

for i in range(n):
    loop_score_array = []
    loop_score = 0
    loop_len = 0
    pos = i
    while True:
        pos = p[pos] - 1
        loop_score += c[pos]
        loop_score_array.append(loop_score)
        loop_len+=1
        if pos == i:
            break
    for i, score in enumerate(loop_score_array):
        if k-i-1 < 0:
            continue
        loop_num = (k-i-1)//loop_len
        score_sum = score + max(0, loop_score)*loop_num
        max_score = max(score_sum, max_score)
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
p = list(int(x)-1 for x in input().split())
c = list(map(int, input().split()))
score = -10**9
his = [0]*(n+1)
for i in range(n):
  rec = np.array([0])
  here = i
  cnt = 0
  for _ in range(k):
    here = p[here]
    rec = np.append(rec,c[here])
    cnt += 1
    if here == i:
      break
  rec = np.cumsum(rec)
  s = max(rec[1:])
  ps = rec[-1]*(k//cnt)+max(rec[0:k%cnt+1])
  s = max(ps,s)
  score = max(s,score)
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


def main():
    N, K = NMI()
    P = NLI()
    P = [p-1 for p in P]
    C = NLI()

    seen = [0] * N
    loops = []
    for i in range(N):
        if seen[i] == 1:
            continue
        now = i
        now_loop = [now]
        now_cost = C[now]
        while True:
            seen[now] = 1
            goto = P[now]
            if seen[goto] == 1:
                break
            now_loop.append(goto)
            now_cost += C[goto]
            now = goto
        loops.append([now_loop, now_cost])

    ans = -float("inf")
    for loop, cost in loops:
        C_cum = make_cumulative([C[p] for p in loop])

        for i, start in enumerate(loop):
            for j, end in enumerate(loop):
                if i == j:
                    base = cost
                    moved = len(loop)
                elif i < j:
                    base = C_cum[j] - C_cum[i]
                    moved = j - i
                else:
                    base = cost - (C_cum[i] - C_cum[j])
                    moved = len(loop) + j - i

                if moved > K:
                    continue

                if cost > 0:
                    tmp_K = K - moved
                    num_loop = tmp_K // len(loop)
                    tmp_ans = num_loop * cost + base
                else:
                    tmp_ans = base

                ans = max(ans, tmp_ans)

    print(ans)



if __name__ == "__main__":
    main()

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

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    left = k
    for j in range(n):
        now = p[now]
        score += c[now]
        left -= 1
        if left >= 0:
            times = left // score_cnt[now][1]
            score_loop = score + times * score_cnt[now][0]
            ans = max(ans, score, score_loop)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    P = [i-1 for i in P]
    ans = -1e19

    for si in range(N):
        index = si
        cycle =[]
        total = 0
        while True:
            index = P[index]
            cycle.append(C[index])
            total = total + C[index]
            if index == si:
                break
        cycle_length = len(cycle)
        count = 0
        for i in range(cycle_length):
            count  = count + cycle[i]
            if i+1 > K:
                break
            num = count
            if total > 0:
                cnt = (K - (i+1)) // cycle_length
                num = num + cnt*total
            ans = max(ans, num)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def main():
    cells, can_jump = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        position = start
        while True:
            route.append(score_on[position])
            position = jumps_from[position]
            if position == start:  # Looped
                break

        length = len(route)
        total = sum(route)
        for jumping, accum_candidate in enumerate(accumulate(route)):
            jumping += 1
            if jumping > can_jump:
                break
            if total > 0:
                accum_candidate += total * ((can_jump - jumping) // length)
            ans = max(ans, accum_candidate)
    return ans


if __name__ == '__main__':
    ans = main()
    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()))

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from numba import jit

def main(N, K, plist, slist, max_score):
    for start in range(N):
        total_score_in_loop = 0
        now = start
        score_loop = []
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        score_rem = 0
        loop_score = 0
        for index, score in enumerate(score_loop, start=1):
            score_rem += score
            if total_score_in_loop > 0:
                loop_score = total_score_in_loop * ((K-index) // len(score_loop))
            if max_score < score_rem+loop_score:
                max_score = score_rem+loop_score
    print(max_score)

if __name__ == '__main__':
    N, K = map(int, input().split())
    plist = np.array([i - 1 for i in map(int, input().split())])
    slist = np.array(list(map(int, input().split())))
    max_score = -10**18
    main(N, K, plist, slist, max_score)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
per=LI()
for i in range(n):
    per[i]-=1
points=LI()
ans=-inf
for i in range(n):
    val=0
    #res=[0 for j in range(n+1)]
    res=[]
    pos=per[i]
    inipos=per[i]
    count=0
    while True:
        val+=points[pos]
        pos=per[pos]
        if len(res)==0:
            res.append(val)
        else:
            res.append(max(res[-1],val))
        #res[count]=max(val,res[count-1])
        count+=1
        if pos==inipos:
            break
    loop=(val,count)
    #print(loop)
    #print(res)
    for x in range(len(res)):
        if loop[0]<=0:
            ans=max(ans,res[x])
        else:
            ans=max(ans,res[x]+loop[0]*((k-x-1)//loop[1]))
print(ans)

Submission status: Time Limit Exceeded

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

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

max_points = []
for now_point in range(2, N+1):
    max_point = -float('inf')
    C_point = 0
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        if C_point > max_point:
            max_point = C_point
        now_point = next_point
    
    max_points.append(max_point)

print(max(max_points))

Submission status: Time Limit Exceeded

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

def main():
    plist = [i - 1 for i in map(int, input().split())]
    slist = list(map(int, input().split()))
    max_score = -math.inf
    for start in range(N):
        total_score_in_loop = 0
        now = start
        score_loop = []
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        score_rem = 0
        loop_score = 0
        for index, score in enumerate(score_loop, start=1):
            score_rem += score
            if total_score_in_loop > 0:
                loop_score = total_score_in_loop * ((K-index) // len(score_loop))
            max_score = max(max_score, score_rem+loop_score)
    print(max_score)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def main():
    n, k = map(int, input().split())
    p_array = list(map(int, input().split()))
    c_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=map(int,input().split())
p=list(map(int,input().split()))
b=list(map(int,input().split()))
a=[0]*n
if sum([b[i]<=0 for i in range(n)])==n:
    print(max(b))
    exit()
for i in range(n):
    if a[i]!=0:
        continue
    c=[i]
    while len(c)==len(set(c)):
        c.append(p[c[-1]]-1)
    c.pop()
    lc=len(c)
    score=sum([b[i] for i in c])
    a[i]=[score,lc]
ans=0
for i in range(n):
    ns=0
    kk=k%a[i][1]
    if a[i][0]>0:
        ns+=a[i][0]*(k//a[i][1])
    for j in range(kk):
        i=p[i]-1
        ns+=b[i]
        ans=max(ns,ans)
for i in range(n):
    ns=0
    if k//a[i][1]==0:
        continue
    if a[i][0]>0:
        ns+=a[i][0]*(k//a[i][1]-1)
    for j in range(a[i][1]):
        i=p[i]-1
        ns+=b[i]
        ans=max(ns,ans)
print(ans)

Submission status: Time Limit Exceeded

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

plist = [i - 1 for i in map(int, input().split())]
slist = list(map(int, input().split()))
max_score = -math.inf
for start in range(N):
    total_score_in_loop = 0
    now = start
    score_loop = []
    while True:
        now = plist[now]
        total_score_in_loop += slist[now]
        score_loop.append(slist[now])
        if now == start:
            break
    score_rem = 0
    loop_score = 0
    for index, score in enumerate(score_loop, start=1):
        score_rem += score
        if total_score_in_loop > 0:
            loop_score = total_score_in_loop * ((K-index) // len(score_loop))
        max_score = max(max_score, score_rem+loop_score)
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    # グルーピング
    import copy
    P2 = set(P)
    Group = []
    while len(P2)>0:
        temp = list(P2)[0]
        tempGroup = []
        while temp in P2:
            tempGroup.append(temp)
            P2.remove(temp)
            temp = P[temp-1]
        Group.append(tempGroup)
    Point = []
    for x in Group:
        tempPoint = []
        for p in x:
            tempPoint.append(C[p-1])
        Point.append(tempPoint)

    #print(Group)
    #print(Point)

    max00 = -10**9
    for x in Point:
        sumx = sum(x)
        tempx = copy.copy(x)
        tempx.extend(x)
        lenx = len(x)
        max0 = -10**9
        dp = [0]*lenx
        if sumx <= 0 or K < lenx:
            for i in range(min(lenx-1,K)):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                max0 = max(max0,max(dp))
                #print(dp)
        else:
            K2 = K % lenx
            SN = int(K/lenx)
            for i in range(lenx):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                #print(dp)
                if i < K2:
                    max0 = max(max0,max(dp) + sumx*SN)
                    #print(max0)
                else:
                    max0 = max(max0,max(dp) + sumx*(SN-1))
        max00 = max(max00,max0)
    print(max00)

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

# グルーピング
import copy
P2 = copy.copy(P)
Group = []
while len(P2)>0:
    temp = P2[0]
    tempGroup = []
    while temp in P2:
        tempGroup.append(temp)
        P2.remove(temp)
        temp = P[temp-1]
    Group.append(tempGroup)
Point = []
for x in Group:
    tempPoint = []
    for p in x:
        tempPoint.append(C[p-1])
    Point.append(tempPoint)

#print(Group)
#print(Point)

max00 = -10**9
for x in Point:
    sumx = sum(x)
    tempx = copy.copy(x)
    tempx.extend(x)
    lenx = len(x)
    max0 = -10**9
    dp = [0]*lenx
    if sumx <= 0 or K < lenx:
        for i in range(min(lenx-1,K)):
            for j in range(lenx):
                dp[j] = dp[j] + tempx[j+i]
            max0 = max(max0,max(dp))
            #print(dp)
    else:
        K2 = K % lenx
        SN = int(K/lenx)
        for i in range(lenx):
            for j in range(lenx):
                dp[j] = dp[j] + tempx[j+i]
            #print(dp)
            if i < K2:
                max0 = max(max0,max(dp) + sumx*SN)
                #print(max0)
            else:
                max0 = max(max0,max(dp) + sumx*(SN-1))
    max00 = max(max00,max0)
print(max00)

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")
for start in range(N):
    x = start
    cyc_score = []
    total_cyc_score = 0
    while True:
        x = P[x]-1
        cyc_score.append(C[x])
        total_cyc_score += C[x]
        if x == start: # 周期を検出
            break
    t = 0
    for i in range(len(cyc_score)):
        t += cyc_score[i]
        if i + 1 > K: break
        now_score = t
        if total_cyc_score > 0:
            e = int((K - i - 1) / len(cyc_score))
            now_score += total_cyc_score * e
        ans = max(ans, now_score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

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

cycles = []

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説放送

def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(i) for i in raw_input().split()]
p=[int(i)-1 for i in raw_input().split()]
c=[int(i) for i in raw_input().split()]
maxx=-10**18
for i in range(n):
  ct=0;j=0;pos=i
  while j<k:
    ct+=c[pos]
    pos=p[pos]
    j+=1
    maxx=max(maxx,ct)
print maxx

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))

ans = -float("inf")

for st in range(N):
  S = []
  temp = P[st]
  S.append(C[temp])
  while temp != st:
    temp = P[temp]
    S.append(S[-1] + C[temp])
  cnt = len(S)
  loop, k = divmod(K, cnt)
  point = 0
  if S[-1] >= 0:
    if k == 0:
      loop -= 1
      k += cnt
    point += S[-1] * loop
  else:
    if loop >= 1:
      k = cnt
  ans = max(ans, point + max(S[:k]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

G = [0] * N

d = -10 ** 9
j = 0

i = 0
s = 0

for l in range(N):
    s = 0
    j = l
    for i in range(K):
        s += C[j]        
        
        if s > d:
            d = s

        j = P[j] - 1
        if j == l and s > 0:
            if K-i > i:
                i = i * (K // i)

        elif j == l:
            break


print(d)

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

vis = [False] * N
ans = [-float("inf")] * N

for root in range(N):
  vis[root] = True
  
  cycle = [root]
  costs = [C[root]]
  u = P[root]
  vis[u] = True
  
  while u != root:
    cycle.append(u)
    costs.append(C[u])
    u = P[u]
    vis[u] = True

  L = len(cycle)
  S = sum(costs)
  for i, v in enumerate(cycle):
    cnt = 0
    for step in range(1, min(L, K) + 1):
      cnt += costs[(i + step) % L]
      val1 = cnt
      val2 = cnt + (K - step) // L * S
      ans[v] = max(ans[v], val1, val2)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))

# 重み付き有向グラフ
edges = [[] for _ in range(N)]
for i in range(N):
    edges[i].append((P[i]-1, C[i]))

# DFSで閉路と経路の最大取得スコアを調査
ans = -float("inf")
for i in range(N):
    q = deque([(i, 0, 0)])
    cycle_score = -1
    cycle_count = -1
    cycle_start = None
    scores = {} # (score, count)
    while q:
        node1, score, count = q.popleft()
        # print(node1, score, count)
        if K < count:
            break
        if 0 < count: 
            ans = max(ans, score)
        if node1 in scores:
            # 閉路
            if score > 0:
                # print("plus cycle detected")
                # cycle.add((score, count, i))
                cycle_score = score
                cycle_count = count
                cycle_start = node1
            break
        scores[node1] = (score, count)
        # for で回しているが、実際は一択
        for node2, weight in edges[node1]:
            q.appendleft((node2, score + weight, count + 1))

    # cycleを回れる限界の-1から始めて、最大のスコアを算出
    if cycle_start is not None:
        cycle_len = cycle_count - scores[cycle_start][1]
        # print("cycle_len", cycle_len, "cycle_score", cycle_score - scores[cycle_start][0])
        loop = (K - scores[cycle_start][1]) // cycle_len - 1

        count = loop * cycle_len + scores[cycle_start][1]
        score = scores[cycle_start][0] + loop * (cycle_score - scores[cycle_start][0])
        # print(count, score, loop)
        q = deque([(cycle_start, score, count)])
        while q:
            node1, score, count = q.popleft()
            # print(node1, score, count)
            if count > K:
                break

            ans = max(ans, score)
            for node2, weight in edges[node1]:
                q.appendleft((node2, score + weight, count + 1))

print(ans)

Submission status: Time Limit Exceeded

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

ans = -float('inf')

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

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

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