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:
import sys


def input():
    return sys.stdin.readline().rstrip()


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


    maxscore = -10 ** 9 - 10
    for i in range(N):
        vis_val = [-10 ** 10] * N
        vis_time = [0] * N
        score = 0
        current = i
        k = 1
        flag=0
        while k <= K:
            current = P[current] - 1
            score += C[current]
            if vis_time[current]:
                if score - vis_val[current] <= 0:
                    roopmax = max(vis_val)
                    flag=1
                    break
                else:

                    one_cicle = k - vis_time[current]
                    one_val = score - vis_val[current]
                    rem = (K - k) // one_cicle
                    score += rem * one_val
                    k += one_cicle *rem
                    roopmax = score
                    k+=1
                    while k <= K:
                        current = P[current] - 1
                        score += C[current]
                        roopmax = max(roopmax, score)
                        k+=1
                        flag=1

            vis_val[current] = score
            vis_time[current] = k
            k += 1
        if flag==0:
            roopmax=max(vis_val)

        maxscore = max(roopmax, maxscore)

    print(maxscore)

if __name__ == "__main__":
    main()

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
INF=-(10**20)
X=[[INF]*(N+1) for i in range(N)]
Y=[0]*N
Z=[0]*N
R=[0]*N
S=set()
V=0
for i in range(N):
  S=set()
  V=i
  S.add(i)
  for j in range(N):
    V=P[V]
    if V in S:
      Z[i]=V
      break
  X[i][0]=0
  for j in range(N):
    Y[i]+=1
    V=P[V]
    X[i][j+1]=X[i][j]+C[V]
    if Z[i]==V:
      R[i]=X[i][j+1]
      break
A=INF
Q=0
T=0
U=0
D=0
E=0
for i in range(N):
  D=K
  V=i
  E=0
  for j in range(min(N,K)):
    if Z[i]==V:
      break
    V=P[V]
    E+=C[V]
    D-=1
  i=V
  D,K=K,D
  if R[i]<=0:
    for j in range(1,min(Y[i],K)+1):
      A=max(A,X[i][j]+E)
  else:
    S=max((K//Y[i])-1,0)
    Q=R[i]*S
    T=0
    U=INF
    V=i
    for j in range(K-S*Y[i]):
      V=P[V]
      T+=C[V]
      U=max(T,U)
    Q+=U
    A=max(A,Q+E)
  D,K=K,D
print(A)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N,K = MI()
P = LI()
C = LI()

for i in range(N):
    if C[i] >= 0:
        break
else:
    print(max(C))
    exit()

from itertools import accumulate

flag = [0]*N
ans = max(C)
for i in range(N-1):
    if flag[i] != 0:
        continue
    A = [C[i]]
    flag[i] = 1
    a = i
    j = P[i]-1
    while j != i:
        A.append(C[j])
        flag[j] = 1
        j = P[j]-1
    a = len(A)
    s = 0
    if sum(A) > 0:
        if K//a > 0:
            s = sum(A)*(K//a-1)
            r = K % a + a
        else:
            s = 0
            r = K % a
    else:
        s = 0
        r = K % a + a
    A = [0] + A + A + A
    S = list(accumulate(A))
    m = 0
    for i in range(a):
        for k in range(1,r+1):
            b = S[i+k] - S[i]
            m = max(m,b)
    s += m
    ans = max(ans,s)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    C = list(map(int, readline().split()))

    ans = -INF
    for i in range(N):
        seen = [False] * N
        s = 0
        s_max = -INF
        scores = []
        k = 0

        while k < K and not seen[i]:
            seen[i] = True
            s += C[P[i]]
            scores.append(s)
            if s_max < s:
                s_max = s
            i = P[i]
            k += 1

        if k == K and ans < s_max:
            ans = s_max
        elif scores[-1] > 0:
            tmp = max(
                s_max,
                scores[-1] * (K // k) + max(0, max(scores[: K % k], default=0)),
                scores[-1] * (K // k - 1) + s_max,
            )
            if ans < tmp:
                ans = tmp
        else:
            if ans < s_max:
                ans = s_max

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = [int(hoge) for hoge in input().split()]
P = [int(hoge)-1 for hoge in input().split()]#0-indexed
C = [int(hoge) for hoge in input().split()]
LoopSum = []
ans = 0
LoopIndex = [-1 for i in range(N)]
Loops = []
num = 0
for start in range(N):
    if -1 == LoopIndex[start]:
        LpSm = C[start]
        LoopIndex[start] = num
        route = [start]
        cur = P[start]
        while cur != start:
            LoopIndex[cur] = num
            route.append(cur)
            cur = P[cur]
            LpSm += C[cur]
        Loops.append(route)
        LoopSum.append(LpSm)
        num += 1
DekiSumAmari = [(K//len(L),sum([C[j] for j in L]),K%len(L)) for L in Loops]
for s in range(N):
    Looplen =len(Loops[LoopIndex[s]])
    score = 0
    D,S,A = DekiSumAmari[LoopIndex[s]]
    if S<=0:#一周もしないほうがいい
        A = min(K,Looplen)
    else:
        if A==0:
            D -= 1
            A = Looplen
        score += D*S
    curpos = s
    curplus = 0
    maxplus = 0
    for i in range(min(K,Looplen)):
        if i == A:
            curplus -= S
        curplus += C[curpos]
        curpos = P[curpos]
        maxplus = max(maxplus,curplus)
    score += maxplus
    ans = max(ans,score)
if ans == 0:
    ans = max(C)
print(ans)

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=-10**18

for i in range(N):
    cnt=K
    pos=i
    tmp=[0]
    base=C[pos]
    while cnt and P[pos]!=i:
        pos=P[pos]
        tmp.append(tmp[-1]+C[pos])
        base+=C[pos]
        cnt-=1
    if P[pos]==i:
        if base>0:
            test=base*(K//len(tmp))
            cnt=K%len(tmp)
            if cnt:
                ttt=max(tmp[j] for j in range(1,cnt+1))
                if test:
                    ttt=max(ttt,0)
                test+=ttt
            ans=max(ans,test)
            if K>=len(tmp):
                test=base*(K//len(tmp)-1)
                cnt=len(tmp)-1
                ttt=max(tmp[j] for j in range(1,cnt+1))
                if test:
                    ttt=max(ttt,0)
                test+=ttt
                ans=max(ans,test)
        else:
            tmp.append(tmp[-1]+C[i])
            cnt=min(K,len(tmp)-1)
            if cnt:
                test=max(tmp[j] for j in range(1,cnt+1))
                ans=max(ans,test)
    else:
        test=max(tmp[j] for j in range(1,len(tmp)))
        ans=max(ans,test)


print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [float('-inf')] + list(map(int, input().split()))
ans = max(C)
for start in range(1, N+1):
    now = start
    score = 0
    c_list = []
    for k in range(1, K+1):
        now = P[now]
        cost = C[now]
        score += cost
        c_list += [cost]
        ans = max(ans, score)
        if now == start:
            Kmk = K-k
            # score = score + score * (Kmk // len(c_list))
            roop = (Kmk // len(c_list))
            score = score + score * max(0, roop-1)
            ans = max(score, ans)
            if roop >= 1:
                for ci in c_list:
                    score += ci
                    ans = max(score, ans)
            for i in range(Kmk % len(c_list)):
                score += c_list[i]
                ans = max(score, ans)
            break
        

print(ans)

Submission status: Accepted

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


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(min(n, k)):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    #print(a, b)
    ans = max(ans,max(b))
    for i in range(n):
        co = b[i]
        i = a[i]
    #    print(i, co)
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    #        print(i, co)
            ans = max(ans, co)
    #    print()

print(ans)

Submission status: Accepted

Solution code:

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

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

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

Q = min2(N,K)

acc = [0]*N
visited = [-1]*N
last = [0]*N


res = -10**9

for p in range(N):
    c = 0
    v = P[p]
    for j in range(Q):
        if visited[v] == j:
            break
        visited[v] = j
        acc[v] = c
        c += C[v]
        last[v] = j
        v = P[v]
        res = max2(c,res)

    i = last[v]
    j += 1

    delta = c - acc[v]
    # print(i,j,delta)
    if delta > 0:
        remaining = K - i
        cycle = j-i
        if remaining < cycle:
            c = acc[v]
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]
        else:
            c = acc[v]+(remaining//cycle - 1)*delta
            remaining = cycle + remaining%cycle
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]

print(res)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1回以上K回以下
ansF=-1000000000000000000
for i in range(n):
    #すでに辿ったもの
    check=[False]*n
    #辿った順番
    turns=[]
    #今
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    #答え(今の)
    ans=0
    #kのうち何回分
    #更新を毎回行う
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    #サイクルの長さ
    l=len(turns)
    #サイクルの和(あまりも)
    #サイクルどこで止めるか
    x=0
    for j in range(l):
        x+=c[turns[j]]
    #そもそもサイクル回らない場合
    if spare<=l:
        for j in range(spare):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    #サイクル回した方が良い場合
    #最後のサイクルは回さない方が良いパターンも
    if x>=0:
        ans+=(x*(spare//l-1))
        ansF=max(ans,ansF)
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    #サイクル回さない方がいい場合
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)

Submission status: Accepted

Solution code:
def solve(shoki):
    global n,k,p,c
    sude=[-1]*n
    sude[shoki]=0
    ten=[0]
    now=shoki
    ishuu_kai=0
    ishuu_ten=0
    for i in range(n):
        now=p[now]
        if(sude[now]<0):
            sude[now]=i+1
            ten.append(ten[-1]+c[now])
        else:
            ten.append(ten[-1]+c[now])
            ishuu_kai=i+1-sude[now]
            ishuu_ten=ten[-1]-ten[sude[now]]
            break
    #print(shoki)
    #print(ten,ishuu_kai,ishuu_ten)
    if(ishuu_ten>0):
        now=shoki
        for i in range(ishuu_kai):
            ten[i]+=((k-i)//ishuu_kai)*ishuu_ten
            now=p[now]

    #print(ten,ishuu_kai,ishuu_ten)
    if(k>ishuu_kai):
        return max(ten)
    else:
        return max(ten[1:k+1])


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=[]
for i in range(n):
    ans.append(solve(i))

print(max(ans))

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):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    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(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')

for start in range(N):
    loop_len = 1
    pos = P[start]
    score = C[pos]
    scores = [score]
    while pos != start:
        loop_len += 1
        pos = P[pos]
        score += C[pos]
        scores.append(score)
    loops = (K-1)//loop_len
    if score > 0:
        cand = max(0, score * loops) + max(scores[:(K-loop_len * loops)])
    else:
        cand = max(scores[:min(K, loop_len)])
    ans = max(ans, cand)
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()))

ans = []
for u in range(N):
    v = P[u] - 1
    cnt = C[v]
    val = cnt
    jump = 1

    # Jump to limit or loop
    while v != u and jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    # Reduce residual to < K
    if jump < K:
        res = max(0, K // jump - 2)
        cnt += cnt * res
        val = max(val, cnt)
        jump += jump * res

    # Residual steps
    while jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    ans.append(val)

print(max(ans))

Submission status: Accepted

Solution code:
# pypy

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

def do(start, k):
    score = 0
    max_score = -10 ** 10
    visited = set()
    now = start
    count = 0
    while True:
        next_node = P[now]
        if next_node in visited:
            if score <= 0:
                return max_score
            else:
                n = k // count
                score = score * (n-1)
                max_score = score
                k %= count; k += count
                for _ in range(k):
                    next_node = P[now]
                    score += C[next_node]
                    max_score = max(max_score, score)
                    now = next_node
                return max_score
        
        score += C[next_node]
        count += 1
        max_score = max(max_score, score)
        now = next_node
        visited.add(now)
        if count == k:
            return max_score

ans = -10 ** 10
for start in range(1, N+1):
    ans = max(ans, do(start, K))

print(ans)

Submission status: Accepted

Solution code:
R = lambda: map(int, raw_input().split())
n, k = R()
p, c = R(), R()
p = [x - 1 for x in p]
vis = [False] * n
ans = max(c)

for i in xrange(n):
    if vis[i]:
        continue
    t = [c[i]]
    j = p[i]
    while j != i:
        vis[j] = True
        t.append(c[j])
        j = p[j]

    m = len(t)
    ts = sum(t)
    for i in xrange(len(t)):
        tmp = min(k, m)
        s = 0
        for j in xrange(tmp):
            s += t[(i + j) % m]
            tk = k - j - 1
            ans = max(ans, s + tk / m * max(0, ts))
print ans

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))

    res = -f_inf
    for now in range(n):
        cnt = 0
        score = [0]
        visited = set()
        for j in range(k):
            next_now = P[now] - 1
            if next_now not in visited:
                score.append(score[-1] + C[next_now])
                visited.add(next_now)
                now = next_now
                cnt += 1
            else:
                break
        score.pop(0)
        if k - cnt == 0:
            res = max(res, max(score))
        else:
            if score[-1] <= 0:
                res = max(res, max(score))
            else:
                q, r = divmod(k, cnt)
                if r == 0:
                    res = max(res, max(score) + score[-1] * (q - 1))
                else:
                    res = max(res, max(score[:r]) + score[-1] * q, max(score[r:]) + score[-1] * (q - 1))
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(arr,brr,k):  # fix inputs here
    console("----- solving ------")
    arr = [a-1 for a in arr]

    console(arr)
    console(brr)
    console(k)

    if all(b <= 0 for b in brr):
        return max(brr)

    visited = [False for _ in arr]
    cycles = []

    for start,_ in enumerate(arr):
        if visited[start]:
            continue
        cur_cycle = [start]
        current = start
        visited[current] = True

        while arr[current] != start:
            current = arr[current]
            cur_cycle.append(current)
            visited[current] = True
        
        cycles.append(cur_cycle)

    res = -float("inf")

    for cycle in cycles:
        console(cycle)

        cs = 0
        psum = []
        for idx in cycle+cycle:
            cs += brr[idx]
            psum.append(cs)
        
        lengths = [-float("inf") for i in cycle]
        for start,_ in enumerate(cycle):
            for length,_ in enumerate(cycle):
                lengths[length] = max(lengths[length], psum[start+length] - psum[start])
    
        console([brr[idx] for idx in cycle])
        full_cycle = sum([brr[idx] for idx in cycle])

        if k < len(cycle) or full_cycle <= 0:
            curres = max(lengths[:k+1])
            console(curres)
            res = max(res, curres)
            continue
        
        console(lengths, full_cycle)

        num_cycles = (k // len(cycle)) - 1
        res_baseline = num_cycles * full_cycle
        remainder = k % len(cycle)

        curres1 = res_baseline + max(lengths)
        curres2 = res_baseline + full_cycle + max(lengths[:remainder+1])

        console(curres1)
        console(curres2)

        curres = max(curres1, curres2)
        console(curres)
        res = max(res, curres)

    console(cycles)

    # return a string (i.e. not a list or matrix)
    return int(res)  


def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    _,k = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    brr = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(arr,brr,k)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,k = m()

masc = [[0 for i in range(n+1)] for j in range(n)]
maxsu = [[0 for i in range(n+1)] for j in range(n)]

roop = [0 for i in range(n)]

p = l()

c = l()

for i in range(n):
    count = 0
    su = 0
    now = i
    for j in range(n+1):
        now = p[now] - 1
        count += 1
        su += c[now]
        masc[i][count-1] = su
        if count == 1:
            maxsu[i][count-1] = su
        else:
            maxsu[i][count-1] = max(maxsu[i][count-2],su)
        if i == now:
            roop[i] = count
            break

ans = -Max

for i in range(n):
    if k <= roop[i]:
        ans = max(ans,maxsu[i][k-1])
    else:
        if masc[i][roop[i]-1] < 0:
            ans = max(ans,maxsu[i][roop[i]-1])
        else:
            ans = max(ans,(k//roop[i]) * masc[i][roop[i]-1] + maxsu[i][k % roop[i]-1],(k//roop[i] - 1) * masc[i][roop[i]-1] + maxsu[i][roop[i]-1])
print(ans)

Submission status: Accepted

Solution code:
def solve(n,x,k):
  ans=-10**20
  s=0
  sx=sum(x)
  for i in range(n):
    if (i+1)>k:break
    s+=x[i]
    d=((k-i-1)//n)*sx
    ans=max(ans,s+d,s)
  return ans

n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  x=x[1:]+[x[0]]
  ans=max(ans,solve(len(x),x,k))
print(ans)

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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


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

# ------------------- fast io --------------------
from math import gcd, ceil



def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
from math import inf

for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -inf
    for i in range(n):
        st = set()
        st.add(i)
        cur = i
        x = []
        while p[cur]-1 not in st:
            cur = p[cur]-1
            st.add(cur)
            x += [c[cur]]
        x += [c[p[cur]-1]]

        pre = [0]*len(x)
        pre[0] = x[0]
        for i in range(1, len(x)):
            pre[i] = pre[i-1] + x[i]
        if len(x) >= k:
            ans = max(ans, max(pre[:k]))
        else:
            kc = k
            kcc = k
            anss = 0
            if pre[-1] > 0:
                anss += pre[-1]*(kc // len(x))
                kc = kc % len(x)
                if kc:
                    anss += max(pre[:kc])
                ans = max(ans, anss, max(pre)+(pre[-1]*((kcc // len(x))-1)))
            else:
                ans = max(ans, max(pre))
    print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    P = LI1()
    C = LI()

    visit = [False] * N
    where = [-1] * N

    group = []
    group_sum = []
    for i in range(N):
        if visit[i]: continue
        
        now = i
        tmp = []
        cum = 0
        while not visit[now]:
            tmp.append(now)
            visit[now] = True
            where[now] = len(group)
            cum += C[now]
            now = P[now]
        group.append(tmp)
        group_sum.append(cum)

    ans = -INF

    for i in range(N):
        g = group[where[i]]

        if len(g) <= K:
            loop_count = K // len(g) - 1
            rest = K - loop_count * len(g)
        else:
            loop_count = 0
            rest = K

        loop_score = group_sum[where[i]]

        tmp = C[P[i]]
        tmp_max = C[P[i]]
        now = P[i]
        for _ in range(rest-1):
            now = P[now]
            tmp += C[now]
            tmp_max = max(tmp, tmp_max)
        ans = max(ans, max(tmp_max, tmp_max + loop_count * loop_score))
    print(ans)






if __name__ == '__main__':
    main()