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:
from copy import copy
n, k = map(int, input().split())
p = list(map(int,input().split()))
c = list(map(int, input().split()))
di = {}
for i in range(n):
    di[i+1] = False
l = 1
cc = 0
per = [] # ループの順番
while cc < n:
    tmp = []
    while True:
        if di[l]:
            break
        else:
            tmp.append(l)
            di[l] = True
            cc += 1
            l = p[l-1]
    per.append(tmp)
    for i in range(n):
        if not di[i+1]:
            l = p[i]
#print(per)
dd = {} # 何個目のループに属するか
for i in range(n):
    dd[i+1] = 0
for i in range(len(per)):
    for j in per[i]:
        dd[j] = i
#print(dd)
su = [] # ループ１週の和
for i in range(len(per)):
    tmp = 0
    for j in per[i]:
        tmp += c[j-1]
    su.append(tmp)
#print(su)
s2 = [] # ループ１週何個か
for i in range(len(per)):
    s2.append(len(per[i]))
#print(s2)
ans = -1*(10**10)
#d2 = {} # per[dd]の中でなんばんめにあるか(0インデックス)
#for i in range(len(per)):
#    for j in range(len(per[i])):
#        d2[per[i][j]] = j
#print(d2)
aa = []
for i in range(n):
    loop = dd[i+1]
    w = i+1
    kk = copy(k)
    if k < s2[loop]:
        tmp = 0
        m = -10**9
        for j in range(k):
            w = p[w-1]
            tmp += c[w-1]
            aa.append(tmp)
    else:
        if su[loop] <= 0:
            tmp = 0
            m = -10**9
            for j in range(n):
                w = p[w-1]
                tmp += c[w-1]
                aa.append(tmp)
        else:
            m_loop = kk // (s2[loop])
            m_loop -= 1
            kk -= m_loop * s2[loop]
            tmp = su[loop]*m_loop
            m = -10**9
            for j in range(kk):
                w = p[w-1]
                tmp += c[w-1]
                if c[w-1] <= 0:
                    continue
                aa.append(tmp)
print(max(aa))

Submission status: Accepted

Solution code:
INF = float('inf')

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


def simulate(start, k):
    result = -INF
    cur = start
    score = 0

    turn = 0
    cycle_check = False
    while turn < k:
        turn += 1
        cur = P[cur]
        score += C[cur]
        result = max(result, score)
        # サイクル時の処理短縮
        if cur == start and cycle_check == False:
            cycle_check = True
            # １周して減ってるなら回す必要なし
            if score <= 0:
                break
            # 1周して増えるなら最後の1周 + αだけ試す
            cycle_cnt = (k // turn) - 1
            if cycle_cnt < 1:
                cycle_cnt = 0
            # break
            turn = cycle_cnt * turn
            score = cycle_cnt * score

    return result


result = -INF
for i in range(n):
    # if i != 2:
    #     continue
    result = max(result, simulate(i, k))

print(result)

Submission status: Accepted

Solution code:
import sys
mINF = -float('inf')
n,k = map(int, sys.stdin.readline().rstrip("\n").split())
p = [int(s)-1 for s in sys.stdin.readline().rstrip("\n").split()]
c = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
loop = []
for i in range(n):
    loop_costs = []
    lc = 0
    np = i
    while True:
        lc += c[p[np]]
        loop_costs.append(lc)
        np = p[np]
        if np == i:
            break
    loop.append(loop_costs)
ans = mINF
for i in range(n):
    loop_i = loop[i]
    if len(loop_i) < k:
        if loop_i[-1] > 0:
            q, mod = divmod(k, len(loop_i))
            if mod == 0:
                q = q - 1
                modmax = max(loop_i)
            else:
                modmax = max(loop_i[:mod])
            ans = max(ans,loop_i[-1]*q+modmax)
        else:
            ans = max(ans,max(loop_i))
    else:
        ans = max(ans,max(loop_i[:k]))
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()))
# print(C)
ans = -float("inf")
hoge = K
for i in range(N):
    K = hoge
    start_point = i
    visited = set()
    ruisekiwa = [0]
    tmp = 0
    for j in range(min(K, N)):
        # とりあえず回数の許す限り次のマスへ行く
        # ループしているならブレイク, 目的値に到着したことがある
        if P[start_point] in visited:
            break
        visited.add(P[start_point])
        ruisekiwa.append(ruisekiwa[-1]+C[P[start_point]])
        start_point = P[start_point]
    if ruisekiwa[-1] < 0:
        ans = max(ans, max(ruisekiwa[1:]))
        continue
    # ループが可能な場合
    if K > len(visited):
        # 可能な限りループする（最後の1回はループしない）
        tmp += ruisekiwa[-1]*(K//len(visited)-1)
        K %= len(visited)  # 余ったループ回数
        # 左側はもう1ループして，余力のループを行った場合．
        # 右側は最後の1ループを理想的なところで止めた場合
        # print("K %= N のあとの : ", K)
        if K != 0:
            tmp += max(ruisekiwa[-1]+max(ruisekiwa[1:K+1]), max(ruisekiwa[1:]))
        else:
            tmp += max(ruisekiwa)
        ans = max(ans, tmp)
    else:
        ans = max(ans, max(ruisekiwa[1:]))
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()))
ans = -10**100
for i in range(n):
    start = i
    cur = i
    i_s_score = 0
    i_s_score_max = C[P[cur]-1]
    move_num = 0
    for j in range(n):
        cur = P[cur]-1
        i_s_score += C[cur]
        i_s_score_max = max(i_s_score, i_s_score_max)
        move_num += 1
        if cur == start:
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        temp = i_s_score*(k//move_num)
        if (k//move_num >= 1):
            temp_dash = i_s_score*(k//move_num-1)+i_s_score_max
            ans = max(ans, temp_dash)
        rest = k%move_num
        ans = max(ans, temp)
        i_s_score = temp
        for j in range(rest):
            cur = P[cur]-1
            i_s_score += C[cur]
            ans = max(ans, i_s_score)
print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import collections
def main():

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

    ans = float('-inf')
    if K <= N:
        for i in range(N):
            v = 0
            k = i
            for j in range(K):
                k = P[k]-1
                v += C[k]
                ans = max(ans, v)
        return ans

    for i in range(N):
        visited = dict()
        k = i
        visited[i] = 0
        val = [0]
        v = 0
        for j in range(1, N+1):
            k = P[k] - 1
            if k not in visited:
                visited[k] = j
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
            else:
                m = visited[k]
                t = j - m
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
                # print(val, j, visited[k])
                val1 = val[:m+1]
                val2 = val[m+1:]
                period = sum(val2)
                pre = sum(val1)
                n = (K - m) // t
                rem = (K-m) % t
                u = 0
                ans = max(ans, u + pre + period * n)
                for p in range(rem):
                    u += val2[p]
                    ans = max(ans, u + pre + period * n)
                u = 0
                for p in range(t):
                    u += val2[p]
                    ans = max(ans, u + pre + period * (n-1))
                break

    return ans


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

Submission status: Accepted

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

ans = -float("inf")
for i in range(1, N+1):
    S = i
    visited = [False for i in range(N+1)]
    point = []
    while visited[S] == False:
        point.append(C[S])
        visited[S] = True
        S = P[S]

    L = len(point)
    index = 0
    for i in range(L):
        if point[i] == C[S]:
            index = i
            break

    not_loop = index
    loop = L-index
    Loop = point[index:]
    B = 0
    for i in range(index, L):
        B += point[i]
    if B > 0:
        if not_loop > K:
            D = 0
            for i in range(K):
                D += point[i]
                ans = max(D, ans)

        if not_loop <= K:
            D = 0
            for i in range(not_loop):
                D += point[i]
            K -= not_loop
            for i in range(1, loop):
                Loop[i] += Loop[i-1]
            for i in range(1, loop):
                Loop[i] = max(Loop[i], Loop[i-1])
            if K % loop == 0:
                ans = max(ans, D+B*(K//loop-1)+Loop[-1])
            elif K % loop != 0:
                ans = max(ans, D+B*(K//loop-1) +
                          Loop[-1], D+B*(K//loop)+Loop[K % loop-1])

    else:
        ans = max(point[0], ans)
        for i in range(1, min(L, K)):
            point[i] += point[i-1]
            ans = max(point[i], ans)


print(ans)

Submission status: Accepted

Solution code:

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


def cycle(v):
    check=[False for _ in range(n+1)]
    check[v]=True
    while True:
        v=P[v]
        if check[v]:
            return v
        else:
            check[v]=True

ans=-1*float("inf")
for v in range(1,n+1):
    point=0
    tans=-1*float("inf")
    m=0
    st=cycle(v)

    while v!=st and m<k:
        m+=1
        v=P[v]
        point+=C[v]
        tans=max(tans,point)

    if m==k:
        ans=max(ans,tans)
        continue
       
    c_point=0
    t=0
    while True:
        t+=1
        v=P[v]
        c_point+=C[v]
        if v==st:
            break
    cp=0
    cpmax=-1*float("inf")
    if 2*t>k-m:
        v=st
        for _ in range(k-m):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)
 

    elif c_point>0:
        l=(k-m)//t
        mv=k-m-(l-1)*t
        cp=c_point*(l-1)
        v=st
        for _ in range(mv):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)

    else:
        v=st
        for _ in range(t):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
for i in range(n):
    p[i]-=1
c = list(map(int,input().split()))
par = [-1 for i in range(n)]
deep = [1 for i in range(n)]
ma = max(c)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if deep[x] > deep[y]:
            par[x] += par[y]
            par[y] = x
        elif deep[x] < deep[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            deep[x] += 1
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
for i in range(n):
    unite(i,p[i])
for i in range(n):
    if par[i] >= 0:
        continue
    else:
        t = -par[i]
        if t >= k:
            for j in range(k):
                tmp = 0
                tmp2 = p[i]
                for l in range(j+1):
                    tmp += c[tmp2]
                    tmp2 = p[tmp2]
                tmp3 = p[i]
                ma = max(ma,tmp)
                for l in range(t):
                    tmp += c[tmp2]
                    tmp -= c[tmp3]
                    tmp2 = p[tmp2]
                    tmp3 = p[tmp3]
                    ma = max(ma,tmp)
        else:
            tmpp = p[i]
            tmp7 = 0
            for j in range(t):
                tmp7 += c[tmpp]
                tmpp = p[tmpp]
            if tmp7 <= 0:
                for j in range(t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma = max(ma,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma = max(ma,tmp)
            else:
                g = k//t
                g2 = k//t - 1
                ma2 = 0
                ma3 = 0
                for j in range(k % t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma2 = max(ma2,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma2 = max(ma2,tmp)
                ma2 += tmp7 * g
                for j in range(t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma3 = max(ma3,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma3 = max(ma3,tmp)
                ma3 += tmp7 * g2
                ma = max(max(ma,ma2),ma3)
print(ma)

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
temp = [int(x) for x in input().split()]
p = [-1]
for x in temp:
    p.append(x)
c = [-1]
temp = [int(x) for x in input().split()]
 
for x in temp:
    c.append(x)
 
# print(p)
# print(c)
# print()
ans = -int(1e12)
for i in range(1, N+1):
    ans = max(ans, c[p[i]])
# print(ans)
for i in range(1, N+1):
    # print("i: ", i)
    visited = [False] * (N+1)
    cur_sum = 0
    cur_box = i
    l = 0
    k = K
    while k > 0:
        if visited[cur_box]:
            break
        cur_sum += c[p[cur_box]]
        ans = max(ans, cur_sum)
        visited[cur_box] = True
        cur_box = p[cur_box]
        k -= 1
        l += 1
        # print(cur_sum)
    if k != 0 and cur_sum > 0:
        cur_sum = (cur_sum * ((K // l)-1))
        ans = max(ans, cur_sum)
        k = (K % l) + l
        while k > 0:
            cur_sum += c[p[cur_box]]
            ans = max(ans, cur_sum)
            cur_box = p[cur_box]
            k -= 1
            # print(cur_sum)
    
    # print("i:", i , ", sum:", cur_sum)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root_rec(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def root(self, n):
        stack = []
        while n >= 0:
            stack.append(n)
            n = self.parent[n]
        m = stack.pop()
        while stack:
            self.parent[stack.pop()] = m
        return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups(self):
        if isinstance(self.parent,list):
            return list(filter(lambda i: self.parent[i]<0, range(len(self.parent))))
        else: # self.parent: defaultdict
            return list(filter(lambda i: self.parent[i]<0, self.parent.keys()))
 
    def groups_num(self):
        return len(self.groups())

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, K = inpl()
P = list(map(lambda x: x-1,inpl()))
C = inpl()

uf = UnionFind(N)
for i in range(N):
    uf.merge(i, P[i])

ans = C[0]
for g in uf.groups():
    L = uf.size(g)
    cycle = C[g]
    p = P[g]
    while p != g:
        cycle += C[p]
        p = P[p]
    q, r = K//L, K % L
    if cycle > 0:
        score = q * cycle
    else:
        score = 0

    s = g
    for _ in range(L):
        u = score
        t = s
        for i in range(L):
            u += C[t]
            t = P[t]
            if i == r:
                if q > 0 and cycle > 0:
                    u -= cycle
                elif q > 0 and cycle <= 0:
                    pass
                elif q == 0:
                    break
            if u > ans:
                ans = u
        s = P[s]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

N, K = mi()
P = li()
C = li()
ans = -float('inf')

for i in range(N):
    ind = i
    his = []
    while True:
        ind = P[ind] - 1
        his.append(C[ind])
        if ind == i:
            his = list(accumulate(his))
            #print(his)
            L = len(his)
            if K > L:
                if his[-1] > 0:
                    if not K%L:
                        ans = max(ans, his[-1] * (K//L), max(his) + his[-1] * max(K//L-1, 0))
                    else:
                        ans = max(ans, max(his[:K%L]) + his[-1] * (K//L), his[-1] * (K//L), max(his) + his[-1] * max(K//L-1, 0))
                else:
                    ans = max(ans, max(his))
            else:
                ans = max(ans, max(his[:K]))
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    p = nl()
    c = nl()
    seen = [0] * n
    ans = max(c)
    for i in range(n):
        if seen[i]:
            continue
        g = list()
        v = i
        while not seen[v]:
            g.append(c[v])
            seen[v] = 1
            v = p[v] - 1
        m = len(g)
        for i in range(1, m):
            g[i] += g[i-1]
        if k <= m:
            for i in range(m):
                for j in range(i+1, i+k+1):
                    cur = 0
                    if j >= m:
                        cur += g[-1]
                        j -= m
                    cur += g[j] - g[i]
                    if ans < cur:
                        ans = cur
        else:
            for i in range(m):
                for j in range(i+1, i+m+1):
                    cur = 0
                    if g[-1] > 0:
                        cur += g[-1] * ((k - (j-i))//m)
                    if j >= m:
                        cur += g[-1]
                        j -= m
                    cur += g[j] - g[i]
                    if ans < cur:
                        ans = cur
    print(ans)
    return

solve()

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n,k = mp()
p = lmp()
p = [p[i]-1 for i in range(n)]
c = lmp()


def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums

ans = -int(1e18)-5
for i in range(n):
    now = p[i]
    sc = [c[now]]
    cnt = 1
    while now != i:
        now = p[now]
        sc.append(c[now])
        cnt += 1
    cums = cum_sum(sc)[1:]
    if k <= len(cums):
        cums = cums[:k]
        ans = max(ans, max(cums))
    else:
        if cums[-1] <= 0:
            ans = max(ans, max(cums))
        else:
            lop = k // len(cums)
            u = [cums[j]+(lop-1)*cums[-1] for j in range(len(cums))] + [cums[j]+lop*cums[-1] for j in range(k%len(cums))]
            ans = max(ans,max(u))
print(ans)

Submission status: Accepted

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()))
res = [0] * N
for i in range(N):
  x = i
  score = -float("inf")
  loopscore = 0
  loop = 0
  while x != i or loop == 0:
    loop += 1
    x = p[x] - 1
    loopscore += c[x]
    if loop <= K: score = max(score, loopscore)
  #print(loopscore)
  if loopscore <= 0:
    res[i] = score
  else:
    res[i] = K // loop * loopscore
    #print(res, loop, loopscore)
    plus = 0
    plusmx = 0
    x = i
    t = 0
    while t < K % loop:
      t += 1
      x = p[x] - 1
      plus += c[x]
      plusmx = max(plusmx, plus)
    res[i] += plusmx
    if K >= loop: res[i] = max(res[i], (K // loop - 1) * loopscore + score)

print(max(res))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    # print(ans)
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        # if i==5:
        #     print(j,c[j],temp)
    t = cnt
    tt = ans
    # if i==8:
    #     print(temp,t)
    if t < k:
        if temp > 0:
            # print(k,t,i)
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
        else:
            j = p[i]
            for l in range(t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        # print(ans)
    # if ans == 29779631210:
    #     print(i,ans,t,temp)
    #     exit()
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()))
ans = max(C)
for i in range(N):
    check = {i}
    loop_score =[]
    k = i
    while True:
        loop_score.append(C[k])
        k = P[k]-1
        t = len(check)
        check.add(k)
        if len(check)==t:
            break
    cum_score = 0
    cum_scores = []
    for j in loop_score:
        cum_score+=j
        cum_scores.append(cum_score)
    loop = cum_scores[-1]
    compare = min(0,max(cum_scores))
    loops = K//len(cum_scores)
    plus = K%len(cum_scores)
    if loop > 0:
        compare = 0
        compare+=loops*loop
    final = cum_scores[:plus]
    if plus != 0:
        compare+=max(final)
        
    if loop > 0:
        compare2 = max(cum_scores) + (loops-1)*loop
        if compare2 > compare:
            compare = compare2

    if K < len(cum_scores):
        cum_scores = cum_scores[:K]
    if max(cum_scores)>compare:
        compare = max(cum_scores)
    if compare>ans and compare!=0:
        ans = compare
print(ans)

Submission status: Accepted

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

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

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

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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


    mod=10**9+7
    N,K=MI()
    P=LI()
    C=LI()
    
    for i in range(N):
        P[i]-=1
    
    uf =UnionFind(N)
    for i in range(N):
        uf.union(i,P[i])
        
    from collections import defaultdict
    dd = defaultdict(list)
        
    for i in range(N):
        root=uf.find(i)
        dd[root]+=[i]
        
    ansAll=-1*(10**10)
    for k,v in dd.items():
        N2=len(v)
        #rootから移動した時の点数の順番，3周分
        L=[0]*(3*N2+3)
        now=k
        for i in range(3*N2+3):
            nxt=P[now]
            L[i]=C[nxt]
            now=nxt
        S=[0]*(3*N2+3)
        for i in range(3*N2+2):
            S[i+1]=S[i]+L[i]
        
        ans=0
        
        ROOP=S[N2]-S[0] 
        if ROOP>0:#1週分
            roop=max(K//N2-1,0)#1周分が+でも最後の1つをとらない方が良いみたいなことも
            ans+=ROOP*roop
            rem=K-roop*N2
        else:
            roop=0
            rem=min(K,N2)
            
        if roop==0:
            temp=-1*(10**10)
        else:
            #1回以上ループしていれば，追加で1こも取る必要はない
            temp=0
        for i in range(1,rem+1):#i個トル
            for j in range(N2+1):#jからスタート
                s=S[j+i]-S[j]
                temp=max(temp,s)
        ans=ans+temp
        
        # print(k,v,roop,rem)
        # print(L)
        # print(S)
        # print(temp,ans)
        # print("---")
        
        
        ansAll=max(ansAll,ans)
        
    print(ansAll)
        
            
    
 
        
    
            
    

main()