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:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, K = mulinputs()
    ind_p = list(map(lambda x: int(x)-1,input().split()))
    ind_c = list(mulinputs())
    tokuten = [0] * N
    for i in range(N):
        p, c = ind_p[i], ind_c[i]
        tokuten[p] = c
    soutokuten = [(0, ind_p[i]) for i in range(N)]
    tokuten_max = 0
    # 試行回数
    for i in range(min(N,K)):
        # スタート地点
        for j in range(N):
            next = soutokuten[j][1]
            tmp = soutokuten[j][0] + tokuten[next]
            soutokuten[j] = (tmp, ind_p[next])
        tokuten_max = max(tokuten_max, *map(lambda t: t[0], soutokuten))
    print(tokuten_max)

    # # find and classificate path
    # visited = [False] * N
    # paths = []
    # while not all(visited):
    #     for p in ind_p:
    #         if visited[p]:
    #             continue
    #         p0 = p
    #         path = [p0]
    #         visited[p0] = True
    #         while p0:
    #             p0 = ind_p[p0]
    #             if visited[p0]:
    #                 break
    #             path.append(p0)
    #             visited[p0] = True
    #         paths.append(path)
    # print(paths)
    # ruisekis = {}
    # for path in paths:
    #     ruiseki = [0] * (len(path)+1)
    #     for i, p in enumerate(path):
    #         ruiseki[i+1] = ruiseki[i] + tokuten[p]
    #     ruiseki = ruiseki[1:]
    #     ruisekis[str(path)] = ruiseki
    # print(ruisekis)


    # for i in range(N):
    #     p, c = ind_p[i], ind_c[i]
    #     indatas.append((p,c))
    # print(indatas)
    # indatas.sort()
    # print(indatas)
# 
    # ruiseki = [0] * (N+1)
    # for i in range(1, N+1):
    #     ruiseki[i] = ruiseki[i-1] + indatas[i-1][1]
    # ruiseki = ruiseki[1:]
    # print(ruiseki)

Submission status: Wrong Answer

Solution code:
N_K = input()
N_K_lis = N_K.split()
N = int(N_K_lis[0])
K = int(N_K_lis[1])
Pall = input()
P = Pall.split()
Call = input()
C = Call.split()
l = []
score = 0
for n in range(0,N):
  stP = int(P[n])
  stC = int(C[stP-1])
  for k in range(K):
    n = int(P[n])-1
    score = score + int(C[int(P[n])-1])
    l.append(score)
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()))

DP=[[C[P[n]]] for n in range(N)]

for start in range(N):
    visited=set()
    cur=P[start]
    while cur not in visited:
        visited.add(cur)
        cur = P[cur]
        DP[start].append(C[cur]+DP[start][-1])


for n in range(N):
    DP[n]=DP[n][:-1]

ans=-float("inf")
ans_start=None

for start in range(N):
    #pattern1(先に進んでからloopする)
    tmp_max=-float("inf")
    tmp_idx=None

    for i in range(min(K,len(DP[start]))):
        if tmp_max<DP[start][i]:
            tmp_max=DP[start][i]
            tmp_idx=i


    K_=K-tmp_idx-1
    if K_>=len(DP[start]) and DP[start][-1]>0:
        loop_cnt=K_//len(DP[start])
        tmp_max+=loop_cnt*DP[start][-1]

    ans=max(ans,tmp_max)

    #pattern2(loopしてから余を加算
    tmp_max=-float("inf")

    if DP[start][-1]>0:
        if K>=len(DP[start]) and DP[start][-1]>0:
           loop_cnt=K//len(DP[start])
           tmp_max+=loop_cnt*DP[start][-1]

        max_stop=0
        for i in range(K%len(DP[start])):
            max_stop=DP[start][i]
        tmp_max+=max_stop
        ans=max(ans,tmp_max)
print(ans)

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)

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

    ans = max(ans, mi + a)

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()))
ans = []
for i in range(n):
    visit = [-1 for j in range(n)]
    cou = 0
    visit[i] = 0
    kar = []
    now = i
    while True:
        cou += 1
        if cou > k:
            break
        nex = p[now] - 1
        if visit[nex] == -1:
            visit[nex] = cou
            if kar:
                kar.append(kar[-1] + c[nex])
            else:
                kar.append(c[nex])
            now = nex
        elif visit[nex] != -1:
            if kar:
                lokz = cou
                losu = kar[-1] + c[nex]
                if losu > 0:
                    if k % lokz == 0:
                        kar.append(losu * (k//lokz))
                    elif k % lokz != 0:
                        tyu = losu * (k//lokz)
                        tyu += max(0,max(kar[:(k%lokz)]))
                        kar.append(tyu)
            else:
                if c[nex] >= 0:
                    kar.append(c[nex]*k)
                elif c[nex] < 0:
                    kar.append(c[nex])
            break
    ans.append(max(kar))
print(max(ans))

Submission status: Wrong Answer

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

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

ans = [0] * N
P = list(map(lambda x:x-1,P))

def rec(visited,next):
    if next in s:
        return visited,visited.index(next)
    else:
        s.add(next)
        visited.append(next)
        return rec(visited,P[next])

for i in range(N):
    s = set([i])
    visited = [i]
    a = 0
    visited,loopStart = rec(visited,P[i])
    # print(visited,loopStart)
    if K < len(visited):
        al = np.array([],dtype='int')
        for j in range(1,len(visited)):
            al = np.append(al,C[j])
        a = al.cumsum().max()
        # print(a)
        # a = acum.max()
    else:
        al = np.array([],dtype='int')
        for j in range(1,len(visited)):
            al = np.append(al,C[j])
        visitedLoop = visited[loopStart:]
        if sum(visitedLoop)<=0:
            a = al.cumsum().max()
        else:
            # 残り回数を循環配列の長さで割った余り
            q,mod = divmod((K-loopStart),len(visitedLoop))
            C_sum = 0
            for j in range(len(visitedLoop)):
                C_sum += C[j]
            am = np.array([],dtype='int')
            for j in range(mod):
                am = np.append(am,C[j])
            am_sum = 0
            if not len(am)==0:
                print(am)
                am_sum = am.cumsum().max()
            a = al[len(visited)-2] + q*C_sum + am_sum
    ans[i]=a

print(max(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()))

INF=10**10

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 cost
    his.append(new)
    vis[new]=1
    now=new

costs=[]
for i in range(N):
  if not vis[i+1]:
    cost=find_cycle(i+1)
    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])):
      tmp = cumcost[idx][i+r2]-cumcost[idx][i]
      out = max(tmp,out)
  return out
  
def opt_cost(idx):
  l = len(costs[idx])
  SUM = sum(costs[idx])
  q,r=divmod(K,l)
  if K>=l:
    return max(SUM*q+best_margin_cost(idx,r),best_margin_cost(idx,l))
  else:
    return best_margin_cost(idx,K)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
INF = 10**18

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

    ans = -INF
    for start in range(N):
        T = K
        S = {start: 0}
        seq = {start: 0}
        t = start
        while T > 0 and not P[t]-1 in S:
            seq[P[t]-1] = seq[t] + 1
            S[P[t]-1] = S[t] + C[P[t]-1]
            ans = max(ans, S[P[t]-1])
            t = P[t] - 1
            T -= 1
        if T > 0:
            scoredelta = S[t] + C[P[t]-1] - S[P[t]-1]
            cycle = seq[t] + 1 - seq[P[t] - 1]
            score = S[P[t]-1]
            T += cycle - 1
            count = T // cycle - 1
            T -= count * cycle
            score += count * scoredelta
            ans = max(ans, score)
            t = P[t]-1
            while T > 0:
                score += C[t]
                ans = max(ans, score)
                t = P[t]-1
                T -= 1
    print(ans)

if __name__ == "__main__":
    main()

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()))
maxsc = -1E20
for s in range(1,n+1):
  x = s
  sc = [0]
  i = 0
  while i<k:
    x = p[x]
    sc.append(sc[i]+c[x])
    i += 1
    if x == s:
      loop = i
      loopsc = sc[i]
      if loopsc > 0:
        baseup = loopsc * int((k-i)/loop)
        for j in range(loop):
          sc[j+1] += baseup
        for j in range((k-i)%loop):
          sc[j+1] += loopsc
      i=k
  maxsc = max(maxsc, max(sc))
print(maxsc)

Submission status: Wrong Answer

Solution code:
INF = 10**15

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

moudeta = [0]*(N+1)

gogolist = []

for i in range(1,N+1):
    if moudeta[i]==1:
        continue
    gogolist.append([])
    now = i
    gogolist[len(gogolist)-1].append(now)
    moudeta[i]=1
    now = P[i]
    while now != i:
        gogolist[len(gogolist)-1].append(now)
        moudeta[now]=1
        now = P[now]
for i in range(len(gogolist)):
    gogolist[i] = gogolist[i]+gogolist[i]

ret = -INF
for golis in gogolist:
    around = 0
    for i in range(len(golis)//2):
        around += C[golis[i]]

    ans = -INF
    ansgo = -INF
    for i in range(len(golis)//2):
        tmpans = -INF
        tmp = 0
        for j in range(K%(len(golis)//2)):
            tmp+=C[golis[i+j]]
            tmpans = max(tmpans,tmp)    
        ans = max(ans,tmpans)
        
        tmpansgo = -INF
        tmp = 0
        for j in range(min(len(golis)//2,K)):
            tmp+=C[golis[i+j]]
            tmpansgo = max(tmpansgo,tmp)
        ansgo = max(ansgo,tmpansgo)

    ret = max(around,ansgo,around*(K//N)+ans,ret,around*(K//N-1)+ansgo)


print(ret)

Submission status: Wrong Answer

Solution code:

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

P = list(map(int, input().split()))

C = list(map(int, input().split()))

d=[[] for i in range(N)]
for i in range(N):
    if P[i]!=-1:
        x=P[i]
        P[i]=-1
        while(x!=-1):
            d[i].append(x)
            y=x
            x=P[x-1]
            P[y-1] = -1

c=[[] for i in range(N)]
for i in range(N):
    for j in range(len(d[i])):
        c[i].append(C[d[i][j]-1])

for i in range(N):
    for j in range(len(c[i])):
        c[i]=sorted(c[i], reverse=True)


A=[]
for i in range(N):
    if len(d[i])!=0:
        a = 0
        b = 0
        q = K // len(d[i])
        r = K % len(d[i])
        a += q * sum(c[i])
        if r != 0:
            for j in range(r):
                if c[i][j]>0:
                    a += c[i][j]
        if K>=len(d[i]):
            for j in range(len(d[i])):
                if c[i][j] > 0:
                    b += c[i][j]
        if K < len(d[i]):
            for j in range(K):
                if c[i][j] > 0:
                    b += c[i][j]
        A.append(max(a,b))

print(max(A))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
loop=[]
v=[1]*n
for i in range(n):
  if v[i]:
    t=[]
    x=i
    while v[x]:
      v[x]=0
      t.append(x)
      x=p[x]-1
    loop.append(t)
ans=0
for l in loop:
  le=len(l)
  t=[c[i] for i in l]
  t=t*2
  if le<k:
    kk=le
  else:
    kk=k
  dp=[0]*kk
  st=[1]*kk
  dp[0]=max(0,t[0])
  for i in range(1,kk):
    dp[i]=max(dp[i-1]+t[i],0)
    if t[i]>=0:
      st[i]=st[i-1]+1
  ans=max(ans,max(dp))
  leng=st[dp.index(max(dp))]
  wa=sum(t)//2
  if wa>0 and k>le:
    ans+=(wa*((k-leng)//le))
f=1
for i in c:
  if i>=0:
    f=0
    break
if f:
  ans=max(c)
print(ans)

Submission status: Wrong Answer

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

memo = [[]  for i in range(n)]
for i in range(n):
    memo[i].append(C[i])
    j = P[i]
    while True:
        memo[i].append(memo[i][-1] + C[j])
        j = P[j]
        if j == i:
            memo[i].append(memo[i][-1] + C[j])
            break

if k <= n:
    ans = max(max(memo[i][:k]) for i in range(n))
    print(ans)
else:
    m = k // n
    k %= n
    circles = [memo[i][-1] - memo[i][0] for i in range(n)]
    if all(c<=0 for c in circles):
        ans = max(max(memo[i]) for i in range(n))
        print(ans)
    else:
        ans = -1e10
        for i  in range(n):
            alt = max(memo[i][:k]) + circles[i] * m
            ans = max(alt, ans)
            alt =  max(memo[i]) + circles[i] * (m-1)
            ans = max(alt, ans)
        print(ans)

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))
        ln = len(score)
        p = k % ln
        c = max(0, sum(score)) * (k // ln)
        l, r = 0, 1
        while l < ln:
            if r - l > p:
                l += 1
                r = l + 1
            ans = max(ans, S[r] - S[l] + c)
            r += 1
        l, r = 0, 1
        while l < ln:
            if r - l > ln:
                l += 1
                r = l + 1
            ans = max(ans, S[r] - S[l])
            r += 1


    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()))
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)+1))
                ttl = 0
                ta = p[i]-1
                tl = 0
                for aaa in range(k//(len(s)+1)):
                    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:
import sys
import numpy as np
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
PG = {}
CG = {}
G = [-1] * (N + 1)


def f(n):
    if G[n] == -1:
        idx = len(PG) + 1
        _P = []
        _C = []
        i = n
        while True:
            if P[i] in _P:
                break
            _P.append(P[i])
            _C.append(C[P[i]])
            G[P[i]] = idx
            i = P[i]
        PG[idx] = _P
        CG[idx] = _C
    else:
        _P = PG[G[n]]
        _C = CG[G[n]]
        idx = _P.index(n) + 1
        # print(f'{idx=}')
        _P = _P[idx:] + _P[:idx]
        _C = _C[idx:] + _C[:idx]
    # print(f'{_P=}, {_C=}')
    if len(_P) < K:  # ぐるぐる回れる
        cumsum = np.array(_C).cumsum()
        if cumsum[-1] <= 0:  # cumsumの最後が0以下だったらぐるぐる回らずmaxのところでやめる
            ans = cumsum.max()
            # print(f'case 1 {cumsum=}, {ans=}')
            return ans
        div, mod = divmod(K, len(_P))
        if mod != 0:
            ans = div * cumsum[-1]
            ans = max(ans, ans + cumsum[:mod].max())
            return ans
        else:
            ans = div * cumsum[-1]
            return ans
    else:
        cumsum = np.array(_C[:K]).cumsum()
        ans = cumsum.max()
        # print(f'{cumsum=}, {ans=}')
        return ans


# f(1)
# print('')
# f(2)
# print('')
# f(3)
# print('')
# f(4)
# print('')
# f(5)

ans = f(1)
for i in range(1, N + 1):
    ans = max(ans, f(i))
# print(f'last answer = {ans}')
# print(f'{G=}, {PG=}, {CG=}')
print(ans)

Submission status: Wrong Answer

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

s=[]
ty=[]
for v in range(k):
  
  for u in range(n):
    x=p[u]
    s.append(0)
    for j in range(v+1):
      e=s[u+v]
      s[u+v]=e+c[x-1]
      x=p[x-1]
    ty.append(s[u+v])

print(max(ty))

Submission status: Wrong Answer

Solution code:
def solve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pd = {i: x for i, x in enumerate(p, 1)}
    cd = {i: x for i, x in enumerate(c, 1)}
    ans = -10 ** 10
    for i in range(1, n + 1):
        res = 0
        x = i
        for j in range(1, min(15001,k + 1)):
            res += cd[x]
            x = pd[x]
            ans = max(res, ans)
    print(ans)


solve()

Submission status: Wrong Answer

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

loop = [ -1 for _ in range( n ) ]
loop_score = [ 0 for _ in range( n ) ]
loop_length = [ 0 for _ in range( n ) ]
for i in range( n ):
    if loop[ i ] == -1:
        score = 0
        length = 1
        loop[ i ] = i
        j = p[ i ] - 1
        while j != i:
            loop[ j ] = i
            score += c[ p[ j ] - 1 ]
            j = p[ j ] - 1
            length += 1
        loop_score[ i ] = score + c[ p[ i ] - 1 ]
        loop_length[ i ] = length

# print( loop, loop_score, loop_length)

def solve( start ):
    current = p[ start ] - 1
    l = loop_length[ loop[ start ] ]
    score = loop_score[ loop[ start ] ]
    if l >= k:
        current = start
        max_score = 0
        cur_score = 0
        for i in range( k ):
            current = p[ current ] - 1
            cur_score += c[ current ]
            if max_score < cur_score or i == 0:
                max_score = cur_score
        return max_score
    else:
        if score > 0:
            score = score * ( k // l )
            current = start
            max_score = 0
            cur_score = 0
            for _ in range( k % l ):
                current = p[ current ] - 1
                cur_score += c[ current ]
                if max_score < cur_score:
                    max_score = cur_score
            return max_score + score
        else:
            score = 0
            current = start
            max_score = 0
            cur_score = 0
            for i in range( k % l ):
                current = p[ current ] - 1
                cur_score += c[ current ]
                if max_score < cur_score or i == 0:
                    max_score = cur_score
            return max_score

best_score = - ( 10 ** 10 )
for i in range( n ):
    now_score = solve( i )
    if best_score < now_score:
        best_score = now_score
print( best_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()))


Cum = [0]*(N+2)
temp = 1
SUM = 0
for i in range(N+1):
    temp = P[temp-1]
    SUM += C[temp-1]
    Cum[i+1] += SUM
    
 
    

group = []
group_C = []
group_Cum = []

check = [1]*N

while sum(check)!=0:
    temp = []
    start_num = check.index(1)+1
    temp_p = P[start_num-1]
    check[temp_p-1] -= 1
    temp.append(temp_p)
    
    temp_c = C[temp_p-1]
    
    temp_Cum = [0]
    temp_Cum.append(temp_c)
    
    for i in range(N):
    
        temp_p = P[temp_p-1]
        check[temp_p-1] -= 1
        temp.append(temp_p)
        temp_c += C[temp_p-1]
        temp_Cum.append(temp_c)
                
        if temp_p == start_num:
            break
    
    for i in range(len(temp)):
        temp_Cum.append(temp_c+temp_Cum[1+i])
    
    
    group.append(temp)
    group_C.append(max(0,temp_c))
    group_Cum.append(temp_Cum)
    
ans = -10**12

for i in range(len(group_C)):
    X = len(group[i])
    Y = K//X
    Z = K%X
       
    group_max = -10**12
    for k in range(1,Z+1):

        for j in range(X):
            group_max = max(group_max,group_Cum[i][k+j]-group_Cum[i][j])
            
        
        ans = max(ans,group_max+Y*group_C[i])
        
    if group_C == 0:
        Z += X
        
        for k in range(1,Z+1):

            for j in range(X):
                group_max = max(group_max,group_Cum[i][k+j]-group_Cum[i][j])
                

            ans = max(ans,group_max+Y*group_C[i])
    
print(ans)

Submission status: Wrong Answer

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

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

for i in range(N):
    visit = [False]*N
    now = i
    l = []
    visit[now] = True
    
    for j in range(N+10):
        nex = P[now]
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    su = sum(l)
    
    if su>=0:
        if K>=len(l):
            now = su*(K//len(l))
            rem = K%len(l)
            ans = max(ans, now)
        
            for j in range(rem):
                now += l[j]
                ans = max(ans, now)
        else:
            now = l[0]
            ans = max(ans, now)
            
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
    else:
        now = l[0]
        ans = max(ans, now)
        
        if K<len(l):
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
        else:
            for j in range(1, len(l)):
                now += l[j];
                ans = max(ans, now)

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

frag, loop, lcnt = set(), [], []
for i in range(n):
    if i in frag:
        continue
    now, tmp, tmpc = i, [], 0
    while True:
        frag.add(now), tmp.append(now)
        now = p[now] - 1
        tmpc += c[now]
        if now in frag:
            loop.append(tmp * 2)
            lcnt.append(tmpc)
            break

lacc = []
for l in loop:
    tmp = [0]
    for li in l[1:]: 
        tmp.append(tmp[-1] + c[li])
    lacc.append(tmp)

ans = min(c)
for l, la, lc in zip(loop, lacc, lcnt):
    num = k % len(l) // 2
    for cnt in range(1, min(len(l) // 2 + 1, k + 1)):
            for i in range(len(l) - cnt - 1):
                tmp = la[i + cnt] - la[i]
                ans = max(ans, tmp + lc * (len(l) // 2 // k - (cnt >= num)))
print(ans)