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: Accepted

Solution code:
N, K = map(int, input().split())
P, C = [list(map(int, input().split())) for _ in range(2)]
c = [1] * N
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
ans = max(C)
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        m[i][c[i]] = m[i][c[i]-1] + C[P[j]-1]
    if m[i][c[i]] > 0:
        ans = max(ans, m[i][c[i]] * (K//c[i]-1) + max(m[i] + [m[i][c[i]] + m[i][j+1] for j in range(K%c[i])]))
    else:
        ans = max(ans, max(m[i][1:min(c[i],K)+1]))
print(ans)

Submission status: Accepted

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

    used = [0]*N
    ans = -float('inf')
    for x in range(N):
        if used[x]:
            continue
        used[x] = 1
        Q = [C[x]]

        while not used[P[x]]:
            x = P[x]
            used[x] = 1
            Q.append(C[x])

        ret = check(Q, K)
        if ret > ans:
            ans = ret

    print(ans)


def check(Q, K):
    length = len(Q)
    tot = sum(Q)
    Q *= 2
    ret = -float('inf')
    for i in range(length):
        accum = 0
        for k in range(1, min(K, length)+1):
            accum += Q[i+k]
            if tot > 0:
                ret = max(ret, accum + tot * ((K-k)//length))
            else:
                ret = max(ret, accum)
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

INF = float('inf')

max_points = []
for i in range(N):
    max_point = -INF
    visit = [0] * N
    visit[i] = 1
    S = [0]
    pos = P[i]
    loop = 0  # P は順列なので、すでにvisitした点に戻ったとき、loopが位数となる
    while True:
        if visit[pos] == 0:
            visit[pos] = 1
            S.append(S[loop] + C[pos])
            pos = P[pos]
            loop += 1
        else:
            S.append(S[loop] + C[pos])
            pos = P[pos]
            loop += 1
            break

    loop_point = S[loop]
    # print(loop_point)
    # print(i, visit)
    if loop > K:
        max_point = max(S[1:K+1])
    else:
        if loop_point > 0:
            loop_num = K // loop
            max_point = max(max_point, loop_point * loop_num + max(S[:(K%loop)+1]))
            max_point = max(max_point, loop_point * (loop_num-1) + max(S[1:loop]))
        else:
            max_point = max(S[1:loop+1])

    max_points.append(max_point)

print(max(max_points))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    ans = -INF

    for i in range(N):
        memo = [0] * (N+1)
        j = 0
        p = i
        while j < N:
            memo[j+1] = memo[j] + C[p]
            p = P[p] - 1
            j += 1
            if p == i:
                break
        tans =-INF
        if memo[j] > 0:
            for k in range(j):
                q = (K-k-1) // j
                tans = max(tans, memo[k+1] + memo[j] * q)
        else:
            for k in range(min(K, j)):
                tans = max(tans, memo[k+1])

        ans = max(ans, tans)
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

ans = -float('inf')
for s in range(N):
    S = []
    i = P[s] - 1
    S.append(C[i])
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Submission status: Accepted

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

n, k = list(map(int, input().split()))
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))

best = max(c)
for i in range(n):
    curr = 0
    score = [0]
    start = i
    while p[start] != i:
        start = p[start]
        curr += c[start]
        score.append(curr)
    cycle_score = score[-1] + c[i]
    cycle_len = len(score)

    for j in range(cycle_len):
        if j <= k and j != 0:
            # if j <= k:
            cycles = (k-j)//cycle_len
            thing = score[j] + max(0, cycle_score) * cycles
            best = max(best, thing)
        elif j == 0 and k >= cycle_len:
            thing = cycle_score * k//cycle_len
            best = max(best, thing)
print(best)

Submission status: Accepted

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

ans = -float('inf')
for s in range(N):
    S = []

    S.append(C[s])
    i = P[s] - 1

    while i != s:
        S.append(S[-1] + C[i])
        i = P[i] - 1
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
from collections import deque
toku=[0]*(n+1)
for i in range(1,n+1):
  ans=[0]
  d=deque()
  visit=[0]*(n+1)
  d.append(i)
  while d:
    now=d.pop()
    if visit[now]==0:
      visit[now]=1
      ans.append(ans[-1]+c[p[now-1]-1])
      d.append(p[now-1])
  syuki=sum(visit)
  if ans[-1]>=0:
    if k%syuki==0:
      toku[i]=max((k//syuki)*ans[-1],(k//syuki-1)*ans[-1]+max(ans))
      
    else:
      toku[i]=(k//syuki)*ans[-1]+max(ans[1:k%syuki+1])
  else:
    if k//syuki==0:
      toku[i]=max(ans[1:k%syuki+1])
    else:
      toku[i]=max(ans[1:])
print(max(toku[1:]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
P = LIST()
C = LIST()

loop_point = [0]*N
loop_count = [0]*N
searched = [0]*N

for i in range(N):
    if searched[i]:
        continue
    idx = i
    points = 0
    cnt = 0
    while not searched[P[idx]-1]:
        idx = P[idx]-1
        searched[idx] = 1
        cnt += 1
        points += C[idx]
    loop_count[i] = cnt
    loop_point[i] = points
    while not loop_point[P[idx]-1]:
        idx_next = P[idx]-1
        loop_count[idx_next] = loop_count[idx]
        loop_point[idx_next] = loop_point[idx]
        idx = idx_next

ans = -INF
for i in range(N):
    p = 0
    idx = i
    loop = loop_point[i] > 0 and K > loop_count[i]
    for j in range(1, min(K+1, loop_count[i]+1)):
        idx = P[idx]-1
        p += C[idx]
        if loop:
            final_p = p + loop_point[i]*((K-j)//loop_count[i])
        else:
            final_p = p
        ans = ans if ans > final_p else final_p
print(ans)

Submission status: Accepted

Solution code:
def f(x):
  D=[-1]*(N+1)
  D[x]=0
  S=[None]*(N+1)
  S[x]=0
  ima=x+0
  for count in range(1, K+1):
    if D[P[ima]]<0:
      D[P[ima]]=count
      S[P[ima]]=S[ima]+C[P[ima]]
      ima=P[ima]+0
    else:
      if S[ima]+C[P[ima]]>S[P[ima]]:
        isshu=count-D[P[ima]]
        atonanshu=max((K-count)//isshu-1, 0)
        atonanho=K-(count+isshu*atonanshu)
        agatta=S[ima]+C[P[ima]]-S[P[ima]]
        S[P[ima]]=S[ima]+C[P[ima]]+agatta*atonanshu
        D[P[ima]]=D[ima]+1
        
        ima=P[ima]+0
        for _ in range(atonanho):
          S[P[ima]]=S[ima]+C[P[ima]]
          D[P[ima]]=D[ima]+1
          ima=P[ima]+0
      break
      
  if D[x]==0:
    S[x]=None
  return max([s for s in S if s is not None])

N, K=map(int, input().split())
P=[None]+list(map(int, input().split()))
C=[None]+list(map(int, input().split()))

print(max([f(x) for x in range(1, N+1)]))

Submission status: Accepted

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 = max(c)
for i in range(n):
    curr = 0
    score = [0]
    posi = i
    while p[posi] != i:
        posi = p[posi]
        curr += c[posi]
        score.append(curr)
    cycle_score = score[-1] + c[i]
    cycle_len = len(score)
    
    for j in range(cycle_len):
        if j <= k and j != 0:
            cycles = (k - j)//cycle_len
            thing = score[j] + max(0, cycle_score) * cycles
            ans = max(ans, thing)
        #Kがサイクルより大きいときの処理をj=0で行う(score[0]は無効なため)
        elif j == 0 and k >= cycle_len:
            thing = cycle_score * k // cycle_len
            ans = max(ans,thing)

print(ans)

Submission status: Accepted

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

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


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


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


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


INF = 1 << 29

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

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


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


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

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

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

    return CONV()


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


sys.setrecursionlimit(200005)


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


def main():

    N,K = isRaw()
    Ps = isRaw()
    Cs = isRaw()
    ans = max(Cs)
    for n in range(N):
        curPos = n
        cycles =[]
        visited = {}
        lastCost = 0
        vidx = 0
        loopStart = -1
        while True:
            visited[curPos] = vidx
            lastCost = lastCost+Cs[curPos]
            cycles.append(lastCost)
            curPos= Ps[curPos]-1
            
            if curPos in visited:
                loopStart = visited[curPos]
                break
        
        c_len = len(cycles)
        c_score = cycles[-1]
        if K>=c_len:
            ans = max(ans,c_score*(K//c_len))
        for c in range(0,min(c_len,K)):
            n_cycle = (K-c-1)//c_len
            score = cycles[c]+max(0,c_score*n_cycle)
            ans = max(score,ans)
    print (ans)

         
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    cycles = []
    memo = [False] * N
    i = 0
    while i < N-1:
        cycle = []
        j = i
        while not memo[j]:
            cycle.append(j)
            memo[j] = True
            j = P[j] - 1
        k = i
        for i in range(k, N):
            if not memo[i]:
                break
        cycles.append(cycle)

    ans = -INF

    for cycle in cycles:
        n = len(cycle)
        # q, r = divmod(K-1, n)
        # r += 1
        memo = [-INF] * n
        for i in range(n):
            s = 0
            for j in range(n):
                s += C[cycle[(i+j)%n]]
                memo[j] = max(memo[j], s)
        tmpmax = -INF
        imax = -1
        if K < n:
            for i in range(K):
                if tmpmax < memo[i]:
                    tmpmax = memo[i]
                    imax = i+1
        else:
            if memo[-1] > 0:
                for i in range(n):
                    q = (K-i-1) // n
                    tmpmax = max(tmpmax, memo[i] + memo[-1] * q)
            else:
                for i in range(n):
                    tmpmax = max(tmpmax, memo[i])

        ans = max(ans, tmpmax)
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

ans = -float('inf')
for i in range(N):
    done = set()
    S = []

    done.add(i)
    S.append(C[i])
    i = P[i] - 1
    while i not in done:
        done.add(i)
        S.append(S[-1] + C[i])
        i = P[i] - 1
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Submission status: Accepted

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):
    if vis[root]:
        continue

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

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        # Rewrite [1, K] as form q * L + r,
        # 0L + 1, 0L + 2, ..., 0L + L
        # 1L + 1, 1L + 2, ..., 1L + L
        # ⋮ 
        # tL + 1, tL + 2, ... 

        # We can ignore 1L + r, 2L + r, ..., (t - 1) * L + r
        # since the total cost of loop is either > 0 or <= 0
        # When > 0, 0L + r < 1L + r < 2L + r < tL + r
        # When <= 0, the answer should be 0L + r

        if S > 0:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                t = (K - rem) // L
                ans[v] = max(ans[v], rem_cost + t * S)
        else:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                ans[v] = max(ans[v], rem_cost)

print(max(ans))

Submission status: Accepted

Solution code:
# D not completed
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

checked_list = [0 for _ in range(N)]
min_INF = -1 * 10 ** 10
max_score = min_INF
for i in range(N):
    if checked_list[i] == 1:
        continue
    posit = i
    loop_list = [posit]
    score_list = []
    for j in range(N):
        posit = P_list[posit] - 1
        if j == 0:
            score_list.append(C_list[posit])
        else:
            score_list.append(score_list[-1] + C_list[posit])
        if posit in loop_list:
            break
        loop_list.append(posit)

    len_loop = len(loop_list)
    max_score_list = max(score_list)
    around_score = score_list[-1]
    temp_score_base = 0
    if around_score > 0 and K // len_loop > 0:
        temp_score_base += (K // len_loop - 1) * around_score
    for k in range(len_loop):
        # print("loop", loop_list)
        # print("score", score_list)
        checked_list[loop_list[k]] = 1
        temp_max_score = temp_score_base
        rest_score = min_INF
        if around_score > 0 and K // len_loop > 0:
            # 最後に1周すべきか
            rest_score = max(max_score_list, max(score_list[:K % len_loop], default=min_INF) + around_score)
            # print(loop_list[k], temp_max_score, K, len_loop, K // len_loop)
        rest_score = max(max(score_list[:min(K, len_loop)]), rest_score)
        temp_max_score = temp_max_score + rest_score
        # print(loop_list[k], temp_max_score, rest_score)
        max_score = max(max_score, temp_max_score)
        # ループ内でずらす
        now_score = score_list.pop(0)
        len_score = len(score_list)
        score_list = [score_list[l] - now_score for l in range(len_score)]
        score_list.append(score_list[-1] + now_score)

print(max_score)

Submission status: Accepted

Solution code:
import sys
from numpy import*
def main(n,k,p,c):
    m=-10**12
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    return m
if sys.argv[-1]=='ONLINE_JUDGE':
  from numba.pycc import CC
  cc=CC('my_module')
  cc.export('main','i8(i8,i8,i8[:],i8[:])')(main)
  cc.compile()
  exit()
from my_module import main
(n,k),p,c=[int_(t.split())for t in open(0)]
print(main(n,k,p,c))

Submission status: Accepted

Solution code:
(n,k),p,c  = [list(map(int, s.split())) for s in open(0)]

pset = set(p)
ans = c[0]
for x in range(1,n+1):
    _sum = [0 for _ in range(2*n)]
    num = 0
    while x in pset:
        pset.remove(x)
        _sum[num + 1] = _sum[num] + c[x-1]
        x = p[x-1]
        num += 1
    if num > 0:
        for i in range(1,num):
            _sum[num + i] += _sum[num] + _sum[i]
        # i == 0
        if k//num > 0:
            tmp = _sum[num] * (k//num)
            if tmp > ans:
                ans = tmp
        for i in range(1, min(k+1,num)):
            base = max(0, _sum[num]) * ((k-i)//num)
            for j in range(num):
                tmp = _sum[j+i] - _sum[j] + base
                if tmp > ans:
                    ans = tmp
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    inf=float("inf")
    n,k=map(int,input().split())
    plst=list(map(int,input().split()))
    clst=list(map(int,input().split()))
    sm=-inf

    seen=[0]*n
    for i in range(n):
        if seen[i] : continue
        pos=i
        work=[]
        while not seen[pos]:
            seen[pos]=1
            work.append(clst[pos])
            pos=plst[pos]-1
        nwork=len(work)
        loop_sum=sum(work)
        work=[0]+list(accumulate(work))
        
        numcut=min(nwork,k)

        for i in range(nwork):
            for j in range(i,i+numcut):
                if j<nwork :
                    smwork=work[j+1]-work[i]
                else :
                    smwork=work[nwork]-work[i]+work[j-nwork+1]
                if loop_sum>0:
                    smwork+=loop_sum*((k-(j+1-i))//nwork) 
                if smwork>sm : sm=smwork

    print(sm)

main()

Submission status: Accepted

Solution code:
# 標準入力
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))

# 0 - indexed 化
for i in range(n):
    p[i] -= 1

ans = -12345678901234567

# 全ての場所からスタートを試す
for st in range(n):
    score = 0
    now = st

    # ループするまで or kまでスコアを計算しans更新
    for i in range(1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)

        # ループしたら
        if now == st:
            # k回までに何回ループできるか計算
            # 最後の一回のループは愚直に計算する（どこに最適があるかわからないため）
            # 最後の一回のループ以外は最適になり得ないので省略しておｋ
            cnt = k//i - 1
            if cnt > 1:
                score *= cnt
                i *= cnt
                ans = max(ans,score)
            break

    # 最後のループ分を愚直に計算
    for j in range(i+1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)
print(ans)

Submission status: Accepted

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 = -12345678901234567
for st in range(n):
    score = 0
    now = st

    # ループするまで or kまで
    for i in range(1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)
        if now == st:
            cnt = k//i - 1
            if cnt > 1:
                score *= cnt
                i *= cnt
                ans = max(ans,score)
            break

    for j in range(i+1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)
print(ans)

Submission status: Accepted

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

import sys


def main():
    # inf = float('inf')              # sys.float_info.max = 1.79e+308
    inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)



    def calc_score(start):
        order = [None] * n
        accum = [None] * n
        order[start] = 0
        accum[start] = 0
        place = start
        cnt = 0
        current_score = 0
        M = -inf

        while cnt < k:
            place = P[place]    # 移動
            cnt += 1    # 移動回数
            current_score += C[place]    # 移動後の index でスコアに追加
            M = max(M, current_score)    # [スタートの次点, 現在地] まで任意の場所をゴールに選ぶときのスコア最大値
            if order[place] is None:
                # 未訪問
                order[place] = cnt
                accum[place] = current_score
            else:
                # 訪問ずみ (loop)
                head_len = order[place]
                loop_len = cnt - head_len
                head_score = accum[place]
                loop_gain = current_score - accum[place]
                if loop_gain <= 0:
                    # debug('encountered loop, but non-positive loop.')
                    return M
                else:
                    # debug('encountered positive loop.')
                    loop_times, res = divmod(k - head_len, loop_len)
                    # place からスタートして "0 以上" res 以下だけ進むときの
                    res_score = 0    # 稼ぐ最大スコア
                    tmp_score = 0    # 現在の累積スコア
                    tmp_place = place    # 現在地
                    for _ in range(res):
                        tmp_place = P[tmp_place]
                        tmp_score += C[tmp_place]    # 移動後の index でスコアに追加
                        res_score = max(res_score, tmp_score)
                    # 限界まで loop を回した上で 0 ~ res だけ貪欲に稼ぐ vs 限界 - 1 回 loop を回し確実にもう一回好きなところでとめられるようにして稼ぐ
                    loop_score = head_score + loop_times * loop_gain + res_score
                    stop_score = M + (loop_times - 1) * loop_gain
                    return max(loop_score, stop_score)

        # debug('never encountered loop.')
        return M
            

    n, k = mi()
    P = lmi_0()
    C = lmi()

    ans = -inf
    for i in range(n):
        score = calc_score(i)
        # debug(f'start: {i} ans: {score}')
        ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-


def solve():
    N, K = list(map(int, input().split()))
    Ps = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    # 最低一回は移動させないといけないの忘れてた
    ans = -float("inf")
    for i in range(N):
        ans = max(ans, Cs[i])

    if K == 1:
        print(ans)
        return

    loop_list = []
    for start in range(N):
        now = start
        visited = set()
        visited.add(now)
        move = 0
        total_score = 0
        max_score = ans

        while True:  # たかだかN回
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            move += 1
            now = nx
            if now in visited:
                # 一周した
                if total_score > 0:
                    # 一周する価値あるので、loop_listに追加
                    loop_list.append((start, total_score, move))
                break

            # 一周してない
            if move == K:
                # もう移動できないので終わり
                break
            visited.add(now)
        ans = max(ans, max_score)


    # 一周した方が得かつ、移動回数が余っているなら、ぐるぐる回る
    for start, score, move in loop_list:
        total_score = score*(K//move)
        restK = K % move
        max_score = total_score

        # K回目の最大値を探す
        now = start
        while restK != 0:
            restK -= 1
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            now = nx
        ans = max(ans, max_score)

        # K-1回目の最大値を探す
        now = start
        total_score = score*(K//move) - score
        max_score -= total_score
        for i in range(move):
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            now = nx
        ans = max(ans, max_score)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
ans=-INF
for i in range(n):
    c1=[]
    a=i
    while True:
        a=p[a]-1
        c1.append(c[a])
        if a==i:
            break
    m1=0
    for j in range(min(k,len(c1))):
        m1+=c1[j]
        ans=max(m1,ans)
    if m1>0:
        t=k//len(c1)
        m1=max(0,m1*(t-1))
        ind=max(0,len(c1)*(t-1))
        ans=max(ans,m1)
        for i in range(ind,k):
            m1+=c1[i%len(c1)]
            ans=max(ans,m1)
out(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n,k=MI()
	P=LI()
	for i in range(n):
		P[i]-=1
	C=LI()

	A=[[] for _ in range(n)]

	for i in range(n):
		A[i].append(C[i])
		now=P[i]
		while i!=now:
			A[i].append(A[i][-1]+C[now])
			now=P[now]
	#print(A)

	ans=-10**18

	for i in range(n):
		l=len(A[i])
		q,r=divmod(k-1,l)

		if q==0:
			ans=max(ans,max(A[i][:k]))
		else:
			if A[i][-1]<=0:
				ans=max(ans,max(A[i]))
			else:
				ans=max(ans,A[i][-1]*(q-1)+max(A[i]),A[i][-1]*(q)+max(A[i][:r+1]))

	print(ans)















if __name__ == "__main__":
	main()