Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Accepted

Solution code:
# -*- 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]

    done = set()
    cycles = []
    for i in range(N):
        c = i
        t = []
        while c not in done:
            n = P[c]
            done.add(c)
            t.append(c)
            c = n
        if t:
            cycles.append(t)

    ans = -INF
    for c in cycles:
        cs = sum(C[v] for v in c)
        if cs > 0:
            m = max(0, (K // len(c)) - 1)
            k = K - len(c) * m
            a = cs * m
            ans = max(ans, a)
        else:
            k = min(len(c), K)
            a = 0

        b = a
        for u in c:
            a = b
            for _ in range(k):
                v = P[u]
                a += C[v]
                ans = max(ans, a)
                u = v

    return ans


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: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

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

for i in range(N):
    if C[i] >= 0:
        break
else:
    print(max(C))
    exit()

from itertools import accumulate


def f(A):  # Aを無限個つなげたリストの、連続K個以下の連続部分列の和の最大値
    a = len(A)
    res = 0
    if sum(A) > 0:
        if K // a > 0:
            res = sum(A) * (K // a - 1)
            r = K % a + a
        else:
            r = K % a
    else:
        r = K % a + a

    A = [0] + A + A + A
    S = list(accumulate(A))
    m = 0
    for i in range(a):
        for k in range(1, r + 1):
            b = S[i + k] - S[i]
            m = max(m, b)
    res += m
    return res


flag = [0]*N
ans = 0
for i in range(N-1):
    if flag[i] != 0:
        continue
    A = [C[i]]
    flag[i] = 1
    j = P[i]-1
    while j != i:
        A.append(C[j])
        flag[j] = 1
        j = P[j]-1
    ans = max(ans,f(A))

print(ans)

Submission status: Accepted

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

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

for start in range(N):
    for goal in range(min(K,len(DP[start]))):
        no_loop_sum=DP[start][goal]
        remain_hops=K-goal-1
        if DP[start][-1]>0:
            loops=remain_hops//len(DP[start])
        else:
            loops=0
        ans=max(ans,no_loop_sum+DP[start][-1]*loops)
print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())
#    n = 5000
#    k = 1
    p = [int(i)-1 for i in ipt().split()]
#    p = [(i-1)%n for i in range(n)]
#    c = [10**9 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    ma = -10**18
    al = [False]*n
    for i in range(n):
        if al[i]:
            continue
        pts = []
        nap = i
        for j in range(n):
            nap = p[nap]
            pts.append(c[nap])
            al[nap] = True
            if nap == i:
                break
        ln = len(pts)
        jt = k%ln+ln
        sma = 0
        for jp in pts:
            sma += jp
        if sma > 0:
            nm = (k//ln-1)*sma
        else:
            nm = 0
        pts *= 2
        ma1 = -10**18
#        print(pts,al)
        for ji in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[ji-jj]
#                print(i,j,j-jj,sm)
                if ma1 < sm:
                    ma1 = sm
        ma1 += nm
        if ma < ma1:
            ma = ma1
#        print(ma)

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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):
    llen = len(l) // 2
    num = k % llen
    for cnt in range(1, min(llen + 1, k + 1)):
        for i in range(len(l) - cnt - 1):
            tmp = la[i + cnt] - la[i]
            tmp2 = tmp + lc * (k // llen - (cnt > num))
            ans = max(ans, tmp, tmp2)
print(ans)

Submission status: Accepted

Solution code:
import sys


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


def calc(arr, k):
    s = sum(arr)
    n = len(arr)
    kp = k % n if s > 0 else k
    if kp == 0:
        kp = n

    ll = min(kp, n)
    cm = max(arr)
    for i in range(n):
        cn = 0
        for ki in range(i, i+ll):
            cn += arr[ki % n]
            cm = max(cn, cm)

    if s > 0:
        return s * ((k-1)//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: Accepted

Solution code:
n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = float('-inf')

ans = minc


def get_loop(i):
    pos = i
    cnt = 0
    cur_score = 0
    while cnt == 0 or pos != i:
        pos = p[pos]
        cur_score = cur_score + c[pos]
        cnt += 1
    return cnt, cur_score

# print(get_loop(2))

def solve(pos, k):
    score = minc
    cur_score = 0
    loop_length, loop_score = get_loop(pos)
    if k >= 2 * loop_length and loop_score > 0:
        # print("%s: %s // %s, %s, %s" % (i, k, loop_length, cur_score, max_loop_score))
        cur_score = loop_score * ((k - loop_length) // loop_length)
        score = max(cur_score, score)
        k = k % loop_length + loop_length
    else:
        k = min(k, 2 * loop_length)
    for _ in range(k):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    # print("%s: %s" % (i, score))
    return score

for i in range(n):
    ans = max(ans, solve(i, k))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
P = tuple(map(lambda x: int(x)-1, input().split()))
C = tuple(map(int, input().split()))
CC = [[] for _ in range(n)]
for idx, p in enumerate(P):
    CC[idx].append(C[p])
    pp = P[p]
    for _ in range(n):
        CC[idx].append(C[pp])
        pp = P[pp]
        if pp == p:
            break
        
from itertools import accumulate
ans = -2*(10**9)
for cc in CC:
    cca = list(accumulate(cc))
    if cca[-1] <= 0:
        # 1周分のうちの最大値
        if k < len(cc):
            ans = max(ans, max(cca[:k]))
        else:
            ans = max(ans, max(cca))
    else:
        # kk周したほうが良い
        kk, r = divmod(k, len(cc))
        if r == 0:
            ans = max(ans, kk*cca[-1], (kk-1)*cca[-1]+max(cca))
        else:
            ans = max(ans, kk*cca[-1] + max(cca[:r]))
print(ans)

Submission status: Accepted

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-1)*S
        mod = k%le
        now = 0
        for i in range(le):
            cal = 0
            for j in range(le):
                if j <= mod:
                    now = max(now,cal+S)
                cal += l[(i+j)%le]
                now = max(now,cal)
        return score+now
    else:
        mod = min(le,k)
        now = -float("INF")
        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: Accepted

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-1)*S
        mod = k%le+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 = -float("INF")
        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: Accepted

Solution code:
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
g = []
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g.append(y)
  else:
    g.append(max(e))
print(max(g))

Submission status: Accepted

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

data = [[0 for i in range(n+1)] for j in range(n)]
loop = [10**10 for i in range(n)]
for i in range(n):
    j = i
    for t in range(1,n+1):
        j = p[j]
        data[i][t] += data[i][t-1] + c[j]
        if j == i:
            loop[i] = min(loop[i],t)

ans = -10**10
#print(data)
#print([data[i][loop[i]] for i in range(n)])

for i in range(n):
    for j in range(1,min(n,k)+1):
        if j > loop[i]:break
        if data[i][loop[i]] <= 0:
            ans = max(ans,data[i][j])
        else:
            ans = max(ans,data[i][loop[i]]*((k-j)//loop[i])+data[i][j])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]

ans = -float('inf')
for i in range(n):
    now = i
    c_sum = [0]
    s = set()
    cnt = 0
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        cnt += 1
        now = p[now]
        if now in s:
            break
    c_sum = c_sum[1:]
    if k < cnt:
        ans = max(ans, max(c_sum[: k]))
    else:
        score = c_sum[-1]
        count = k // cnt
        k_ = k - count*cnt
        score *= count
        score_2 = score - c_sum[-1]
        score_2 += max(c_sum)
        if k_ > 0:
            score += max(0, max(c_sum[:k_]))
        ans = max(ans, score, max(c_sum), score_2)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**18
m = 10**9 + 7

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

    ans = - INF
    used = [0] * N
    candidate = []

    for i in range(N):
        if used[i]: continue
        now = i
        used[i] = 1
        tmp = [i]
        
        while P[now]-1 not in tmp:
            used[P[now]-1] = 1
            tmp.append(P[now]-1)
            now = P[now]-1
        
        candidate.append(tmp)

    # 各ループごとにK回以内で回して最大値を調べていく
    for tmp in candidate:
        M = len(tmp)
        accumT = []
        for t in tmp:
            accumT.append(C[t])
        loop = 3
        accumT = [0] + list(accumulate(accumT*loop))
        res = - INF

        if K <= M:# ループにならない
            for i in range(loop*M+1):
                for j in range(i+1,loop*M+1):
                    if j - i > K: 
                        break
                    res = max(res,accumT[j]-accumT[i])
            ans = max(ans,res)
        else:
            SUM = accumT[M]
            if SUM > 0:
                addition = SUM * (K//M - 1)# K//M回回らない方がいい場合がある
                for i in range(loop*M+1):
                    for j in range(i+1,loop*M+1):
                        if j - i > K%M+M:
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res+addition)
            else:
                for i in range(loop*M+1):
                    for j in range(i+1,loop*M+1):
                        if j - i > M:
                            break
                        res = max(res,accumT[j]-accumT[i])
                ans = max(ans,res)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k = tin()
	#s = input()
	al = lin()
	cl=lin()
	dd=[0]*n
	for i in range(n):
		if dd[i]!=0:
			continue
		cc=set()
		pos = i
		point=0
		n_node=0
		while pos not in cc:
			cc.add(pos)
			pos=al[pos]-1
			point+=cl[pos]
			n_node+=1
			
		for p in cc:
			dd[p] = (point, n_node)
	
	ret=-mod*mod
	for i in range(n):
		pi, ni = dd[i]
		if pi < 0:
			point=0
			pmax=-mod*mod
			pos=i
			for _ in range(ni):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(pmax, point)
			ret = max(ret, pmax)
		elif k < ni*2:
			point=0
			pmax=-mod*mod
			pos=i
			for _ in range(k):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(pmax, point)
			ret = max(ret, pmax)
		else:
			point = pi*((k//ni)-1)
			nk=k%(ni) + ni
			pos = i
			pmax = point
			for _ in range(nk):
				cc.add(pos)
				pos=al[pos]-1
				point+=cl[pos]
				pmax = max(point, pmax)
			ret = max(ret, pmax)
	return ret
		
		
			
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
p = LI()
c = LI()
C = []
S = []
for i in range(n):
    lst = [-1]*n
    cnt = 0
    idx = i
    s = 0
    while lst[idx] == -1:
        lst[idx] = cnt
        s += c[idx]
        cnt += 1
        idx = p[idx] - 1
    C.append(cnt)
    S.append(s)

if n >= k:
    ans = -10**10
    for i in range(n):
        cnt = 0
        ret = 0
        idx = p[i]
        while cnt < k:
            ret += c[idx-1]
            idx = p[idx-1]
            cnt += 1
            ans = max(ans, ret)
    print(ans)
else:
    ans = -10**10
    for i in range(n):
        if S[i] > 0:
            tmp = S[i] * (k // C[i])
            r = k % C[i]
            cnt = 0
            ret = 0
            idx = p[i]
            if r == 0:
                tmp -= S[i]
                r = C[i]
            while cnt < r:
                ret += c[idx-1]
                idx = p[idx-1]
                cnt += 1
                ans = max(ans, tmp + ret)
        else:
            cnt = 0
            ret = 0
            idx = p[i]
            while cnt < n:
                ret += c[idx-1]
                idx = p[idx-1]
                cnt += 1
                ans = max(ans, ret)
    print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())
#    n = 5000
#    k = 1
    p = [int(i)-1 for i in ipt().split()]
#    p = [(i-1)%n for i in range(n)]
#    c = [10**9 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    ma = -10**18
    al = [False]*n
    for i in range(n):
        if al[i]:
            continue
        pts = []
        nap = i
        for j in range(n):
            nap = p[nap]
            pts.append(c[nap])
            al[nap] = True
            if nap == i:
                break
        ln = len(pts)
        jt = (k-1)%ln
        jt += 1+ln
        sma = 0
        for jp in pts:
            sma += jp
        if sma > 0:
            nm = ((k-1)//ln-1)*sma
        else:
            nm = 0
        pts *= 2
        ma1 = -10**18
#        print(pts,al)
        for ji in range(ln):
            sm = 0
            for jj in range(jt):
                sm += pts[ji-jj]
#                print(i,j,j-jj,sm)
                if ma1 < sm:
                    ma1 = sm
        ma1 += nm
        if ma < ma1:
            ma = ma1
#        print(ma)

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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+1]), cumsum[loop_size] + max(cumsum[0:K_%loop_size+1]))
            ans = max(ans, tmp)
        else:
            ans = max(ans, max(cumsum[1:j+1]))
print(ans)

Submission status: Accepted

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

visited = [False for _ in range(n)]
lp = []
lp_cum = []

ans = -10**9
for i in range(n):
	if not visited[i]:
		lp.append([i])
		lp_cum.append([0, c[i]])
		visited[i] = True
		while not visited[p[lp[-1][-1]]]:
			lp[-1].append(p[lp[-1][-1]])
			lp_cum[-1].append(lp_cum[-1][-1] + c[lp[-1][-1]])
			visited[lp[-1][-1]] = True
		t_sum, t_num = lp_cum[-1][-1], len(lp[-1])
		for x in range(1, len(lp_cum[-1])):
			for y in range(x):
				r_sum, r_num = lp_cum[-1][x] - lp_cum[-1][y], x-y
				if t_sum <= 0:
					if r_num <= k:
						ans = max(ans, r_sum)
				else:
					if r_num <= k:
						ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))
				if x < len(lp_cum[-1])-1 or y > 0:
					r_sum, r_num = lp_cum[-1][-1] - lp_cum[-1][x] + lp_cum[-1][y], len(lp[-1])-x+y
					if t_sum <= 0:
						if r_num <= k:
							ans = max(ans, r_sum)
					else:
						if r_num <= k:
							ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
r = -10**9
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g=y
  else:
    g=max(e)
  r = max(r,g)
print(r)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    p = list(map(lambda x:int(x) - 1, input().split()))
    c = list(map(int, input().split()))
    seen = [0] * n
    accumulate = []
    for i in range(n):
        if seen[i] == 0:
            accumulate.append([c[i]])
            pre = i
            while True:
                if seen[pre] == 1:
                    accumulate[-1].pop()
                    break
                seen[pre] = 1
                now = p[pre]
                pre = now
                accumulate[-1].append(accumulate[-1][-1] + c[now])
    
    ans = -float("INF")
    for lst in accumulate:
        if len(lst) >= k:
            for interval in range(1, k + 1):
                for start in range(len(lst)):
                    if start + interval >= len(lst):
                        num = lst[-1] + lst[(start + interval) % len(lst)] - lst[start]                    
                    else:
                        num = lst[(start + interval)] - lst[start]
                    ans = max(ans, num)
        else:
            if lst[-1] > 0:
                for interval in range(1, len(lst) + 1):
                    for start in range(len(lst)):
                        num = (k - interval) // len(lst) * lst[-1]
                        if start + interval >= len(lst):
                            num += (lst[-1] + lst[(start + interval) % len(lst)] - lst[start])                    
                        else:
                            num += (lst[(start + interval)] - lst[start])
                        ans = max(ans, num)
                """
                for interval in range(1, k - len(lst) * (k // len(lst)) + 1):
                    for start in range(len(lst)):
                        num = (k // len(lst)) * lst[-1]
                        if start + interval >= len(lst):
                            num += (lst[-1] + lst[(start + interval) % len(lst)] - lst[start])
                        else:
                            num += lst[(start + interval)] - lst[start]
                        ans = max(ans, num)
                """
            else:
                for interval in range(1, len(lst)):
                    for start in range(len(lst)):
                        if start + interval >= len(lst):
                            num = lst[-1] + lst[(start + interval) % len(lst)] - lst[start]                    
                        else:
                            num = lst[(start + interval)] - lst[start]
                        ans = max(ans, num)
            
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loopid = [-1 for _ in range(N)]
loop_found = 0
for i in range(N):
    if loopid[i] != -1:
        continue
    loopid[i] = loop_found
    j = P[i]-1
    while loopid[j] == -1:
        loopid[j] = loop_found
        j = P[j]-1
    loop_found += 1

loops = [[] for _ in range(loop_found)]
for nodeid, id in enumerate(loopid):
    loops[id].append(nodeid)

ans = -math.inf
for loop in loops:
    K_tmp = K
    score_tmp = 0
    cs = []
    j = loop[0]
    for _ in range(len(loop)):
        cs.append(C[j])
        j = P[j] - 1
    if sum(cs) >= 0:
        score_tmp += sum(cs)*max(0, K//len(loop)-1)
    K_tmp %= len(loop)
    if K>=len(loop):
        K_tmp += len(loop)

    max_rest = -math.inf
    cs = cs + cs + cs
    for i in range(1, len(cs)):
        cs[i] += cs[i-1]
    j = -1
    tmp_min = math.inf
    for i, c in enumerate(cs):
        max_rest = max(max_rest, c-tmp_min)
        if tmp_min >= c:
            tmp_min = c
            j = i
        if i-j >= K_tmp:
            tmp_min = cs[j+1]
            j += 1
            x = j
            for k, c_ in enumerate(cs[j+1:i+1]):
                if tmp_min >= c_:
                    tmp_min = c_
                    x = k + j + 1
            j = x
    score_tmp += max_rest
    ans = max(ans, score_tmp)
print(ans)

Submission status: Accepted

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


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

ans=-1*(10**10)

if K<10000000:
    for i in range(N):
        tmp=0
        pos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            pos=P[pos]-1
            count+=1
     
    print(ans)
else:
    
    for i in range(N):
        tmp=0
        pos=i
        gpos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            
            pos=P[pos]-1
            count+=1
            if pos==gpos:
                divide=K//count-1
                tmp=tmp*divide
                count=count*divide
                gpos=10**10
            
    
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
scores = []
for i in range(N):
  pos = P[i]-1
  s = [C[i]]
  j = 1
  while j < K and pos != i:
    s.append(s[-1]+C[pos])
    pos = P[pos]-1
    j += 1
  smax = max(s)
  length = len(s)
  if length < K and s[-1] > 0:
    if K%length != 0:
      smod = s[:K%length]
      smodmax = max(smod)
    else:
      smodmax = 0
    scores.append(max(s[-1] * ((K//length)-1) + smax, s[-1] * (K//length), s[-1] * (K//length) + smodmax))
  else:
    scores.append(smax)
print(max(scores))