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:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

n=0
loops=[]
loops_score=[]
searched=[False]*N
sum_len=0

for _ in range(N):
    n=searched.index(False)
    l=[]
    ls=[]
    for i in range(N):
        n=P[n]-1
        searched[n]=True
        if n in l:
            break
        l.append(n)
        ls.append(C[n])
    
    loops.append(l)
    loops_score.append(ls)
    sum_len+=len(l)
    if sum_len==N:
        break
    
#print(loops)
#print(loops_score)

ans=-1*float('inf')

for scores in loops_score:
    ans_=0
    ls=len(scores)
    scores_sum=sum(scores)
    
    if K>ls and scores_sum>0:
        ans_loop=scores_sum*(K//ls)
    else:
        ans_loop=0
        
    maxlen=min(K,ls)
    #print(maxlen)
    ex_scores=scores+scores[:-1]
    #print(ex_scores)
    le=ls*2-1
    
    ruiseki=[0]*(le+1)
    for i in range(1,le+1):
        ruiseki[i]=ruiseki[i-1]+ex_scores[i-1]
    #print(ruiseki)
    
    ans_=max(scores)
    
    if K>=2:
        for d in range(2,maxlen):
            #for j in range(le+1-d):
            for j in range(ls):
                ans_=max(ans_,ruiseki[j+d]-ruiseki[j])
                #print(scores[j:j+d])
                #print(le,d,j,ans_+ans_loop)
                if d==maxlen-1:
                    break
    ans=max(ans,ans_+ans_loop)
        
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import glob

class InputGenerator(object):
    def __init__(self, input_path=None):
        if input_path != None:
            self.g = self.input_generator(input_path)
        else:
            self.g = None

    def input_generator(self, input_path):
        with open(input_path) as f:
            for line in f:
                yield line

    def get_input(self):
        if self.g == None:
            return input()
        else:
            return next(self.g)

def get_max_local_trip(sorted_c_list, local_trip_k):
    n = len(sorted_c_list)
    local_trip_sum_max = -1e10
    sorted_c_list += sorted_c_list
    for i in range(0, n):
        for j in range(i, n):
            local_trip = sorted_c_list[i:j+1]
            if len(local_trip) <= local_trip_k:
                local_trip_sum = sum(local_trip)
                # print(i, j, local_trip, len(local_trip), local_trip_sum)
                if local_trip_sum > local_trip_sum_max:
                    local_trip_sum_max = local_trip_sum

    return local_trip_sum_max

def get_local_kn(sorted_c_list, k):
    n = len(sorted_c_list)

    if k % n == 0:
        num_round    = k // n - 1
        local_trip_k = n
    else:
        num_round    = k // n
        local_trip_k = k % n
        # print(num_round, local_trip_k)

    return num_round, local_trip_k

def solve(gen):
    n, k = list(map(int, gen.get_input().rstrip().split()))
    p_list = list(map(int, gen.get_input().rstrip().split()))
    c_list = list(map(int, gen.get_input().rstrip().split()))
    # print(n, k)
    # print(p_list)
    # print(c_list)

    sorted_c_list = []
    sorted_c_list_list = []

    unvisited_list = list(range(n))
    for i in unvisited_list:
        start_i = i
        while True:
            next_i = p_list[i] - 1
            sorted_c_list.append(c_list[next_i])
            i = next_i
            if i == start_i:
                # print(sorted_c_list)
                sorted_c_list_list.append(sorted_c_list)
                sorted_c_list = []
                break
            else:
                unvisited_list.remove(i)

    global_max_score = -1e10
    for sorted_c_list in sorted_c_list_list:
        num_round, local_trip_k = get_local_kn(sorted_c_list, k)
        round_sum = sum(sorted_c_list)

        local_max_score = get_max_local_trip(sorted_c_list, local_trip_k)
        if round_sum > 0 and num_round > 0:
            local_max_score += num_round * round_sum

        if global_max_score < local_max_score:
            global_max_score = local_max_score

    print(global_max_score)

if __name__ == '__main__':
    test_flag = len(sys.argv) > 1

    if test_flag == True:
        file_path_list = sorted(glob.glob('test/*'))
    else:
        file_path_list = [None]

    for file_path in file_path_list:
        gen = InputGenerator(file_path)
        solve(gen)

Submission status: Wrong Answer

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

    ans = -10**9
    loops = {}

    for i in range(1,N+1):
        p = i
        k = K
        max_score = -10**9
        score = 0
        visited = set([p])
        visited_lst = [p]
        score_lst = [0]
        while 0 < k:
            score += C[P[p]]
            max_score = max(max_score,score)
            score_lst.append(score)
            p = P[p]
            k -= 1
            if p in visited:
                if p in loops:
                    if 0 < loops[p][0]:
                        score += loops[p][0]*(k//loops[p][1])
                        k %= loops[p][1]
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
                else:
                    idx = visited_lst.index(p)
                    l = len(score_lst)-1-idx
                    for j in range(idx,l):
                        loops[visited_lst[j]] = [score-score_lst[idx],l]
                    if 0 < score-score_lst[idx]:
                        score += (score-score_lst[idx])*(k//l)
                        k %= l
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
            else:
                visited.add(p)
                visited_lst.append(p)
        # print(max_score)
        max_score = max(max_score,score)
        ans = max(ans,max_score)
    # print(loops)

    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()))
m = None
for i in range(N):
    nx = P[i] - 1
    r = 0
    s = {nx}
    for j in range(K):
        s.add(nx)
        r += C[nx]
        m = r if m is None else max(r, m)
        nx = P[nx] - 1
        if nx in s:
            if r > 0 and K > j + 1:
                r *= (K - j - 1) // j
            m = r if m is None else max(r, m)
            break
print(m)

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))
    vis = [0 for i in range(n)]
    grps = []
    g = 1
    for i in range(n):
        if vis[i] == 0:
            que = [i]
            vis[i] = g
            cnt = [i]
            while len(que)>0:
                st = que.pop(0)
                if vis[p[st]-1]!=0:
                    g += 1
                    grps.append(cnt)
                    break
                vis[p[st]-1] = g
                cnt.append(p[st]-1)
                que.append(p[st]-1)

    loop_sum = [0 for i in range(len(grps))]
    for i in range(len(grps)):
        s = 0
        for j in range(len(grps[i])):
            s += c[grps[i][j]]
        loop_sum[i] = s

    ans = -1 * float('inf')
    g_max = -1 * float('inf')
    for i in range(len(grps)):
        g_len = len(grps[i])
        for j in range(g_len):
            loop = k//g_len
            lost = k - loop*g_len
            if lost == 0:
                lost = g_len
                loop -= 1
            s = 0
            point = grps[i][j]
            for _ in range(lost):
                point = p[point]-1
                s += c[point]
                if s > g_max:
                    g_max = s
            s += loop * loop_sum[i]
            if ans < s:
                ans = s
    print(max(ans,g_max))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
N, K = map(int, input().split())
Plst = list(map(int, input().split()))
Clst = list(map(int, input().split()))

lst = [0]*N
Mb = -10000000000000000000000
for j in range(K):
    afPlst = copy.deepcopy(Plst)
    for i in range(N):
        lst[i] = lst[i] + Clst[Plst[i]-1]
        afPlst[i] = Plst[Plst[i]-1]

    Plst = copy.deepcopy(afPlst)
    Ma = max(lst)
    if Ma > Mb:
        Mb = Ma

print(Mb)

Submission status: Wrong Answer

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

co = 0
L = 0
s = 0
mod = 0
max = 0
for i in range(1,n+1):
	m = i
	while co == 0:
		s += c[m-1]
		m = p[m-1]
		L += 1
		if m == i:
			co += 1
	m = i
	if s < 0:
		for _ in range(k%L):
			mod += c[m-1]
			m = p[m-1]
			if (k//L)*s + mod >= max:
				max = (k//L)*s + mod
	else:
		for _ in range(k%L):
			mod += c[m-1]
			m = p[m-1]
			if (k//L)*s + mod >= max:
				max = (k//L)*s + mod
	co = 0
	L = 0
	s = 0
	mod = 0

print(max)

Submission status: Wrong Answer

Solution code:
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

visited=[False]*N
loop=[]
res=-10**15
for i in range(N):
    if visited[i]!=True:
        loop.append([])
        #loop[-1].append(C[i])
        now=P[i]
        while visited[now]!=True:
            loop[-1].append(C[now])
            visited[now]=True
            now=P[now]

for i in range(len(loop)):
    score=0
    loop_sum=0
    for k in range(len(loop[i])):
        loop_sum+=loop[i][k]
    loop_cnt=len(loop[i])
    kaisuu=K

    if K>loop_cnt:
        if loop_sum>0:
            score+=(K//loop_cnt)*loop_sum
            kaisuu=K%loop_cnt
        else:
            kaisuu=loop_cnt
    else:
        kaisuu=K

    test=loop[i]+loop[i]
    A=[0]*len(test)
    A[0]=test[0]
    ans=-10**15
    #for index in range(1,len(test)):
        #A[index]=A[index-1]+test[index]
    for l in range(0,len(loop[i])):
        for r in range(l,len(test)):
            sum=0
            for k in range(l,r):
                sum+=test[k]
            ans=max(ans,sum)   
            
    ans+=score
    res=max(ans,res)


print(res)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  # print(l)
  # print(roop)

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1]))
    else:
      ans=max(ans,max(l[i][1:K+1]))
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans1=c*l[i][roop_count]
        k=K%roop_count
        _ans1+=max(l[i][1:k+1]+[0])
        ans=max(ans,_ans1)
        if c>=1:
          _ans2=(c-2)*l[i][roop_count]
          _ans2+=max(l[i][:K+1])
          ans=max(ans,_ans1,_ans2)

  return ans

# main()
print(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 = -100000000000000000000000000000000000
ans_ = 0
for i in range(n):
    base = c[i]
    ans_check = c[i]
    ttt = p[i] - 1
    aaa = k // n
    for j in range(n):
        ans_check += c[ttt]
        ttt = p[ttt] - 1
        if base < ans_check:
            base = ans_check
    
    if base > 0:
        ans_ = base * aaa
        ttt = p[i]-1
        for k in range(k % n + 1):
            ans_ += c[ttt]
            ttt = p[ttt] - 1
            if base < ans_:
                base = ans_
    else:
        ans_ = base
        
    if ans < ans_:
        ans = ans_
        
        
print(ans)

Submission status: Wrong Answer

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


def print_ans(N, K, pr, cr):
    """Test Case
    >>> print_ans(5, 2,[2, 4, 5, 1, 3], [3, 4, -10, -8, 8])
    8
    """
    ans = 0

    maximum = 0
    pr = [p - 1 for p in pr]

    for i in range(N):
        point = i
        tmp = 0
        for _ in range(K):
            tmp += cr[point]
            maximum = max(tmp, maximum)
            point = pr[point]
    print(maximum)


if __name__ == '__main__':
    N, K = map(int, input().rstrip().split())
    pr = list(map(int, input().rstrip().split()))
    cr = list(map(int, input().rstrip().split()))
    print_ans(N, K, pr, cr)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice

def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    sumc = sum(C)
    v = 0
    if sumc > 0 and N <= K:
        x = K // N
        v = x * sumc
        K -= x * N

    points = [v] * (N * (N + 1))
    pos = list(range(1, N + 1))
    for i in range(1, min(N, K) + 1):
        for n in range(N):
            new_pos = pos[n] = P[pos[n]]
            points[i * N + n] = points[i] + C[new_pos]
    
    ans = max(points)
    if ans == 0:
        y = max(C[1:])
        if y < 0:
            ans = y
    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, K, P, C):
    ans = max(C)
    for i in range(N):
        used = [False] * N
        now = 0
        mx = -INF
        cnt = 0
        while True:
            if used[i]:
                break
            used[i] = True
            now += C[i]
            mx = max(mx, now)
            i = P[i] - 1
            cnt += 1
        tmp = max(mx, now)
        if now > 0:
            cycle, mod = divmod(K, cnt)
            if cycle > 1:
                tmp = max(tmp, now * (cycle - 1) + mx)
            t = now * cycle
            tmp = max(tmp, t)
            for j in range(mod):
                t += C[i]
                tmp = max(tmp, t)
                i = P[i] - 1
        ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    *C, = map(int, input().split())
    main(N, K, P, C)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
*P, = map(int, input().split())
*C, = map(int, input().split())

P = [p-1 for p in P]

used = [0]*N
ans = -float('inf')
for x in range(N):
    if used[x]:
        continue
    used[x] = 1
    Q = [C[x]]

    while not used[P[x]]:
        x = P[x]
        used[x] = 1
        Q.append(C[x])

    M = len(Q)
    acc = list(accumulate(Q*2))
    if acc[M-1] > 0:
        ret = acc[M-1]*(K//M)
        ret += max(acc[K % M+i] - acc[i] for i in range(M))

    else:
        R = Q*2
        ret = -float('inf')
        prev = 0
        cnt = 0
        for i, r in enumerate(R):
            if cnt >= K:
                prev -= R[i-K]
                cnt -= 1
            if prev+r > r:
                cnt += 1
                s = prev + r
            else:
                cnt = 1
                s = r
            ret = max(ret, s)
            prev = s

    if ret > ans:
        ans = ret

print(ans if ans > -float('inf') else max(C))

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
Pt = lma()
P = [p-1 for p in Pt]
C = lma()
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
uf = unionfind(n)
for i in range(n):
    uf.unite(i,P[i])

def score(x):#xからスタートしたスコア
    l = uf.get_size(x)
    p,r = divmod(k,l)
    tmp = [-10**15 for i in range(l+1)]#一回の累積和
    tmp_p = [-10**15 for i in range(l+1)] #pサイクル目の累積和
    ret = 0
    if p==0:
        xt=x
        mx = -10*15
        for i in range(r):
            nex = P[xt]
            ret+=C[nex]
            xt = nex
            mx = max(mx,ret)
        return mx

    gain_cycle = 0
    xt=x
    for i in range(l):
        nex = P[xt]
        gain_cycle +=C[nex]
        ret+=C[nex]
        tmp[i+1] = ret
        if i<=r-1:
            tmp_p[i+1]=ret
        xt = nex
    if gain_cycle>=0:
        return max(tmp_p) + p* gain_cycle
    else:
        return max(tmp)

        #print(ret,"ret")

ans = -10**15
for i in range(n):
    ans = max(ans,score(i))
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()))

tokuten = []
zan = p[:]
while len(zan) != 0:
    loop = []
    start = zan.pop()
    loop.append(c[start-1])
    next = p[start-1]
    zan.remove(next)
    while start != next:
        loop.append(c[next-1])
        next = p[next-1]
        if next in zan:
            zan.remove(next)
    tokuten.append(loop)

ans = -10e9
for loop in tokuten:
    tmp = 0
    le = len(loop)
    su = sum(loop)
    if le < k:
        if su > 0:
            tmp += (k//le)*su
            amari = k%le
            ma = -10e10
            lplp = loop + loop
            index = loop.index(max(loop))
            for i in range(1,amari+1):
                ma = max(ma,sum(lplp[index:i+index]))
            tmp += ma
            ans = max(ans,tmp)
        if su <= 0:
            ma = -10e10
            lplp = loop + loop
            index = loop.index(max(loop))
            for i in range(1,le+1):
                ma = max(ma,sum(lplp[index:i+index]))
            ans = max(ans,ma)
    else:
        ma = -10e10
        lplp = loop + loop
        index = loop.index(max(loop))
        for i in range(1,k+1):
            ma = max(ma,sum(lplp[index:i+index]))
        ans = max(ans,ma)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

Q=[]
uf=UnionFind(N)
for i in range(N):
    uf.union(i,P[i]-1)
D1=list(uf.all_group_members().values())
D2=[]
for i in D1:
    ans=0
    for j in i:
        ans+=C[j]
    D2.append(ans)
L=[len(i) for i in D1]
S=min(3*max(L),K)

for i in range(N):
    ans=-float('inf')
    ans1=0
    now=P[i]-1
    for j in range(S):
        ans1+=C[now]
        now=P[now]-1
        ans=max(ans1,ans)
    Q.append(ans)
    
for i,value in enumerate(D2):
    ans3=value*(K//L[i])
    for j in D1[i]:
        ans=-float('inf')
        ans1=0
        now=P[j]-1
        for k in range(K%L[i]+1):
            ans1+=C[now]
            now=P[now]-1
            ans=max(ans1,ans)
        Q.append(ans3+ans)
print(max(Q))

Submission status: Wrong Answer

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

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

m=0
for a in range(n):
    q=0
    s=a
    h=[s]
    for b in range(k):
        s=p[s]
        if not s in h:
            q+=c[s]
            h.append(s)
            if q>m:
                m=q
            
        else:
            r=0
            cyc=0
            ws=h[-1]
            while ws!=h[-2]:
                ws=p[ws]
                r+=c[ws]
                cyc+=1
            
            r+=c[h[-2]]
            cyc+=1
            if q>m:
                m=q

            i=k-b+1
            q+=r*(i//cyc)
            for d in range(i%cyc):
                s=p[s]
                q+=c[s]
                if q>m:
                    m=q



print(m)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

best = [0 for _ in range(n)]
ans = -1000000000
for i in range(n):
    now = i
    j = 0
    visited = deque()
    score = deque([0])
    isLoop = True
    while now not in visited:
        visited.append(now)
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if j >= k:
            isLoop = False
            break
    # best[i] = max(score)
    ans = max(ans, max(list(score)[1:]))
    if score[-1] > 0:
        loop_num = k//len(score)
        rest = k%len(score)
        # print(list(score)[:rest+2])
        # best[i] = max(best[i], max(list(score)[:rest+2])+loop_num*score[-1] )
        ans = max(ans, max(list(score)[:rest+2])+loop_num*score[-1] )
        # print(loop_num)
        # best[i] = max(best[i], max(list(score))+(loop_num-1)*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )

print(ans)

Submission status: Wrong Answer

Solution code:
# 2020/08/15
# AtCoder Beginner Contest 175 - D

# Input
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
mc = max(c)
p.insert(0,0)
c.insert(0,0)

# Calc
vmax = 0
for i in range(1, n+1):
    pl = [0] * 5002
    idx = i
    val = 0
    jr = min(k, 5001)
    tmpvmax = 0
    for j in range(jr):
#        if pl[idx] == 1:
#            break
#            continue
#        else:
        pl[idx] = 1
        val = val + c[p[idx]]
        tmpvmax = max(val, tmpvmax)
        idx = p[idx]
    vmax = max(vmax, tmpvmax, val)
# Output
print(min(vmax, mc))