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, KK = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

cnt = [1] * (N+1)
retsu = []
for i in range(1,N+1):
    idx = i
    r = []
    for _ in range(N):
        if cnt[idx] == 0:
            break
        r.append(C[P[idx]])
        cnt[idx] = 0
        idx = P[idx]
    if r:
        retsu.append(r)

ans = -1 * (10 ** 10)
for z in retsu:
    K = KK
    s = sum(z)
    l = len(z)
    if K <= l:
        plus = 0
    elif s <= 0:
        plus = 0
        K = l
    else:
        plus = s * (K // l)
        if K % l == 0:
            plus -= s
    K %= l
    if K == 0:
        K = l
    
    moto = z + z
    point = [[0] * l for _ in range(l+K-1)]
    kari = -1 * (10 ** 10)
    for i in range(l+K-1):
        for j in range(l):
            if i == j:
                point[i][j] = moto[i]
            elif i - j >= K or i < j:
                continue
            else:
                point[i][j] = moto[i] + point[i-1][j]
            kari = max(kari, point[i][j])
    ans = max(ans, plus + kari)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
    snp=P[i]
    r=C[snp]
    L=[r]
    c=0
    np=P[snp]
    while True:
        if c==k-1:
            ANS=max(max(L),ANS)
            break
        if np==snp:
            y=k%(c+1)
            m=k//(c+1)
            if y==0:
                ANS=max(max(L),max(L)+(m-1)*L[-1],ANS)
                break
            else:
                #print(m,y)
                #print(L)
                ANS=max(max(L),max(max(L[:y]),0)+m*L[-1],ANS)
                break
        r+=C[np]
        L.append(r)
        np=P[np]
        c+=1
print(ANS)

Submission status: Accepted

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

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

Submission status: Accepted

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

n,k = map(int,input().split())
p = list(map(int,input().split()))

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

c = list(map(int,input().split()))
used = [False]*n

edge = []

for i in range(n):
    if used[i]:
        continue
    now = i
    edge.append([])

    while True:
        if used[now]:
            break
        used[now] = True
        edge[-1].append(c[now])
        now = p[now]

res = -10**9
for i in range(len(edge)):
    s = sum(edge[i])
    m = len(edge[i])

    for j in range(m):
        tmp = 0
        ctr = 0
        for h in range(j+1,m):
            ctr += 1
            tmp += edge[i][h]
            if ctr <= k:
                res = max(res,tmp,tmp+((k-ctr)//m)*s)
        for h in range(j+1):
            ctr += 1
            tmp += edge[i][h]
            if ctr <= k:
                res = max(res,tmp,tmp+((k-ctr)//m)*s)
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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()))
    
visited = [False] * n
ans = max(c)

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

Submission status: Accepted

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

p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

loop_max = []
loop_len = []
S = []
ans = []

for i in range(len(p)):
    now = i
    temp_len = 0
    temp_s = 0
    temp_l = []
    while True:
        now = p[now] - 1
        temp_len += 1
        temp_s += c[now]
        temp_l.append(temp_s)

        # 最初に戻ってきたら
        if now == i:
            break

    loop_len.append(temp_len)
    loop_max.append(temp_l)
    S.append(temp_s)

for i in range(len(S)):
    mod = k % loop_len[i] if k % loop_len[i] != 0 else loop_len[i]
    if S[i] > 0:
        if max(loop_max[i][:mod]) > 0:
            ans.append(((k-1)//loop_len[i])*S[i] + max(loop_max[i][:mod]))
        else:
            ans.append(((k - 1) // loop_len[i]) * S[i])
    else:
        ans.append(max(loop_max[i]))

print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate 

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

ans = -10**18-1
seen = [False]*N
for i in range(N):
    if seen[i]:
        continue
    loop = []
    now = i
    while seen[now] == False:
        seen[now] = True
        loop.append(C[now])
        now = P[now]
    loop_size = len(loop)
    loop_score = sum(loop)
    cumsum = list(accumulate(loop+loop))
    for j in range(1, min(K, loop_size)+1):
        for l in range(loop_size):
            r = l+j
            subseq = cumsum[r] - cumsum[l]
            ans = max(ans, subseq, subseq+loop_score*((K-j)//loop_size))
print(ans)

Submission status: Accepted

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

p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

p_flag = [0 for _ in range(len(p))]
loop_max = []
loop_len = []
S = []
S_max = []
ans = []

for i in range(len(p)):
    # if p_flag[i] == 1:
    #     continue
    now = i
    temp_len = 0
    temp_s = 0
    S_max = - (10**9 + 1)
    temp_l = []
    while True:
        now = p[now] - 1
        temp_len += 1
        temp_s += c[now]
        temp_l.append(temp_s)
        p_flag[now] = 1

        # 最初に戻ってきたら
        if now == i:
            break

    loop_len.append(temp_len)
    loop_max.append(temp_l)
    S.append(temp_s)

for i in range(len(S)):
    mod = k % loop_len[i] if k % loop_len[i] != 0 else loop_len[i]
    if S[i] > 0:
        if max(loop_max[i][:mod]) > 0:
            ans.append(((k-1)//loop_len[i])*S[i] + max(loop_max[i][:mod]))
        else:
            ans.append(((k - 1) // loop_len[i]) * S[i])
    else:
        ans.append(max(loop_max[i]))

# print(loop_max)
# print(ans)
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate 

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

ans = -10**18-1
seen = [False]*N
for i in range(N):
    if seen[i]:
        continue
    loop = []
    now = i
    while seen[now] == False:
        seen[now] = True
        loop.append(C[now])
        now = P[now]
    loop_size = len(loop)
    loop_score = sum(loop)
    cumsum = [0]+list(accumulate(loop+loop))
    for j in range(1, min(K, loop_size)+1):
        for l in range(loop_size+1):
            r = l+j
            subseq = cumsum[r] - cumsum[l]
            ans = max(ans, subseq, subseq+loop_score*((K-j)//loop_size))
print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

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

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

print(d_moving_piece())

Submission status: 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()))

move_db = [[0] * N for _ in range(65)]
point_db = [[0] * N for _ in range(65)]
maxpoint_db = [[0] * N for _ in range(65)]

for i, (p, c) in enumerate(zip(P, C)):
    move_db[0][i] = p
    point_db[0][i] = c
    maxpoint_db[0][i] = c

for i in range(40):
    for j in range(N):
        move_db[i+1][j] = move_db[i][move_db[i][j]]
        point_db[i+1][j] = point_db[i][move_db[i][j]] + point_db[i][j]
        maxpoint_db[i+1][j] = max(maxpoint_db[i][j], point_db[i][j] + maxpoint_db[i][move_db[i][j]])

res = -10 ** 19
for i in range(N):
    tmp, now = 0, i
    for d in range(32):
        if K&(1<<d):
            res = max(res, tmp + maxpoint_db[d][now])
            tmp += point_db[d][now]
            now = move_db[d][now]

print(res)

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=max(c)
for i in range(n):
    f=i
    r=0
    l=[]
    while True:
        f=p[f]
        l.append(c[f])
        r+=c[f]
        if f==i:
            break
    t=0
    for j in range(len(l)):
        t+=l[j]
        ret=t
        if r>0:
            e=(k-j-1)//len(l)
            ret+=r*e
        ans=max(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = [-1] * self.n
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = cnt
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] == cnt:
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = cnt
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

"""
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
print(roop.move(A, K) + 1)

"""

"""
# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)
"""


# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()

ignore = [-1] * N
ans = -float('inf')
for i in range(N):
    if ignore[i] >= 0:
        continue
    ### ループ生成 ###
    ignore[i] = 1
    opt_l = [i]
    to = P[i]
    while ignore[to] == -1:
        opt_l.append(to)
        ignore[to] = 1
        to = P[to]
    ###
    ### 作成したループで得点リスト生成 ###
    n = len(opt_l)
    point = [0] * n
    for i in range(n):
        point[i] = C[opt_l[i]]
    ###
    ### 得点リスト内の連続する区間の総和のうちの最大値を累積和を使って求める ###
    sum_roop = sum(point)
    # ループの累積和作成
    imos = [0]
    point += point
    for i in range(len(point)):
        imos.append(imos[i] + point[i])
    #
    ran = min(n, K)
    for i in range(n):
        # 区間の大きさran以下についての総和を求める
        for j in range(1, ran + 1):
            if sum_roop >= 0:
                opt = imos[i + j] - imos[i] + ((K - j) // n) * sum_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)
    ###
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=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    accum=[0]+accum
    #print(accum)
    for x in range(1,l+1):
        if accum[x+l-1]-accum[x-1]<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
import itertools

if __name__ == "__main__":

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

	# print(P)
	# 一度計算したサイクル情報をキャッシュしておくための配列
	# cycleIDs = np.full( N, -1, np.int64 )
	cycleIDs = [ -1 for _ in range(N)]
	cycleInfs = []
	cycleID = 0
	procCnt = 0

	for n in range(N):
		v = n

		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleCosts.append( C[v] )
				cycleIDs[v] = cycleID

				v = P[v]
				if cycleIDs[v] != -1:
					# サイクル終了
					# ループを含めない最大の処理回数
					procCnt = K % len( currentCycleCosts )
					# それで足りてるのかわからないが、Last2周分は、ループ合計がプラスでも必ずしもループするとは限らない
					# その部分は、ちゃんと計算する
					# -------------------------------------------------
					# 4 101
					# 2 3 4 1
					# 50 -49 -50 50
					# 上記のようなパターンの場合、
					# 最大25回ループ + 1回処理可能だが、その場合、25 + 50 = 75
					# 24回ループ + 2回処理でやめると、124になる
					# 無条件でループする回数は、ループ可能な最大の回数-1らしい
					# -------------------------------------------------
					# 割り切れて、尚且つサイクル合計がマイナスのパターンで、最低１個は処理するのにもここで対応
					if len( currentCycleCosts ) + procCnt <= K:
						procCnt += len( currentCycleCosts )

					cycleInfs.append( ( procCnt, len(currentCycleCosts), currentCycleCosts * 3 ) )
					cycleID += 1
					break



	# scores = []
	# procCnt = 0
	ans = -10 ** 9
	for procCnt, currentCycleSize, currentCycleCosts in cycleInfs:

		# サイクル内でループしてスコアを稼ぐ場合の考慮
		loopScore = 0
		if sum(currentCycleCosts) > 0:
			cycleLoopCnt =  ( K - procCnt ) // currentCycleSize
			loopScore = cycleLoopCnt * sum(currentCycleCosts[:currentCycleSize])
			# print("loopScore",loopScore,procCnt)

		# このサイクルに属する全頂点分をまとめて計算する
		for i in range(currentCycleSize):
			# print(np.roll( currentCycleCosts, i ).cumsum()[:procCnt])
			score = max( itertools.accumulate( currentCycleCosts[i:i+procCnt] ) )
			if ans < score + loopScore:
				ans = score + loopScore
			# ans = max( ans, score + loopScore )


	print(ans)
	# print(max(scores))

Submission status: Accepted

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

max_score = 0
first = True
for i in range(N):
  score = 0
  step = 0
  path = {}
  cumulative_score = []
  current_p = i
  cycle_passed = False
  while step < K:
    # record current step
    cumulative_score.append(score)
    
    # check if cycle is found
    if (not cycle_passed) and (current_p in path.keys()):
      # found a cycle 
      # calculate score sum within the cycle
      # calculate steps with in the cycle
      cycle_start_step = path[current_p]
      cycle_steps = step - cycle_start_step
      cycle_sum = cumulative_score[step] - cumulative_score[cycle_start_step]
      if cycle_sum < 0:
        # negative cycle
        # finish 
        break
      else:
        #positive cycle
        remain_steps = K - step
        if remain_steps > cycle_steps:
          cycle_times = (K - step) // cycle_steps - 1
          step += (cycle_times * cycle_steps)
          score += (cycle_times * cycle_sum)
          cycle_passed = True
        else:
          cycle_passed = True    
        
    # record current step
    path[current_p] = step
    
    # go to next step
    next_p = p_list[current_p-1]
    score += c_list[next_p-1]
    if (first):
      max_score = score
      first = False
    else:
      max_score = max(max_score, score)
    
    current_p = next_p
    step += 1

print(max_score)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
uf = UnionFind(N)
ans = -10**9
for i in range(N):
    uf.union(i,P[i]-1)
for group in uf.all_group_members().values():
    size = len(group)
    SUM = 0
    for i in group:
        SUM += C[i]
    if SUM < 0:
        SUM = 0
    for i in group:
        cur = i
        current_sum = 0
        remain = K
        for _ in range(size):
            cur = P[cur]-1
            current_sum += C[cur]
            remain -= 1
            if remain < 0:
                break
            ans = max(ans,current_sum+SUM*(remain//size))
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()))
now=-100000000000
for i in range(1,n+1):
    retu=[]
    sum1=0
    sum2=0
    sum3=0
    max1=-1000000000000
    max2=-1000000000000
    flag=0
    x=i
    while(flag==0):
        x=p[x-1]
        sum1+=c[x-1]
        retu.append(c[x-1])
        if x==i:
            flag=1
    if len(retu)>=k: #操作回数が周期未満
        for j in range(k):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        ans=max1
    elif sum1<=0: #周期和が負
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        ans=max2
    else:
        w=k%len(retu)
        
        if w==0:
            w=len(retu)
        for j in range(w):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        if max1+sum1>max2:
            ans=sum1*(k-w)//len(retu)+max1
        else:
            ans=sum1*((k-w)//len(retu)-1)+max2
    now=max(now,ans)
print(now)