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

score_table=[]

for next_st in range(1,N+1):
    score_list=[0]
    zahyo=[]
    for i in range(N):
        next_st=P[next_st]
        if next_st in zahyo:
            break
        zahyo.append(next_st)
        score_list=score_list+[score_list[i]+C[next_st]]
    score_table.append(score_list)

#各点からの合計
ans=[0]*N

for i in range(N):
    if K>=N:
        if score_table[i][-1]<=0:
            ans[i] = max(score_table[i])
        else:
            ans[i] = score_table[i][-1]*K//N + max(score_table[i][0:K%N])
    else:
        ans[i] = max(score_table[i][0:K])

print(max(ans))

Submission status: Wrong Answer

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=0
check=set()

for i in range(N):
    
    if i in check:
        continue
    
    # create loop
    tmpK=K
    tmpans=0
    loop_check=set()
    tmp_idx=i
    loop=[]
    while tmp_idx not in loop_check:
        loop.append(C[tmp_idx])
        loop_check.add(tmp_idx)
        check.add(tmp_idx)
        tmp_idx=P[tmp_idx]
    
    S=sum(loop)
    L=len(loop)
    if S>=0:
        tmpans=S*(tmpK//L)
        tmpK%=L
    
    # 部分最大列を検索
    #print('loop',loop)
    loop*=2
    for i in range(len(loop)-1):
        loop[i+1]+=loop[i]
    n=2*L
    def init_min(init_min_val):
        #set_val
        for i in range(n):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res
    #####単位元######
    ide_ele_min = 10**15
    #num_min:n以上の最小の2のべき乗
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    init_min(loop)
    local_max=0
    for i,v in enumerate(loop):
        if i>=1:
            #print('v,min=',v,query_min(max(0,i-tmpK),i),v-query_min( max(0,i-tmpK),i ))
            local_max=max(local_max,v-query_min( max(0,i-tmpK),i ) )

    local_max2=0
    for i,v in enumerate(loop):
        if i>=1:
            #print('v,min=',v,query_min(max(0,i-tmpK),i),v-query_min( max(0,i-tmpK),i ))
            local_max2=max(local_max2,v-query_min( max(0,i-K),i ) )
    
    ans=max(ans,local_max+tmpans,local_max2)

if ans==0:
    print(max(C))
else:
    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()))
cp_max = -float('inf')

if n < k:
    k_rev = n
else:
    k_rev = k

for i in range(n):
    cp = 0
    a = p[i] - 1
    for j in range(k_rev):
        cp += c[a]
        a = p[a] - 1
        cp_max = max(cp_max, cp)
    if n < k:
        for x in range(k - n):
            if c[a] >= 0:
                cp += c[a]
                a = p[a] - 1
                cp_max = max(cp_max, cp)
            elif c[a] < 0:
                break

print(cp_max)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
def read_p(s):
    return int(s) - 1
p = list(map(read_p,input().split()))
c = list(map(int,input().split()))

if k < n:
    ans = 0
    for i in range(n):
        s = 0
        at = i
        for _ in range(k):
            at = p[at]
            s += c[at]
            ans = max(s, ans)
    print(ans)
else:
    g = []
    f = [0]*n
    for i in range(n):
        if f[i] == 0:
            at = i
            t = []
            for _ in range(n):
                t.append(at)
                f[at] = 1
                at = p[at]
                if at == i:
                    break
            g.append(t)
    ans = 0
    
    for t in g:
        teamScore = 0
        allMinus = False
        maxMember = -10e9
        for i in t:
            teamScore += p[i]
            maxMember = max(maxMember, i)
        if teamScore > 0:
            teamScore *= (k//len(t))
        else:
            allMinus = True
            teamScore = 0

        for i in range(len(t)):
            s = teamScore
            at = t[i]
            for _ in range(k%len(t)):
                at = p[at]
                s += c[at]
                ans = max(s, teamScore)
        if allMinus:
            teamScore = max(teamScore, maxMember)
        
        ans = max(ans, teamScore)
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
P  = [0] + list(map(int,input().split()))
C = [0] + list(map(int,input().split()))

L = [[] for i in range(n+1)]
length = [0]*(n+1)

for i in range(1,n+1):
    x = i

    s = set([])
    sw = 0
    for j in range(1,n+1):

        x = P[x]
        if P[x] in s and sw == 0:
            length[i] = j-1
            sw = 1
            
        s.add(P[x])
        point = C[x]
        if L[i] != []:
            L[i].append(L[i][-1]+C[x])
        else:
            L[i].append(C[x])
            
    if sw == 0:
        length[i] = n


ans = - float("Inf")

if k > n:

    for i in range(1,n+1):
        m = k//length[i]
        p = k%length[i]
        if p == 0:
             point = m * L[i][length[i]-1]
        else:
            point = m * L[i][length[i]-1] + max(L[i][:p])

        ans = max(ans, point)
    
    for a in L[1:]:
        if a != []:
            ans = max(max(a[:n]), ans)
        
else:
    for a in L[1:]:
        if a != []:
            ans = max(max(a[:k]), 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()))
l = [0] * n


tl = 0
ta = 0
ml = 0
for i in range(n):
    s = set()
    ta = p[i]-1
    tl = c[i]
    l[i] = tl
    for j in range(k):

        if ta in s:
            if tl > 0:
                l[i] = tl*(k//(len(s)))
                ttl = 0
                ta = p[i]-1
                tl = 0
                for aaa in range(k//(len(s))):
                    tl += c[ta]
                    ta = p[ta]-1
                    ttl = max(ttl,tl)
                l[i] += ttl
            break
        else:
            s.add(ta)
        
        tl += c[ta]
        l[i] = max(l[i],tl)
        ta = p[ta]-1
    
print(max(l))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
INF = 10**18
ans = -INF
for i in range(N):
    arr = []
    tot = 0
    rest = K
    visited = {}
    visited[i] = rest
    point = {}
    point[i] = 0
    nex = i
    while rest:
        nex = P[nex]
        tot += C[nex]
        arr.append(tot)
        rest -= 1
        if nex in visited:
            loop = visited[nex]-rest
            loop_point = tot-point[nex]
            tmp_tot = tot
            tmp_rest = min(rest, loop)
            while tmp_rest:
                nex = P[nex]
                tmp_tot += C[nex]
                arr.append(tmp_tot)
                tmp_rest -= 1
            if loop_point > 0:
                tot += (rest//loop)*loop_point
                arr.append(tot)
                rest = rest%loop
            else:
                rest = min(rest, loop)
            break
        else:
            visited[nex] = rest
            point[nex] = tot
    #print(i, arr)
    ans = max(ans, max(arr))
print(ans)

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()))
was = [False]*n
sums = []
for i in range(n):
    if not was[i]:
        iWas = [False]*n
        pos = i
        sumn = [c[i]]
        while not iWas[pos]:
            iWas[pos] = True
            was[pos] = True
            pos = p[pos]-1
            sumn+=[c[pos]]
        sumn = sumn[:-1]
        sums.append(sumn)
m = -99999999999999999999999
for i in range(len(sums)):
    totS = sum(sums[i])
    l = len(sums[i])
    for g in range(len(sums[i])):
        arr = []
        s = 0
        for j in range(l):
            s+=sums[i][(g+j)%l]
            arr.append(s)

        if totS > 1:
            if k%l:
                m = max(m,totS*(k//l)+max(arr[:k%l]))
            else:
                max(m, totS * (k // l))
        else:

            m = max(m, max(arr[:min(l,k)]))
print(m)

Submission status: Wrong Answer

Solution code:
def resolve():
    N, K = map(int, input().split())
    P, C = [-1], [-1]
    P += list(map(int, input().split()))
    C += list(map(int, input().split()))
    ans = -(10**9+1)

    for x in range(1,N+1):
        k = K
        score, max_score = 0, 0
        while k > 0:
            x = P[x]
            score += C[x]
            max_score = max(max_score, score)
            k -= 1
        ans = max(max_score, ans)
            
    print(ans)
    
resolve()

Submission status: Wrong Answer

Solution code:
def find(vals,l):
    ans = 0
    for i in range(len(vals)//2):
        curr = vals[i+l-1]
        if i-1 >= 0:
            curr -= vals[i-1]

        ans = max(ans,curr)

    #print(ans,l)
    return ans

def dfs(edges,node,k,costs,visited):
    nodes = []
    stack = [node]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            nodes.append(node)
            stack.append(edges[node])

    vals = []
    for node in nodes:
        vals.append(costs[node-1])

    for i in range(1,len(vals)):
        vals[i] += vals[i-1]

    total = vals[-1]
    if total >= 0:
        ans = total*(k//len(vals))
    else:
        ans = 0

    val = 0
    k %= len(vals)
    vals.extend(vals)
    for i in range(1,k+1):
        val = max(val,find(vals,i))

    return ans+val

def main():
    n,k = map(int,input().split())
    perm = list(map(int,input().split()))
    costs = list(map(int,input().split()))
    edges = [-1]*(n+1)
    for i in range(n):
        edges[i+1] = perm[i]

    ans = 0
    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            ans = max(ans,dfs(edges,i,k,costs,visited))

    print(ans)

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()))
mx=-float("inf")


for i in range(n):
  sc=0
  pn=i
  if k<=n:
    for j in range(k):
      pn=p[pn]-1
      sc+=c[pn]
      mx=max(mx,sc)
  else:
    lp=[]
    for j in range(n):
      pn=p[pn]-1
      sc+=c[pn]
      lp.append(sc)
      mx=max(mx,sc)
    sc=(k//n)*sc+lp[k%n]
    mx=max(mx,sc)
   #print(sc,lp)
print(mx)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
p = list(int(x)-1 for x in input().split())
c = list(map(int, input().split()))
score = 0
for i in range(n):
  loop = []
  rec = [0]
  here = i
  loop.append(here)
  for _ in range(k):
    here = p[here]
    if here not in loop:
      loop.append(here)
      rec.append(rec[-1]+c[here])
    else:
      rec.append(rec[-1]+c[here])
      break
  if len(loop)<k:
    s = max(rec)+rec[-1]
  else:
    s = max(rec)
  score = max(s,score)
print(score)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
P = [-1]+list(map(int,input().split()))
C = [-1]+list(map(int,input().split()))
visited = [True]+[False]*n
circles = []
for i in range(1,n+1):
    if not visited[i]:
        pre = i
        visited[i]=True
        s = [C[i]]
        while P[i] != pre:
            s.append(C[P[i]])
            visited[P[i]] = True
            i = P[i]
        circles.append((s,sum(s)))
# print(circles)
ans1 = 0

anslist = []

for ci in circles:
    ci_ans = 0
    if ci[1] > 0:
        ci_ans += ci[1]*(k//len(ci[0]))
    acc = list(accumulate(ci[0]*2))
    maxi = 0
    ci2 = 2*ci[0]
    for d in range(1,min(len(ci[0]),ci[1]*k % len(ci[0])+1)):
        for i in range(d,len(ci2)):
            maxi = max(maxi,ci2[i]-ci2[i-d])
    ci_ans += maxi
    anslist.append(ci_ans)
print(max(anslist))

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]


N, K = map(int, input().split())
P = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ans = 0
sco = 0
bas = 0

if(N>K):
    for i in range(N):
        sco = C[P[i]-1]
        bas = P[i]-1
        ans = max(ans, sco)
        for j in range(K-1):
            sco += C[P[bas]-1]
            bas = P[bas]-1
            ans = max(ans, sco)
    print(ans)

else:
    sco2 = [0]*N
    ans2 = [0]*N
    kai = [0]*N
    for i in range(N):
        sco2[i] = C[P[i]-1]
        bas = P[i]-1
        ans2[i] = sco2[i]
        #if(i==bas):
        #    kai[i] = 1
        #    break
        for j in range(N):
            sco2[i] += C[P[bas]-1]
            bas = P[bas]-1
            ans2[i] = max(ans2[i], sco2[i])
            if(P[i]-1==bas):
                kai[i] = j+2
                break
    for i in range(N):
        if(ans2[i]>sco2[i]):
            break
        nok = K-kai[i]
        sco2[i] = sco2[i]*(nok//kai[i])
        ans2[i] = max(ans2[i], sco2[i])
        nok = nok%kai[i]
        bas = i
        for j in range(nok):
            bas = P[bas]-1
            sco2[i] += C[P[bas]-1]
            ans2[i] = max(ans2[i], sco2[i])
    print(max(ans2))

Submission status: Wrong Answer

Solution code:
L1=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
N,K=L1[0],L1[1]

print(8)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
P = [int(_) - 1 for _ in input().split()]
C = [int(_) for _ in input().split()]

max_point = - math.inf

for start in range(N):
  i = start
  p_seq = []
  c_seq = []
  visited = set([i])

  for _ in range(K):
    i = P[i]
    p_seq.append(P[i])
    c_seq.append(C[i])
    if i in visited:
      break
    visited.add(i)
  
  len_rep = len(c_seq)
  inc = sum(c_seq)

  point = - math.inf
  if len_rep == K:
    cur = None
    for c in c_seq:
      cur = cur + c if cur is not None else c
      point = max(cur, point)
  elif inc <= 0:
    cur = None
    for c in c_seq[:K % len_rep]:
      cur = cur + c if cur is not None else c
      point = max(cur, point)
  else:
    cur = inc * (K // len_rep)
    for c in c_seq[:K % len_rep]:
      cur = cur + c if cur is not None else c
      point = max(cur, point)
  
  max_point = max(max_point, point)
  

  

    
print(max_point)

Submission status: Wrong Answer

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
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 = -10 ** 30

dic = {}

for n in range(N):
    tmax = -10**30
    t = 0
    c = 0
    ni = n
    goto = True

    if not n in dic:
        while True:
            t += C[ni]
            c += 1
            ni = P[ni]
            tmax = max(t, tmax)
            if n == ni:
                break
            if c == K:
                ans = max(ans, tmax)
                goto = False
                break


        ni = n
        for i in range(c):
            dic[ni] = [c, t]
            n = P[ni]

    else:
        c = dic[n][0]
        t = dic[n][1]

    if goto:
        t *= (K // c)
        tt = t
        ni = n
        for i in range(K % c):
            t += C[ni]
            c += 1
            ni = P[ni]
            tt = max(t, tt)

        ans = max(ans, tmax, tt)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
C = list(map(int,input().split()))
C.insert(0,0)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        a = [i]
        hist[i]=1
        j = i
        while True:
            if hist[P[j]]==0:
                a.append(P[j])
                hist[P[j]]=1
                j = P[j]
            else:break
        A.append(a)
B = []
for i in range(len(A)):
    a = A[i]
    n = len(a)
    b = []
    for j in range(n):
        b.append(C[a[j]])
    B.append(b)
S = {}
for i in range(len(B)):
    if i not in S:
        S[i] = {}
    n = len(B[i])
    a = B[i]+B[i]
    b = [0 for _ in range(2*n+1)]
    for j in range(1,2*n+1):
        b[j] = b[j-1]+a[j-1]
    for k in range(1,n+1):
        S[i][k]=-10**10
        for j in range(2*n-k+1):
            S[i][k] = max(S[i][k],b[j+k]-b[j])
ans = -10**10
for i in range(len(B)):
    n = len(B[i])
    a = B[i]+B[i]
    if K<=n:
        for k in range(1,K+1):
            ans = max(ans,S[i][k])
    else:
        if S[i][n]>0:
            cnt = (K//n-1)*S[i][n]
            cmax = -10**10
            b = [0 for _ in range(2*n+1)]
            for j in range(1,2*n+1):
                b[j] = b[j-1]+a[j-1]
            cnt1 = -10**10
            for k in range(1,n+K%n+1):
                for j in range(n+K%n+1-k+1):
                    cnt1 = max(cnt1,b[j+k]-b[j])
            cnt += cnt1
            ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,K = [int(i) for i in input().split()]
P = [int(i)-1 for i in input().split()]
C = [int(i) for i in input().split()]
places = []
n = 0
i = 0
T = list(range(N))
while n < N:
    L = [i]
    T.remove(i)
    n += 1
    for _ in range(N):
        if not P[i] in L:
            i = P[i]
            T.remove(i)
            L.append(i)
            n += 1
        else:
             break
    places.append(L)
    if T:
        i = T[0]
scores = []
for L in places:
    s = 0
    M = []
    for l in L:
        s += C[l]
        M.append(s)
    scores.append(M)
ans = -(10**9)
for L in scores:
    l = len(L)
    if K >= l:
        ans = max(ans,L[-1])
        if L[-1] > 0:
            ans = max(ans,L[-1] * (K//l))
    for i in range(l):
       ans = max(ans,L[i])
    for i,j in itertools.combinations(range(l),2):
        if j-i <= K:
            n = 0
            if L[-1] > 0:
                n = L[-1] * ((K-j+i)//l)
            ans = max(ans, L[j]-L[i]+n)
        if N-j+i <= K:
            n=0
            if L[-1]>0:
                n= L[-1] * ((K-l+j-i)//l)
            ans = max(ans,L[i] + L[-1] - L[j]+n)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, P, C):
    P = [p-1 for p in P]
    S = [[0] * (N+1) for _ in range(N)]


    if K < 2*N:
    # if True:
        ans = -INF
        for i in range(N):
            c = i
            a = 0
            for j in range(K):
                n = P[c]
                a += C[n]
                ans = max(ans, a)
                c = n
        error_print('--')
        return ans

    ga = -INF
    for i in range(N):
        c = i
        done = {c: 0}
        S[i][0] = C[i]
        ans = -INF
        for j in range(1, N+1):
            n = P[c]
            S[i][j] = C[n] + S[i][j-1]
            c = n
            if n in done:
                break
            else:
                done[n] = j
        ans = max(ans, S[i][1] - C[i])
        ans = max(ans, S[i][done[n]] - C[i])
        if S[i][j] - S[i][done[n]] > 0:
            ans = S[i][done[n]]
            a = S[i][j] - S[i][done[n]]
            l = j - done[n]
            k = K - done[n]
            m = (k // l)
            if m > 0:
                m -= 1
            ans += a * m
            rem = K - m * l - done[n]
            c = n
            b = ans
            for _ in range(rem):
                n = P[c]
                b += C[n]
                ans = max(ans, b)
                c = n
            ans -= C[i]
        # print(i, ans)
        ga = max(ga, ans)

    return ga


    # from pprint import pprint
    # pprint(S)

    # for i in range(N):



def main():
    N, K = read_int_n()
    P = read_int_n()
    C = read_int_n()
    print(slv(N, K, P, C))


if __name__ == '__main__':
    main()

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()))
z=-10000000000000
lin=[0]*n
lstart=[]
llen=[]
loopsum=[]
loopstructure=[]
stsc=[]
for i in range(n):
    if lin[i]==0:
        lstart.append(i)
        d=i
        f=0
        v=0
        strc=[i]
        sc=[c[i]]
        while lin[d]==0:
            lin[d]=1
            d=p[d]-1
            strc.append(d)
            sc.append(c[d])
            f+=1
            v+=c[d]
            if i==d :
                llen.append(f)
                loopsum.append(v)
                loopstructure.append(strc)
                stsc.append(sc)                
for j in range(len(stsc)):
    o=len(stsc[j])-1
    x=-10000000000000
    y=-10000000000000
    q=min(o,k)
    for i in range(o):
        for ii in range(1,q+1):
            if i+ii<o:
                ny=sum(stsc[j][i:i+ii])
            else:
                ny=sum(stsc[j][0:i+ii-o]+stsc[j][i:o])
            if ny>y:
                y=ny

                
    nz=max((k//o)*loopsum[j]+y,y)
    if nz>z:
        z=nz
print(z)

Submission status: Wrong Answer

Solution code:
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")

def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()


n,k = Ri()
a = Ri(); a = [i-1 for i in a]
c = Ri()

lis = []
vis = [False]*n
for i in range(n):
    if not vis[i]:
        temp = []
        nex = i
        while True:
            temp.append(c[nex])
            vis[nex] = True
            nex = a[nex]
            if vis[nex] : break
        lis.append(temp)
summ = []
# print(lis)

for i in range(len(lis)):
    temp = [0]*(len(lis[i]) + 1)
    for j in range(len(lis[i])):
        temp[j+1] = temp[j] + lis[i][j]
    summ.append(temp[:])

# print(summ)
maxxans= -INF
for i in range(len(lis)):
    actualcircle = k//len(lis[i])
    # print(actualcircle)
    for krem in range(1, min(n, k)+1):
        tot = summ[i][-1]
        cnt = len(lis[i])
        tempans = tot*(krem//cnt)
        rem = krem%cnt
        for j in range(len(lis[i])):
            if j + rem -1 >= cnt:
                temp = summ[i][-1] - summ[i][j]
                totrem = rem - ((cnt-1) - j +1)
                temp += summ[i][totrem]
                maxxans = max(maxxans, temp + tempans)
            else:
                maxxans = max(maxxans, tempans + summ[i][j+rem] - summ[i][j])
        tempans = tot*actualcircle
        
        if krem <= len(lis[i])%k:
            # print(tempans)
            for j in range(len(lis[i])):
                if j + rem -1 >= cnt:
                    temp = summ[i][-1] - summ[i][j]
                    totrem = rem - ((cnt-1) - j +1)
                    temp += summ[i][totrem]
                    maxxans = max(maxxans, temp + tempans)
                else:
                    maxxans = max(maxxans, tempans + summ[i][j+rem] - summ[i][j])
            # print(maxxans)
print(maxxans)

Submission status: Wrong Answer

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

    scores = [c[p[0] - 1]]
    previous = p[0]
    for i in range(1, n):
        scores.append(c[previous - 1])
        previous = p[previous - 1]
    sum_score = sum(scores)
    # start_point
    acc_table = [[i] for i in scores]
    for i in range(n):
        acc_table[i].append(scores[i])
        for j in range(1, n):
            acc_table[i].append(acc_table[i][-1] + scores[(i + j) % n])

    if sum_score > 0:
        rest = k % n
        sum_scores = sum_score * int(k / n)
        print(sum_scores + max([acc_table[i][rest] for i in range(n)]))
    else:
        print(max(acc_table))

Submission status: Wrong Answer

Solution code:
import sys


def _ia(): return map(int, sys.stdin.readline().strip().split())


def calc(arr, k):
    s = sum(arr)
    n = len(arr)
    flag = s > 0 and k >= n

    kp = k % n if flag else k
    l = min(kp, n)

    cm = max(arr) if s <= 0 else 0
    for i in range(n):
        cn = 0
        for ki in range(i, i+l):
            cn += arr[ki % n]
            cm = max(cn, cm)

    if flag:
        return s * (k//n) + cm
    else:
        return cm


def main():
    n, k = _ia()
    p = list(map(lambda x: x-1, _ia()))
    c = list(_ia())

    f = [False] * n
    g = []
    for idx in range(n):
        if f[idx]:
            continue

        nxt = idx
        tmp = [c[nxt]]
        f[nxt] = True

        for _ in range(n):
            nxt = p[nxt]
            if nxt == idx:
                break
            tmp.append(c[nxt])
            f[nxt] = True

        g.append(tmp)

    return max(calc(gi, k) for gi in g)


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

Submission status: Wrong Answer

Solution code:
import math

n, k = map(int, input().split(" "))
pL = list(map(int, input().split(" ")))
cL = list(map(int, input().split(" ")))

if len(list(filter(lambda x: x > 0, cL))) == 0:
    print(max(cL))
    exit()

ans = 0
for i in range(n):
    sm = []
    crnt = pL[i]
    for _ in range(min(k, n)):
        if pL[i] == crnt - 1:
            break
        sm.append(cL[crnt - 1])
        crnt = pL[crnt - 1]
    t = sum(sm)

    a = 0
    if t >= 0:
        a = t * (k // n)

    mi = 0
    s = 0
    for j in range(len(sm)):
        s += sm[j]
        mi = max(mi, s)

    ans = max(ans, mi + a)

print(ans)