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:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        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,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

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

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

U=Union_Find(N+1)

for i in range(1,N+1):
    U.union(i,P[i])

Cycle_Point={}
for a in U.roots():
    if a==0:
        continue

    b=P[a]
    S=C[a]
    while a!=b:
        S+=C[b]
        b=P[b]
    Cycle_Point[a]=S

Ans=-float("inf")
for i in range(1,N+1):
    group=U.find(i)
    length=U.size(i)

    rap,remain=divmod(K,length)

    if Cycle_Point[group]>0:
        Base_Score=Cycle_Point[group]*rap

        Temp_Score=Base_Score
        Score=Temp_Score

        p=i
        for _ in range(remain):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)
    else:
        Temp_Score=0
        Score=C[P[i]]

        p=i
        for _ in range(min(length,K)+1):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)

print(Ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A=[[0]*n]
Cur=[int(i)+1 for i in range(n)]
L=[0]*n
for _ in range(n):
  N=[0]*n
  for i in range(n):
    N[i]=A[-1][i]+C[P[Cur[i]-1]-1]
    Cur[i]=P[Cur[i]-1]
    if L[i]==0 and Cur[i]==i+1:
      L[i]=_+1
  A.append(N)
ans=max(A[1])
for i in range(n):
  ct=0
  loop=L[i]
  loop_ct=A[loop][i]
  rem=-float("inf")
  if k>loop and loop_ct>0:
    ct+=(k//loop)*loop_ct
    
    for j in range(k%loop):
      rem=max(rem,A[j+1][i])
    ans=max(ans,rem+ct)
  else:
    for j in range(min(k,n)):
      rem=max(rem,A[j+1][i])
    ans=max(ans,rem)
print(ans)

Submission status: Wrong Answer

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

def junkan_max_score(junkan, C, K):
    junkan_scores = [C[junkan[j+1]] if j != len(junkan)-1 else C[junkan[0]]
                    for j in range(len(junkan))
                    ]
    
    if len(junkan) > K or sum(junkan_scores) <= 0:
        return max([sum(junkan_scores[:i+1]) for i in range(K)])
    else:
        n_junkan = int(K/len(junkan))
        base_score = n_junkan*sum(junkan_scores)
        nokori_K = K-(n_junkan*len(junkan))
        if nokori_K == 0:
            return base_score
        else:
            return base_score+max([sum(junkan_scores[:i+1]) for i in range(nokori_K)])

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))
seen = [None]*n
vs = []
ans = -float("inf")
def sub(v, num):
    v = v+v
    n = len(v)
    val = sum(v[:num])
    ans = val
    for i in range(num,n):
        val = val + v[i] - v[i-num]
        ans = max(ans, val)
    return ans
for i in range(n):
    if seen[i]:
        continue
    v = []
    s = i
    seen[s] = True
    while True:
        s = p[s]
        seen[s] = True
        v.append(c[s])
        if s==i:
            break
    ss =sum(v)
    val1 = -float("inf")
    if ss>=1:
        val1 = ss*(k//len(v))
        tmp = max(sub(v,i) for i in range(k%len(v)+1))
        val1 += tmp
    val2 = -float("inf")
    for i in range(1,len(v)+1):
        val2 = max(val2, sub(v, i))
        
    val = max(val1, val2)
#     print(val1, val2, val, v, i, ss)

    ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    C = list(map(int, readline().split()))

    ans = -INF
    for i in range(N):
        seen = [False] * N
        s = 0
        s_max = -INF
        scores = []
        k = 0

        while k < K and not seen[i]:
            seen[i] = True
            s += C[P[i]]
            scores.append(s)
            if s_max < s:
                s_max = s
            i = P[i]
            k += 1

        if k == K and ans < s_max:
            ans = s_max
        elif scores[-1] > 0:
            tmp = max(s_max, scores[-1] * (K // k) + max(scores[: K % k], default=0))
            if ans < tmp:
                ans = tmp
        else:
            if ans < s_max:
                ans = s_max

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = max(C)
d = {}
for i in range(N):
    if i in d:
        continue
    s = P[i]-1
    d[s] = 0
    l = [C[i]]
    while s != i:
        l.append(C[s])
        s = P[s]-1
        d[s] = 0
    c = K//len(l)*sum(l)
    l += l
    if c>0:
        r = K%(len(l)//2)
        s = sum(l[:r])
        ans = max(ans,c+s)
        for j in range(r,len(l)):
            s -= l[j-r]
            s += l[j]
            ans = max(ans,c+s)
    else:
        c_l = [0]*(len(l)+1)
        for i in range(len(l)):
            c_l[i] = c_l[i-1]+l[i]
        r = min(len(l)//2,K)
        for j in range(len(l)//2):
            for k in range(r):
                s = c_l[j+k]-c_l[j-1]
                ans = max(ans,s)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10**18


def main():

    N, K = in_nn()
    P = in_nl()
    C = in_nl()

    if K < N + 10:
        ans = -INF
        for i in range(N):
            score = 0
            max_score = -INF
            now = i

            for j in range(K):
                now = P[now] - 1
                score += C[now]
                max_score = max(score, max_score)
            ans = max(ans, max_score)

        print(ans)
        exit()

    else:

        ans = -INF
        for i in range(N):
            score = 0
            max_score = -INF
            now = i
            search = {now}
            move_cnt = 0

            for _ in range(N + 10):
                now = P[now] - 1
                score += C[now]
                max_score = max(score, max_score)
                move_cnt += 1

                if now in search:
                    break
                search.add(now)

            if score < 0:
                ans = max(ans, max_score)
            else:
                tk = K % move_cnt
                score = score * (K // move_cnt)
                max_score = score
                now = i
                for x in range(tk):
                    now = P[now] - 1
                    score += C[now]
                    max_score = max(score, max_score)
                ans = max(ans, max_score)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans=[]
for i in range(N):
    trace=[-1 for _ in range(N)]
    cand=[0]
    trace[i]=0
    pos=i
    cnt=1
    while True:
        pos=P[pos]-1
        if trace[pos]==-1:
            cand.append(cand[-1]+C[pos])
            trace[pos]=cnt
            cnt+=1
        else:
            init=trace[pos]
            loop=cnt-init
            point=cand[-1]+C[pos]-cand[init]
            break
    cand.append(cand[init]+(K-init)//loop*point+cand[init+(K-init)%loop]-cand[init])
    ans.append(max(cand[1:]))
print(max(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()))
X = -float('inf')
for i in range(1, N+1):
    now = i
    point_i = 0
    K_i = K
    while True:
        now = P[now]
        point_i += C[now]
        K_i -= 1
        X = max(X, point_i)
        if K_i == 0:
            break
        if now == i:
            roop = K - K_i
            roop_n = K // roop
            roop_r = K % roop
            point_i = point_i * roop_n
            X = max(X, point_i)
            for j in range(roop_r):
                now = P[now]
                point_i += C[now]
                X = max(X, point_i)
            break
    X = max(X, point_i)
print(X)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
#"""
Ps = [P-1 for P in map(int, input().split())]
Cs = list(map(int, input().split()))
"""
Ps = [(i+1)%N for i in range(N)]
Cs = [-(10 ** 9)] * N
#"""
group = [-1] * N
grouped_Cs = []
next_num = 0
for i in range(N):
    if group[i] == -1:
        g = []
        while group[i] == -1:
            group[i] = next_num
            g.append(Cs[i])
            i = Ps[i]
        grouped_Cs.append(g)
        next_num += 1

max_score = -(10 ** 18 + 10 ** 9)
for g in grouped_Cs:
    l = len(g)
    q, r = divmod(K-1, l)
    r += 1
    score = max(0, sum(g) * q)
    max_s = -(10 ** 18 + 10 ** 9)
    for k in range(1, r+1):
        s = sum(g[:k])
        max_s = max(max_s, s)
        for i in range(l):
            s -= g[i]
            s += g[(i+k)%l]
            max_s = max(max_s, s)
    
    max_score = max(max_s + score, max_score)

print(max_score)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**10

n, k = map(int, input().split())
p = [int(item) - 1 for item in input().split()]
c = [int(item) for item in input().split()]
visited = [0] * n
cycles = []

for i in range(n):
    if visited[i]:
        continue
    nc = []
    v = i
    visited[v] = True
    nc.append(c[v])
    while not visited[p[v]]:
        v = p[v]
        visited[v] = True
        nc.append(c[v])
    cycles.append(nc)

ans = -INF 
for cycle in cycles:
    length = len(cycle)
    c_num = (k - 1) // length
    total = sum(cycle) * c_num
    total = max(0, total)
    rest = k - (c_num * length)
    cycle = cycle + cycle
    for l in range(length):
        total_rest = 0
        for diff in range(rest):
            total_rest += cycle[l + diff]
            ans = max(ans, total + total_rest)

print(ans)

Submission status: Wrong Answer

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


def calc(start, P, C, k):
    seen = {start}
    loop = 1
    pos = start
    res = 0
    maxim = -float("INF")
    while True:
        next = P[pos]
        point = C[next]
        res += point
        pos = next
        if res > maxim:
            maxim = res
        if pos in seen:
            break
        seen.add(pos)
        loop += 1
        if loop == k+1:
            break

    if res <= 0:
        return maxim

    residue = k - loop
    t = residue // loop
    residue %= loop
    max1 = res * t + maxim
    res *= (t+1)
    max2 = res
    for _ in range(residue):
        next = P[pos]
        point = C[next]
        res += point
        pos = next
        if res > max2:
            max2 = res

    return max(max1, max2)


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

    ans = -float("INF")
    for start in range(n):
        res = calc(start, P, C, k)
        if ans < res:
            ans = res

    print(ans)


if __name__ == "__main__":
    main()

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()))
for i in range(n):
    P[i] -= 1

V = [0] * n
ans = -float("inf")
an = 0
for i in range(n):
    if V[i] == 0:
        A = []
        V[i] = 1
        ii = P[i]
        V[ii] = 1
        A.append(C[ii])
        while ii != i:
            ii = P[ii]
            V[ii] = 1
            A.append(C[ii])
        # print(A)
        an = 0
        anb=0
        anb2=0
        kb=k
        kb2=k
        if sum(A) > 0:
            anb += sum(A) * (k//len(A))
            kb = k%len(A)
        if kb > len(A) and sum(A) > 0:
            anb2 += sum(A) * (k//len(A)-1)
            kb2 = k % len(A) + k
        A += A
        S = [A[0]]
        # print(an,k)
        for i in range(1,len(A)):
            S.append(S[-1]+A[i])
        # print(S)
        anc = 0
        for i in range(len(S)):
            for j in range(i+1, min(i+kb2+1,len(S))):
                anc = max(anc,S[j]-S[i])

        for i in range(len(S)):
            for j in range(i+1, min(i+kb+1,len(S))):
                an = max(an,S[j]-S[i])

        ans = max(an+anb,anc+anb2,ans)
            
if ans == 0 and max(C) < 0:
    print(max(C))
else:
    print(ans)

Submission status: Wrong Answer

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

base = max(0, sum(C)*(k//n))
k = k%n
M = max(C)

for i in range(n):
  score = 0
  now = i
  for j in range(k):
    now = P[now]-1
    score += C[now]
    M = max(M, score)
  
print(base+M)

Submission status: Wrong Answer

Solution code:
N, K = (int(i) for i in input().split())
P = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
score = -10**9
for i in range(N):
    p = i
    k = 0
    cnt = 0
    while k < K:
        p = P[p] - 1
        c = C[p]
        k = k + 1
        cnt = cnt + c
        score = max(cnt, score)
        if p == i:
            if cnt <= 0:
                break
            else:
                x = K//k
                cnt = cnt * x
                k = x * k
print(score)

Submission status: Wrong Answer

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

ans = (10**9)*(-1)
for start in range(1,n+1):
    val = 0
    vals = []
    already_set = set()
    curr_mass = start
    while True:
        next_mass = pl[curr_mass]
        point = cl[next_mass]
        if next_mass in already_set:
            break
        else:
            vals.append(point)
            already_set.add(next_mass)
            curr_mass = next_mass
    if k <= len(vals):
        c_max = vals[0]
        c_val = vals[0]
        if len(vals) > 1:
            for v in vals[1:k]:
                c_val += v
                c_max = max(c_max, c_val)
        # print(c_max)
        ans = max(c_max,ans)
    else:
        v_sum = sum(vals)
        if v_sum <= 0:
            c_max = vals[0]
            c_val = vals[0]
            if len(vals) > 1:
                for v in vals[1:]:
                    c_val += v
                    c_max = max(c_max, c_val)
            # print(c_max)
            ans = max(c_max,ans)
        else:
            loop_cnt = k//len(vals)
            rem = k - loop_cnt*len(vals)
            c_max = v_sum*loop_cnt
            c_val = c_max
            if rem > 0:
                for v in vals[:rem]:
                    c_val += v
                    c_max = max(c_max, c_val)
            # print(c_max)
            ans = max(c_max,ans)
print(ans)
# 2939275739

Submission status: Wrong Answer

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


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(n):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    #print(a, b)
    ans = max(b)
    for i in range(n):
        co = b[i]
        i = a[i]
    #    print(i, co)
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    #        print(i, co)
            ans = max(ans, co)
    #    print()

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]



def main():
    N, K = read_values()
    P = read_list()
    C = read_list()

    res = - 10 ** 10
    for i in range(N):
        t = []
        c = 0
        p = i
        while len(t) == 0 or p != i:
            p = P[p] - 1
            c += C[p]
            t.append(c)

        # print(t, c)
        if len(t) > K or c < 0:
            res = max(res, max(t))
        else:
            s = K // len(t) * c
            k = K % len(t)
            # print(f"s: {s}, k: {k}")
            tmp = - 10 ** 10
            for i in range(k):
                tmp = max(tmp, s + t[i])
            
            s -= c
            for i in range(len(t)):
                tmp = max(tmp, s + t[i])
            
            res = max(res, tmp)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
P = [i-1 for i in map(int, input().split())]
C = list(map(int, input().split()))

seen = [0] * N

ans = -10**20

for i in range(N):
    if not seen[i]:
        seen[i] = 1
        loop = [C[i]]
        while True:
            i = P[i]
            if seen[i]:
                break
            seen[i] = 1
            loop.append(C[i])
        L = len(loop)
        loop = list(accumulate(loop*2, initial=0))
        if loop[L] <= 0:
            move = min(L, K)
            for i in range(L):
                for j in range(1, move+1):
                    ans = max(ans, loop[i+j]-loop[i])
        else:
            div, mod = divmod(K, L)
            tmp = div * loop[L]
            move = min(mod, K)
            for i in range(L):
                for j in range(1, move+1):
                    ans = max(ans, tmp + loop[i + j] - loop[i])

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()))
X = -float('inf')
for i in range(1, N+1):
    now = i
    point_i = 0
    K_i = K
    while True:
        now = P[now]
        point_i += C[now]
        K_i -= 1
        X = max(X, point_i)
        if now == i:
            roop = K - K_i
            roop_n = K // roop
            roop_r = K % roop
            point_i = point_i * roop_n
            for j in range(roop_r):
                now = P[now]
                point_i += C[now]
            break
        if K == 0:
            break
    X = max(X, point_i)
print(X)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  d=(k-1)//len(x)
  dd=max(d*sum(x),0)
  kk=k-d*len(x)
  s=0
  x.append(x[0])
  for i in x[1:kk+1]:
    s+=i
    ans=max(ans,s+dd)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10**18


def main():

    N, K = in_nn()
    P = in_nl()
    C = in_nl()

    if K <= N:
        ans = -INF
        for i in range(N):
            score = 0
            max_score = -INF
            now = i

            for j in range(K):
                now = P[now] - 1
                score += C[now]
                max_score = max(score, max_score)
            ans = max(ans, max_score)

        print(ans)
        exit()

    else:

        ans = -INF
        for i in range(N):
            score = 0
            max_score = -INF
            now = i
            search = {now}
            move_cnt = 0

            for _ in range(N):
                now = P[now] - 1
                score += C[now]
                max_score = max(score, max_score)
                move_cnt += 1

                if now in search:
                    break
                search.add(now)

            if score < 0:
                ans = max(ans, max_score)
            else:
                tk = K % move_cnt
                score = score * (K // move_cnt)
                max_score = score
                now = i
                for x in range(tk):
                    now = P[now] - 1
                    score += C[now]
                    max_score = max(score, max_score)
                ans = max(ans, max_score)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = map(int, readline().split())
    p = list(map(int, readline().split()))
    p = [x - 1 for x in p]
    c = list(map(int, readline().split()))
    ans = -INF

    for i in range(n):
        cur = i
        nx = -1
        cnt = 0
        score_dict = dict()
        score_dict[0] = 0
        score = 0
        rem = k
        while rem > 0 and nx != i:
            cnt += 1
            rem -= 1
            nx = p[cur]
            score += c[nx]
            score_dict[cnt] = score
            ans = max(ans, score)
            cur = nx

        if rem > 0 and score > 0:
            loop = (rem // cnt) - 1
            if loop > 0:
                score += score * loop
                rem -= loop * cnt
            for j in range(min(cnt, rem + 1)):
                st = score + score_dict[j]
                ans = max(ans, st)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
R = lambda: map(int, raw_input().split())
n, k = R()
p, c = R(), R()
p = [x - 1 for x in p]
vis = [False] * n
ans = max(c)

for i in xrange(n):
    if vis[i]:
        continue
    t = [c[i]]
    j = p[i]
    while j != i:
        vis[j] = True
        t.append(c[j])
        j = p[j]

    m = len(t)
    s = sum(t)

    ta = 0
    tk = k
    if s > 0:
        ta += s * (tk / m)
        tk %= m
    else:
        tk = m

    t = t + t
    j = -1
    v = 0
    mv = max(t)
    for i in xrange(len(t)):
        if v < 0:
            j = i - 1
            v = 0
        v += t[i]
        if i - j > tk:
            j += 1
            v -= t[j]
        mv = max(mv, v)
    ans = max(ans, ta + mv)
print ans

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
# print()
# print(*P)
# print(*C)
x = 0
used = [0] * N
root = [-1] * N
path = defaultdict(list)
score = defaultdict(list)
for i in range(N):
    if used[i]:
        continue
    x = i
    while used[x] == 0:
        used[x] = 1
        path[i].append(x)
        score[i].append(C[x])
        root[x] = i
        x = P[x]
ans = -float('inf')
for r in path:
    pa, sc, le = path[r], score[r], len(path[r])
    for i in range(le-1):
        sc[i+1] += sc[i]
    tmp = sc[-1] * (K // le)
    if tmp < 0:
        m = -float('inf')
        for i in range(len(pa)):
            for j in range(i+1, len(pa)):
                if j - i <= K:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= K:
                    m = max(m, sc[le-1] - sc[j] + sc[i])
        ans = max(ans, m)
    else:
        k = K % le
        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= k:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= k:
                    m = max(m, sc[le-1] - sc[j] + sc[i])
        ans = max(ans, m + tmp)
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()))
memo = []
ans = -1e16
for i in range(1,N+1):
  cnt = 0
  sumn = 0
  now = i
  for j in range(K):
    now = P[now]
    cnt += 1
    sumn += C[now]
    ans = max(sumn,ans)
    if now == i:
      break
  memo.append((cnt, sumn))

for i in range(1,N+1):
  cnt, sumn = memo[i-1]
  if sumn < 0:
    continue
  if cnt >= K:
    continue
  sumn = sumn * (cnt // K)
  cnt = cnt % K 
  for j in range(K):
    now = P[now]
    cnt += 1
    sumn += C[now]
    ans = max(sumn,ans)

for i in range(1,N+1):
  if P[i] == i:
    ans = max(ans, C[i] *K)
    
#print(memo)
print(ans)