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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
p = LIST()
c = LIST()

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

ans = -inf
for i in range(n):
    visit = [inf]*n
    reg_score = [-inf]*n

    now = i
    count = 0
    score = 0
    while visit[now] == inf:
        visit[now] = count
        reg_score[now] = score
        count += 1
        now = p[now]
        score += c[now]

    x = visit[now]
    y = count - visit[now]
    X = reg_score[now]
    Y = score - reg_score[now]

    for j in range(n):
        if visit[j] == inf:
            continue
        if j != i:
            tmp0 = reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)
        elif (k-x)//y>0:
            tmp0 = Y + reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)

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


for i in range(n):

  sc=0
  pn=i
  mass=[0]*n
  for j in range(k):
    if mass[pn]!=0:
      lpk=j-mass[pn][0]
      amari=(k-j)%lpk
      lpsc=sc-mass[pn][1]
      if lpsc<=0:
        mx=max(mx,sc)
        break
      for l in range(amari):
        pn=p[pn]-1
        sc+=c[pn]
      sc+=lpsc*((k-j-amari)//lpk)
      mx=max(mx,sc)
      break
    mass[pn]=[j,sc]
    pn=p[pn]-1
    sc+=c[pn]
    mx=max(mx,sc)
print(mx)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10**9-1
for i in range(N):
    cumsum = [0]*(N+1)
    seen = [-1]*N
    K_ = K
    now = i
    j = 0
    while K_ > 0 and seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        K_ -= 1
        j += 1
    if K_ == 0:
        ans = max(ans, max(cumsum[1:j+1]))
    else:
        if cumsum[j] > 0:
            loop_size = j
            loop_n = K//loop_size - 1
            tmp = loop_n*cumsum[loop_size]
            tmp += max(max(cumsum[1:loop_size]), cumsum[loop_size] + max(cumsum[0:K_+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
[N,K]=list(map(int, input().split()))
plist=list(map(int, input().split()))
clist=list(map(int, input().split()))
ls=[0]*N
for a in range(N):
    k=0
    i=a
    maxs=0
    score=0
    while k<=K:
        i=plist[i]-1
        score+=clist[i]
        k+=1
        if k!=1:
            if score>maxs:
                maxs=score
        else:
            maxs=score
    ls[a]=maxs
print(max(ls))

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 = 0
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:
            m = max(m,totS*(k//l)+max(arr[:k%l]+[0]))
        else:

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline

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

kouho = []

used = [False] * (n)
for i in range(n):
    if used[i]:
        continue
    now = i
    cnt = 0
    res = 0
    route = []
    while True:
        if used[now]:
            break
        route.append(C[P[now] - 1])
        used[now] = True
        nex = P[now] - 1
        cnt += 1
        res += C[nex]
        now = nex
    kouho.append((res, cnt, route))

ans = -(10 ** 20)
for res, cnt, route in kouho:
    temp1 = 0
    num = len(route)
    kaisu = 0
    if k >= cnt:
        if res > 0:
            temp1 += res * (k // cnt)
            kaisu = k % cnt
        else:
            kaisu = num
    else:
        kaisu = k
    temp2 = -(10 ** 20)
    route += route
    ACR = list(accumulate([0] + route))
    for i in range(num):
        for j in range(1, kaisu + 1):
            temp3 = ACR[j + i] - ACR[i]
            temp2 = max(temp2, temp3)
            # print((i, j), temp3)
    # print(temp1)
    ans = max(ans, temp1 + temp2)
    if res > 0 and k >= cnt:
        kaisu = num
        for i in range(num):
            for j in range(1, kaisu + 1):
                temp3 = ACR[j + i] - ACR[i]
                temp2 = max(temp2, temp3)
                # print((i, j), temp3)
        ans = max(ans, temp1 + temp2)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

P = [p-1 for p in P]

check = [False] * n
loops = []

for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)


ans = 0

for loop in loops:

    num = len(loop)
    sho = k // num
    r = k % num
    L = [C[p] for p in loop]

    ans_tmp = 0

    ryaku = 0
    if sum(L) > 0:
        ryaku = sum(L) * sho
    if ryaku == 0 and r==0:
        r = num

    L += L[:r]
    ACC = [0] + list(accumulate(L))
    # print(ACC, r)

    if ryaku == 0 and r==0:
        r = num

    for i in range(num):
            for j in range(i+1, i+r+1):
                # print(i, j)
                # print(ACC[j]-ACC[i]+ ryaku)
                ans_tmp = max(ans_tmp, ACC[j]-ACC[i]+ ryaku)

    ans = max(ans, ans_tmp)

if ans == 0:
    print(max(C))
    exit()
print(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()))
L=[]
mx=-10**9
for i in range(n):
    prmx=-10**9
    t=p[i]
    l=[]
    sm=c[t]
    l.append(c[t])
    while t!=i:
        t=p[t]
        l.append(c[t])
        sm+=c[t]
    e=k%len(l)
    f=k//len(l)
    for i in range(len(l)-1):
        for j in range(i,min(len(l),i+k+1)):
            ms=sum(l[i:j+1])
            prmx=max(prmx,ms)
    if sm>0:
        prmx += sm*f
    mx=max(mx,prmx)
print(mx)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
c = [1] * N
s = [C[P[i]-1] for i in range(N)]
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        s[i] += C[P[j]-1]
        if  c[i] <= K:
            if s[i] > m[i][c[i]-1]:
                m[i][c[i]] = s[i]
            else:
                m[i][c[i]] = m[i][c[i]-1]
ans = min(C)
for i in range(N):
    if s[i] > 0:
        if  s[i] * (K//c[i]) + m[i][K%c[i]] > ans:
            ans = s[i] * (K//c[i]) + m[i][K%c[i]]
    else:
        if max(m[i][1:min(c[i],K+1)]) > ans:
            ans = max(m[i][1:min(c[i],K+1)])
print(ans)

Submission status: Wrong Answer

Solution code:
def roop(i,K):
    isroop=False
    last=[-1]*N
    lastcnt=[-1]*N
    n=i
    last[n]=0
    lastcnt[n]=0
    roopp=-1#ループ1回のポイント
    cnt=0
    rs=-1#ループ開始
    maxp=-10**30
    point=0
    while(True):
        cnt+=1
        n=P[n]
        point+=C[n]
        maxp=max(maxp,point)
        if last[n]!=-1:
            roopp=point-last[n]
            syuki=cnt-last[n]#ループ周期
            isroop=True
            rs=n
            start=last[n]
            break
        last[n]=point
        lastcnt[n]=cnt
        if cnt==K:
            break
    if not isroop:
        return  maxp
    if roopp<0:
        return maxp
    K-=lastcnt[rs]
    roopcnt=K//syuki
    allpoint=(K//syuki)*roopp
    K%=syuki
    j=0
    n=rs
    point=0
    maxpp=0
    while(j<K):
        j+=1
        n=P[n]
        point+=C[n]
        maxpp=max(maxpp,point)
    stopp=0#どこで止めるのが最大か
    n,j=rs,0
    while(j<syuki):
        j+=1
        n=P[n]
        point+=C[n]
        stopp=max(stopp,point)
    
    if rs!=i:
        return max([start,start+allpoint,start+allpoint+maxpp,start+allpoint-roopp+stopp])
    else:
        if roopcnt>1:
            return max([allpoint,allpoint+maxpp,maxp,allpoint-roopp+stopp])
        else:
            return max([allpoint,allpoint+maxpp,maxp])
        
        
        

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

ans=-10**30
for i in range(N):
    r=roop(i,K)
    ans=max(ans,r)
print(ans)

Submission status: Wrong Answer

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

curr_sum = []
for f_idx in range(n):
    curr_max = [c[f_idx]]
    for _ in range(k - 1):
        idx = p[f_idx]
        curr_max.append(curr_max[-1] + c[idx])
    curr_sum.append(max(curr_max))

print(max(curr_sum))

Submission status: Wrong Answer

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

ans = -10**9
v = [False for _ in range(n)]
for i in range(n):
  j = i
  if v[j]:
    continue
  r = []
  while(v[j] == False):
    r.append(j)
    v[j] = True
    j = p[j]
  s = 0
  rr = []
  f1 = True
  f2 = True
  for ri in r:
    s += c[ri]
    rr.append(c[ri])
    if c[ri] > 0:
      f1 = False
    if c[ri] < 0:
      f2 = False
  k1 = k%len(r)
  k2 = k//len(r)
  rr = rr+rr
  now = 0
  for i in range(len(rr)-k1+1):
    now = max(sum(rr[i:i+k1]),now)
  if s > 0:
    now += s*k2
  ans = max(ans,now)
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 j != 1:
            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[:k]), 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()))
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-=1
    y-=1
    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())
  
uni=UnionFind(N)
for i,p in enumerate(P):
  uni.union(i+1,p)
ans=0
for n in uni.roots():
  n+=1
  i=n
  X=[n]
  cost=[C[n-1]]
  while P[i-1]!=n:
    X.append(P[i-1])
    cost.append(C[P[i-1]-1])
    i=P[i-1]
  l=len(X)
  if sum(cost)>0:
    if K%l==0:
      ans=max(ans,sum(cost)*(K//l))
    else:
      k=K%l
      ans=max(sum(cost)*(K//l)+max([sum(cost[i:i+k]) for i in range(l-k+1)]),ans)
  else:
    if K//l==0:
      k=K
    else:
      k=l
    cost=cost+cost
    for i in range(1,k+1):
      ans=max(ans,max([sum(cost[j:j+i]) for j in range(2*l-i)]))
if ans==0 and 0 not in C:
  ans=max(C)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))

# 重み付き有効グラフ
edges = [[] for _ in range(N)]
for i in range(N):
    edges[i].append((P[i]-1, C[i]))

# DFSで閉路と経路の最大取得スコアを調査
max_path_score = -float("inf")
cycle = set() # (score, count, start_node)
for i in range(N):
    visited = set()
    q = deque([(i, 0, 0)])
    while q:
        node1, score, count = q.popleft()
        if K < count:
            break
        if 0 < count: 
            max_path_score = max(max_path_score, score)
        if node1 in visited:
            # 閉路
            if score > 0:
                cycle.add((score, count, i))
            break
        visited.add(node1)
        for node2, weight in edges[node1]:
            q.appendleft((node2, score + weight, count + 1))
# print("max_path", max_path_score)

if len(cycle) == 0:
    print(max_path_score)
else:
    ans = max_path_score

    # サイクル内のノードは一回だけ計算する
    calculated = set()
    # サイクルごとの最大スコアを算出
    for (score, length, start) in cycle:
        path_list = []
        q = deque([start])
        visited = set()
        while q:
            node = q.popleft()
            path_list.append((node, C[node]))
            if node in visited:
                break
            visited.add(node)
            for node2, weight in edges[node]:
                q.append(node2)

        # サイクルのパス内で得られる最大スコア
        acum = [0 for _ in range(len(path_list) + 1)] # 累積和
        for i, (node, weight) in enumerate(path_list):
            calculated.add(node)
            acum[i+1] = acum[i] + weight
        path_max = -float("inf")
        res_path_max = - float("inf") # サイクルのあまりで到達できる最大スコア
        res_len = K % length
        for i in range(len(path_list)):
            for j in range(i, len(path_list) + 1):
                tmp_score = acum[j] - acum[i]
                path_max = max(path_max, tmp_score)
                if j - i <= res_len:
                    res_path_max = max(res_path_max, tmp_score)
                    
        
        # あまりを使う場合
        ans = max(ans, score * (K // length) + res_path_max)    
        # サイクル内の最大パスを使う場合
        ans = max(ans, score * (K // length - 1) + path_max)

    print(ans)

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(n+1,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())
ListJ = list(map(int, input().split()))
ListP = list(map(int, input().split()))
INF = -10000000000
List = [INF]*N
flag = True
point = 0
pointMax = -10000000000
mid = 0
ListG=[0]*N
periodG = []
for i in range(N):
  flag = True
  point = 0
  mid = 0
  k = i
  while flag:
    if List[k] != INF:
      periodG.append(mid)
      flag = False
    else:
      mid +=  ListP[k]
      List[k] = mid
      ListG[k]=i
      k = ListJ[k]-1
  mid = periodG[ListG[i]]
  if mid >0:
    n = List.count(INF)
    n = N-n
    period = N//n
    point = period*mid
    for i in range(K-period*n):
      mid +=  ListP[k]
      k = ListJ[k]-1
      point = max(point,mid)
    pointMax = max(point,pointMax)
  else:
    num_list = list(map(int, List))
    point = max(num_list)
    pointMax = max(pointMax,point)
print(pointMax)

Submission status: Wrong Answer

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

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 main():
	log = Logger(0)
	n, k = map(int, sys.stdin.readline().split())
	p = list(map(int, sys.stdin.readline().split()))
	c = list(map(int, sys.stdin.readline().split()))
	uf = UnionFind(n)
	max_score = -float("inf")
	for i in range(n):
		uf.union(p[i] - 1, i)
	log.print(uf.all_group_members())
	for i in range(n):
		cnt = k
		score = 0
		loop = uf.members(p[i]-1)
		log.print(loop)
		if k > len(loop):
			here = i
			loopsum = 0
			for j in range(len(loop)):
				here = p[here] - 1
				loopsum += c[here]
			assert i == here
			if loopsum > 0:
				score += loopsum * (k // len(loop))
				cnt %= len(loop)
		tmp_max_score = -float("inf")
		here = i
		for j in range(len(loop) - 1):
			if j >= cnt:
				break
			here = p[here] - 1
			score += c[here]
			log.print(here, score)
			tmp_max_score = max(tmp_max_score, score)
		log.print(tmp_max_score)
		max_score = max(tmp_max_score, max_score)
	print(max_score)




	


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

ans = - 10 ** 10
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt > k:
        continue
    if k - cnt <= cnt:
        score_tmp = score
        for j in range(1, k - cnt + 1):
            score_tmp += c[nxt]
            ans = max(ans, score_tmp)
            #print("ans = ", ans, "score_tmp = ", score_tmp, "nxt = ", nxt, "c[nxt] = ", c[nxt])
            nxt = p[nxt]
    else:
        a = (k - cnt) // cnt
        score_tmp = score + score * a
        ans = max(ans, score_tmp)
        for j in range(1, (k - cnt) - a * cnt + 1):
            score_tmp += c[nxt]
            ans = max(ans, score_tmp)
            nxt = p[nxt]


#print("score:", score)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
used = [0]*n
c = list(map(int,input().split()))
ans = -float("INF")
def calc(x):
    l = []
    now = x
    score = 0
    while used[now] == 0:
        used[now] = 1
        l.append(c[now])
        now = p[now]-1
    S = sum(l)
    le = len(l)
    if S > 0 and k > le:
        score += (k//le)*S
        mod = k%le
        now = 0
        for i in range(le):
            cal = 0
            for j in range(mod):
        
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    else:
        mod = min(le,k)
        now = 0
        for i in range(le):
            cal = 0
            for j in range(mod):
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    
for i in range(n):
    if used[i] == 0:
        ans = max(ans,calc(i))
print(ans)

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
from sys import stdin
def main():
    readline = stdin.readline
    n,k = map(int,readline().split())
    P = list(map(int,readline().split()))
    C = list(map(int,readline().split()))
    dic = defaultdict(int)
    for i in range(n):
        dic[i+1] = P[i]
    ans = -float('inf')
    for start in range(n):
        nya = deque()
        root = defaultdict(int)
        pya = start+1
        cnt = 0
        SUM = 0
        nl = 0
        while root[dic[pya]] == 0 and cnt < k:
            pya = dic[pya]
            nya.append(C[pya-1])
            nl += 1
            cnt += 1
            SUM += C[pya-1]
            root[pya] = 1
            ans = max(ans,SUM)
        if cnt < k:
            need = k-cnt
            sumnya = SUM
            a = need//nl
            SUM += sumnya * a
            ans = max(ans,SUM)
            nokori = need - nl*a
            for idx in range(nokori):
                SUM += nya[idx]
                ans = max(ans,SUM)
        else:
            ans = max(ans,SUM)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
r = []
visit = [0] * n
for i in range(n):
    if not visit[i]:
        x = []
        j = i
        while True:
            if visit[j]:
                break
            x.append(c[j])
            visit[j] = 1
            j = p[j] - 1
        r.append(x)
l = len(r)
ans = -1145141919810
for x in r:
    ll = len(x)
    y = [0] * (ll + 1)
    for i in range(ll):
        y[i + 1] = y[i] + x[i]
    sumx = y[ll]
    a = 0
    b = -1145141919810
    kk = k
    #print(kk, ll)
    if ll < kk:
        if sumx > 0:
            a = max(0, (kk // ll) * sumx)
        kk -= ll * (kk // ll)
    #print(a, kk, ll, sumx)
    #print(y)
    kk = max(kk, 1)
    for i in range(1, kk + 1):
        for j in range(ll + 1 - i):
            #print(i + j, j)
            b = max(y[i + j] - y[j], b)
    for i in range(kk - 1):
        for j in range(i + 1):
            #print(ll - 1 - (j - 1), 1 + (i - j))
            b = max(y[ll] - (y[ll - 2 - (j - 1)] - y[1 + (i - j)]), b)
    ans = max(a + b, ans)
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-(K//len(l))*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:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    P = [p-1 for p in read_ints()]
    C = read_ints()

    max_score = -math.inf
    for i in range(N):
        cycle_score = C[i]
        scores = [0, C[i]]
        j = P[i]
        k = K
        while k > 1 and i != j:
            cycle_score += C[j]
            scores.append(cycle_score)
            j = P[j]
            k -= 1
        cycle_size = len(scores)-1
        cycle_count = K//cycle_size
        max_score = max(max_score, max(scores[1:]))
        if cycle_count != 0:
            max_score = max(max_score, cycle_score*cycle_count+max(scores[1:K%cycle_size+1], default=0))
    return max_score


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = [int(x)-1 for x in input().split()]
c = list(map(int, input().split()))
realans = -1001001001
for i in range(n):
    count = 0
    now = i
    score = 0
    for _ in range(n):
        if now == i and count != 0:
            break
        now = p[now]
        count += 1
        score += c[now]
    ans = 0
    ans += score * (k // count)
    nk = k % count
    if ans < 0:
        if nk == 0:
            nk = k
        ans = 0

    maxim = -1001001001
    now = i
    tmp = 0
    for j in range(nk):
        now = p[now]
        tmp += c[now]
        maxim = max(maxim, tmp)
    ans += maxim
    realans = max(realans, ans)
print(realans)