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: Wrong Answer

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

ans = 0
for i in range(N):
    score = 0
    score_max = 0
    pos = [P[i]-1]
    for j in range(N-1):
        pos.append(P[pos[j]]-1)
        if P[pos[j]]-1 == i:
            break
    
            
    score = C[pos[0]]
    score_max = score
    for j in range(1,K%len(pos)):
        score += C[pos[j]]
        score_max = max(score_max, score)
    
    if K > len(pos):
        sc = 0
        for j in pos:
            sc += C[j]
        score += sc * int(K/len(pos))
        score_max = max(score_max, score)
    
    if i == 0:
        ans = score_max
    else:
        ans = max(ans,score_max)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
CC = [[] for _ in range(n)]

for idx, p in enumerate(P):
    CC[idx].append(C[p])
    pp = P[p]
    for _ in range(n):
        CC[idx].append(C[pp])
        pp = P[pp]
        if pp == p:
            break
        
from itertools import accumulate
ans = -5**13
for cc in CC:
    cca = list(accumulate(cc))
    sc = sum(cc)
    if sc <= 0:
        if k < len(cc):
            ans = max(ans, max(cca[:k]))
        else:
            ans = max(ans, max(cca))
    else:
        kk, r = divmod(k, len(cc))
        if r == 0:
            ans = max(ans, kk*sc)
        else:
            ans = max(ans, kk*sc + max(cca[:r]))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 63


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

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    #print(loops)
    #print(loopSums)
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] < 0 or K <= len(loop)-2:
                j = i
                max_val = -INF
                while True:
                    if j >= len(loop):j=0
                    if i != j and j:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    if i == j: break
                ans = max(ans, max_val)
                continue
            

            rest = K
            #if K <= len(loop) - i - 1:
            #    val += loopSum[i + K - 1] - loopSum[i]
            #    ans = max(ans, val)
            #    continue
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            val += (rest // (len(loop)-1)) * loopSum[-1]
            rest = rest % (len(loop) - 1)
            val += loopSum[rest]
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())

    ################


    mod=10**9+7
    N,K=MI()
    P=LI()
    C=LI()
    
    for i in range(N):
        P[i]-=1
    
    uf =UnionFind(N)
    for i in range(N):
        uf.union(i,P[i])
        
    from collections import defaultdict
    dd = defaultdict(list)
        
    for i in range(N):
        root=uf.find(i)
        dd[root]+=[i]
        
    ansAll=-1*(10**10)
    for k,v in dd.items():
        N2=len(v)
        #rootから移動した時の点数の順番，2周分
        L=[0]*(2*N2+3)
        now=k
        for i in range(2*N2+3):
            nxt=P[now]
            L[i]=C[nxt]
            now=nxt
        S=[0]*(2*N2+3)
        for i in range(2*N2):
            S[i+1]=S[i]+L[i]
        
        ans=0
        
        ROOP=S[N2]-S[0] 
        if ROOP>0:#1週分
            roop=K//N2
            ans+=ROOP*roop
            rem=K%(N2)
        else:
            roop=0
            rem=min(K,N2)
            
        if roop==0:
            temp=-1*(10**10)
        else:
            temp=0
        for i in range(1,rem+1):#i個トル
            for j in range(N2+1):#jからスタート
                s=S[j+i]-S[j]
                temp=max(temp,s)
        ans=ans+temp
        
        # print(k,v,roop,rem)
        # print(L)
        # print(S)
        # print(temp,ans)
        # print("---")
        
        
        ansAll=max(ansAll,ans)
        
    print(ansAll)
        
            
    
 
        
    
            
    

main()

Submission status: Wrong Answer

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

ans = -10**9
loops = {}
for i in range(1,N+1):
    p = i
    k = K
    max_score = -10**9
    score = 0
    visited = set([p])
    visited_lst = [p]
    score_lst = [0]
    while 0 < k:
        score += C[P[p]]
        max_score = max(max_score,score)
        score_lst.append(score)
        p = P[p]
        k -= 1
        if p in visited:
            if p in loops:
                if 0 < loops[p][0]:
                    score += loops[p][0]*(k//loops[p][1])
                    k %= loops[p][1]
                    visited = set([p])
                    visited_lst = [p]
                    score_lst = [score]
                else:
                    break
            else:
                idx = visited_lst.index(p)
                l = len(score_lst)-1-idx
                for j in range(idx,l):
                    loops[visited_lst[j]] = [score-score_lst[idx],l]
                if 0 < score-score_lst[idx]:
                    score += (score-score_lst[idx])*(k//l)
                    k %= l
                    visited = set([p])
                    visited_lst = [p]
                    score_lst = [score]
                else:
                    break
        else:
            visited.add(p)
            visited_lst.append(p)
    # print(max_score)

    ans = max(ans,max_score)
# print(loops)
print(ans)

Submission status: Wrong Answer

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


def compute_cycle_score(score_list):
    s = sum(score_list)
    N_ = len(score_list)
    if s > 0:
        L = K % N_
        M = K // N_
        score = M * s
    else:
        L = min(N_, K)
        score = 0

    score_cand = []
    score_list_ = score_list + score_list
    #I = len(score_list)
    score_sum_k = score_list
    for k in range(1,L+1):
        if k > 1:
            score_sum_k = [a+b for a,b in zip(score_sum_k, score_list_[k-1:k-1+N_]) ]
            #score_sum_k = [ score_sum_k[i] + score_list_[i+k-1] for i in range(N_) ]
        s_ = max(score_sum_k)
        #score_sum_k, s_ = compute_scores_in_interval(score_list_, score_sum_k, I, k)
        score_cand.append(s_)
    if len(score_cand) > 0:
        score += max(score_cand)
    return score


Left = list(range(N))

scores_partition = []
while len(Left) > 0:
    temp = []
    start = min(Left)
    p = start
    init = True
    while p != start or init:
        init = False
        temp.append(C[p])
        Left.remove(p)
        p = P[p] - 1
    scores_partition.append(temp)


result = max(map(compute_cycle_score, scores_partition))
print(result)

Submission status: Wrong Answer

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


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):

    if K > N-1:
        temp_max = C[0]
        for i in range(N):
            score_i = [0]*N 
            score_i_max = [0]*N

            h = P[i]-1
            if h == i: break
            score_i[0] = C[h]
            score_i_max[0] = C[h]
            for j in range(1, N):
                h = P[h]-1
                score_i[j] = score_i[j-1] + C[h]
                score_i_max[j] = max(score_i[j-1], score_i[j])
                if h == i: break

            # print(score_i)
            mod_k = K % (j+1)
            rat_k = K //(j+1)
            if score_i[j] > 0:
                t = rat_k * score_i[j] + max(0,(score_i_max[mod_k-1]))
                temp_max = max(t, temp_max)
            else:
                temp_max = max(score_i_max[j], temp_max)

        print(temp_max)
    
    elif K <= N:
        score = [[0]*N for i in range(N)]
        for i in range(N):
            h = i
            for j in range(1, K):
                h = P[h]-1
                score[i][j] = score[i][j-1] + C[h]
        print(max(sum(score,[])))


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
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())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
p = lr()
c = lr()
visited = [True for i in range(n)]
ans = -inf

for i in range(n):
    if visited[i]:
        add_list = [i+1]
        visited[i] = False
        tmp = p[i]-1
        pre = 0
        while visited[tmp]:
            pre+=1
            visited[tmp] = False
            add_list.append(tmp+1)
            tmp = p[tmp]-1
        pre_ans = -inf
        length = len(add_list)
        a1 = [0]
        for m in range(2*length):
            a1.append(a1[-1]+c[add_list[m%length]-1])
        pre_total = a1[length]
        ret_ind = length-1
        for ind in range(1, ret_ind+1):
            for m in range(length):
                pre_ans = max(pre_ans, a1[m+ind]-a1[m])
        u = k//length
        if pre_total > 0:
            pre_ans+=(u*pre_total)
        ans = max(ans, pre_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
raw = []
seen = [0 for _ in range(n)]
for i in range(n):
  now = int(i)
  tmp = []
  if seen[i]:
    continue
  while seen[now] == 0:
    tmp.append(c[now])
    seen[now] = 1
    now = p[now] - 1
  raw.append(tmp)
#print(raw)
can = 0
for x in raw:
  sun = sum(x)
  l = len(x)
  if l == 1:
    can = max(can,sun*k)
    continue
  x += x
  x += x
  #print(x)
  now = [0]
  for y in x:
    now.append(now[-1]+y)
  #print(now)
  if sun > 0 and k >= l:
    ans = sun* (k//l-1)
    k = k % l + l
    #print(ans,k)
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          #print(now[j]-now[i],j-i,bool(268==now[j]-now[i]))
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    #print('#',maxi)
    #print('#',sun)
    #print(k)
    can = max(ans+maxi,can)
    #print(maxi)
    #print(ans+maxi)
  else:
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    can = max(maxi,can)
if can == 0:
  print(max(c))
else:
  print(can)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())

def junkan_max_score(junkan, C, K):
    ruiseki = [0]
    for i in range(len(junkan)):
        if i < len(junkan)-1:
            j = junkan[i+1]
        else:
            j = junkan[0]
        ruiseki.append(ruiseki[-1]+C[j])

    n_junkan = int(K/len(junkan))
    if n_junkan == 0:
        return max(ruiseki[1:K+1])
    elif ruiseki[-1] <= 0:
        return max(ruiseki[1:])
    else:
        junkan_score = n_junkan*ruiseki[-1]
        nokori_K = K-(n_junkan*len(junkan))
        if nokori_K == 0:
            return junkan_score
        else:
            return junkan_score+max(ruiseki[1:nokori_K+1])
        

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

p_junkan = {i:[i] for i in range(N)}

for i, lst in p_junkan.items():
    j = P[i]-1
    while j != i:
        lst.append(j)
        j = P[j]-1


junkan_max = [junkan_max_score(lst, C, K) for i,lst in p_junkan.items()]
print(max(junkan_max))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def main():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    m = max(C)
    if m <= 0:
        print(m)
        exit()
    i, c = 0, 0
    G = []
    g = []
    v = [False] * n
    while c < n:
        if v[i]:
            G.append(g)
            g = []
            i = v.index(False)
        g.append(i)
        v[i] = True
        i = P[i] - 1
        c += 1
    if g != []:
        G.append(g)
    ans = 0
    for g in G:
        score = [C[gg] for gg in g]
        S = [0] + list(accumulate(score * 2))
        l = len(score)
        c = max(0, sum(score)) * (k // l)
        for i in range(1, (k % l if c > 0 else l) + 1):
            for j in range(min(l, len(S) - i)):
                ans = max(ans, S[j + i] - S[j] + c)

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

score = 0
score_list = []

max_C = max(C)
index = C.index(max_C) + 1

for i in range(0,K):
    index = index -1

    score = score + C[index]
    score_list.append(score)

    index = P[index]

max_score = max(score_list)
print(max_score)

Submission status: Wrong Answer

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

#到達したかの判定
#masu=[0]*(n+1)
#nは1~n
def junkan(N):
  #到達したかの判定
  masu=[0]*(n+1)
  ans=0
  ans22=-(10**9+1)
  junkan_flag=False
  now_mas=p[N-1]
  count=0
  #このwhileはせいぜい5000
  while True:
    if masu[now_mas]==1:
      junkan_flag=True
      break
    count+=1
    ans+=c[now_mas-1]
    if ans22<=ans:
      ans22=ans
    masu[now_mas]=1
    now_mas=p[now_mas-1]
  if junkan_flag==True and ans>0:
    ans=(k//count)*ans
    for i in range(k-(k//count)*count):
      ans+=c[now_mas-1]
      if ans22<=ans:
        ans22=ans
      now_mas=p[now_mas-1]
    return max(ans,ans22)
  else:
    return max(ans,ans22)
hantei=0
answ=-(10**9+1)

for i in range(1,n+1):
  hantei=junkan(i)
  if answ <= hantei:
    answ=hantei
print(answ)

Submission status: Wrong Answer

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()))
reach = [False]*n
x = []
cx = []
for i in range(n):
    if reach[i]:continue
    buf = [c[i]]
    nexti = p[i]
    while nexti!=i:
        buf.append(c[nexti])
        reach[nexti] = True
        nexti = p[nexti]
    x.append(buf)
ans = []

import itertools
for i in x:
    n = k//len(i)
    a = sum(i)*n
    ind = k%len(i)
    ii = i+i
    r = list(itertools.accumulate(ii))
    for j in range(len(i)):
        for k in range(1,min(len(i),k+1)):
            s = r[j+k]-r[j]
            if k<ind+1:
                ans.append(a+s)
            ans.append(s)
print(max(ans))

Submission status: Wrong Answer

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()

P = In.ints()
C = [-1] + In.ints()

connection = [-1 for i in range(N+1)]

for i in range(N):
    connection[i+1] = P[i]

ans = -99999999999

for i in range(1, N+1):
    start = connection[i]
    tempans = C[start]
    tempk = K-1

    ans = max(ans, tempans)
    seen = [False for i in range(N+1)]
    seen[start] = True    

    while tempk > 0:
        nex = connection[start]
        if not seen[nex]:
            start=nex
            seen[start]=True
            tempans += C[start]
            ans = max(ans, tempans)
            tempk-=1            
        else:
            break
    
    if tempk>N:
        if tempans<0:
            continue
        
        
        stepsround = K-tempk
        howManyRounds = tempk//stepsround

        tempans += tempans*howManyRounds
        tempk-=howManyRounds*stepsround

        ans = max(ans, tempans)
    
    while tempk > 0:        
        start=connection[start]            
        tempans += C[start]
        ans = max(ans, tempans)
        tempk-=1            



Out.int(ans)


######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
p = list(map(int, input().split()))
p = [i-1 for i in p]
c = list(map(int, input().split()))
loops = []
used = set()
for i in range(n):
    if i in used:
        continue
    used.add(i)
    tmp = [i]
    nxt = p[i]
    while nxt not in used:
        tmp.append(nxt)
        used.add(nxt)
        nxt = p[nxt]
    loops.append(tmp)

def calc(l,r,cs):
    if r == 0:
        return 0
    tmp = -float("inf")
    for i in range(2*l):
        for j in range(i+1, min(2*l, i+r)+1):
            x = cs[j] - cs[i]
            if tmp < x:
                tmp = x
    return tmp

ans = -float("inf")

for loop in loops:
    s = sum(c[i] for i in loop)
    l = len(loop)
    tmp_loop_score = [c[i] for i in loop]
    for i in loop:
        tmp_loop_score.append(c[i])

    tmp_ans_max = max(tmp_loop_score)
    ans = max(ans, tmp_ans_max)

    cs = [0]
    for i in range(2*l):
        cs.append(cs[-1] + tmp_loop_score[i])

    if s > 0:
        m = k//l
        tmp_ans = m*s
        r = k%l
        tmp_ans += calc(l,r,cs)
        r = min(l, k)
        tmp_ans = max(tmp_ans, calc(l,r,cs))
    else:
        r = min(2*l, k)
        tmp_ans = calc(l,r,cs)

    ans = max(ans, tmp_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys

# 標準入力を取得
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

# 求解処理
ans = -sys.maxsize
for i in range(N):
    pos = i
    S = []
    score = 0
    while True:
        pos = P[pos] - 1
        score += C[pos]
        S.append(score)
        if pos == i:
            break
    length = len(S)

    if K <= length:
        ans = max(ans, max(S[:K]))
    else:
        if S[-1] > 0:
            if K % length == 0:
                ans = max(ans, int(K / length) * S[-1])
            else:
                ans = max(ans, int(K / length) * S[-1] + max(S[:(K % length)]))
        else:
            ans = max(ans, max(S))

# 結果出力
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
m = -1 * 10 ** 9 
for i in range(1, n+1):
    place = p[i-1]
    sm = [c[place-1]]
    while place != i:
        place = p[place-1]
        sm += [c[place-1] + sm[-1]]

    if len(sm) < k:
        m = max(m, 
            max(max(sm), 
                sm[-1] * (k // len(sm)) + sm[min(k % len(sm)-1, sm.index(max(sm)))]
                )
        )
    else:
        for j in range(k):
            m = max(m, sm[j])

print(m)

Submission status: Wrong Answer

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

INF=10**15

vis=[0]*(N+1)

def find_cycle(start):
  vis[start]=1
  his=[start]
  now=start
  cost=[]
  while 1:
    new = P[now-1]
    cost.append(C[new-1])
    if vis[new]==1:
      return his,cost
    his.append(new)
    vis[new]=1
    now=new

cycles=[]
costs=[]
for i in range(N):
  if not vis[i+1]:
    his,cost=find_cycle(i+1)
    cycles.append(his)
    costs.append(cost)
    
def cumsum(array):
    new=[0]
    for i in range(len(array)):
        new.append(array[i]+new[-1])
    return new 
    
cumcost=[]
for i in range(len(costs)):
  cost=costs[i]
  cumcost.append(cumsum(cost*2))
  
def best_margin_cost(idx,r1):
  out=-INF
  for r2 in range(1,r1+1):
    for i in range(len(costs[idx])):
      #print(idx,i,r2)
      tmp = cumcost[idx][i+r2]-cumcost[idx][i]
      out = max(tmp,out)
  return out
  
def opt_cost(idx):
  l = len(cycles[idx])
  SUM = sum(costs[idx])
  q,r=divmod(K,l)
  if K>=l and SUM>0:
    return SUM*q+best_margin_cost(idx,r) 
  elif K < l:
    return best_margin_cost(idx,K)
  else:
    return best_margin_cost(idx,l)

ans = -INF
for i in range(len(cycles)):
  ans = max(ans,opt_cost(i))
  
print(ans)