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:
def examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return

def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i,p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0]*N for _ in range(31)]
    score_doubling = [[0]*N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2,31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
            score_doubling[k][i] = score_doubling[k-1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[0,-inf] for i in range(N)]
    locate = [[i,i] for i in range(N)]
    ans = max(C)

    if ans<0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            if score[i][1]<0:
                continue
            #print(score[i],locate[i])
            if score_doubling[k + 1][locate[i][1]]>0:
                score[i][1] += score_doubling[k + 1][locate[i][1]]
                locate[i][1] = locat_doubling[k+1][locate[i][1]]
            if score[i][1] < score[i][0]:
                score[i][1] = score[i][0]
                locate[i][1] = locate[i][0]

        if K&(1<<k)>0:
            for i in range(N):
                score[i][0] += score_doubling[k+1][locate[i][0]]
                locate[i][0] = locat_doubling[k+1][locate[i][0]]
    for s in score:
        ans = max(ans,s[0],s[1])
    print(ans)
    return

def examE():
    R, C, K = LI()
    V = [[-inf]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = LI()
        V[r-1][c-1] = v
    dp0 = [[0]*(C+1) for _ in range(R+1)]
    dp1 = [[0]*(C+1) for _ in range(R+1)]
    dp2 = [[0]*(C+1) for _ in range(R+1)]
    dp3 = [[0]*(C+1) for _ in range(R+1)]

    for r in range(R):
        for c in range(C):
            v = V[r][c]
            if 0<v:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = max(dp1[r+1][c],dp0[r+1][c]+v,dp0[r][c+1]+v,dp1[r][c+1]+v,dp2[r][c+1]+v,dp3[r][c+1]+v)
                dp2[r+1][c+1] = max(dp2[r+1][c],dp1[r+1][c]+v)
                dp3[r+1][c+1] = max(dp3[r+1][c],dp2[r+1][c]+v)
            else:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = dp1[r+1][c]
                dp2[r+1][c+1] = dp2[r+1][c]
                dp3[r+1][c+1] = dp3[r+1][c]

    ans = max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C])
    print(ans)
    return

def examF():

    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
raw = []
seen = [0 for _ in range(n)]
for i in range(n):
  now = int(i)
  tmp = []
  if seen[i]:
    continue
  while seen[now] == 0:
    tmp.append(c[now])
    seen[now] = 1
    now = p[now] - 1
  raw.append(tmp)
#print(raw)
can = 0
for x in raw:
  sun = sum(x)
  l = len(x)
  x += x
  x += x
  #print(x)
  now = [0]
  for y in x:
    now.append(now[-1]+y)
  #print(now)
  if sun > 0 and k >= l:
    ans = sun* (k//l-1)
    k = k % l + l
    #print(ans,k)
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          #print(now[j]-now[i],j-i,bool(268==now[j]-now[i]))
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    #print('#',maxi)
    #print('#',sun)
    #print(k)
    can = max(ans+maxi,can)
    #print(maxi)
    #print(ans+maxi)
  else:
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    can = max(maxi,can)
if can == 0:
  print(max(c))
else:
  print(can)

Submission status: Wrong Answer

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 = max(c[1:])
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))
        ans = max(ans, cur_sum)
        k = K % 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: Wrong Answer

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:
        ans = max(ans, i_s_score_max)
        temp = i_s_score*(k//move_num)
        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: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
used = [0]*n
c = list(map(int,input().split()))
ans = -float("INF")
def calc(x):
    d = {}
    l = []
    now = x
    count = 0
    score = 0
    while used[now] == 0:
        used[now] = 1
        l.append(c[now])
        d[now] = count
        count += 1
        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 = -float("INF")
        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 = le
        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: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
maxlis = []
for start in range(1,n+1):
    point = 0
    p_lis =[]
    now = start
    for i in range(n):
        next = p[now-1]
        point += c[next-1]
        p_lis.append(point)
        now = next
    print(p_lis)
    if k >= n:
        if k%n == 0:
            pre_max = max(p_lis[-1]*(k//n),max(p_lis),p_lis[-1]*(k//n))
        else:
            pre_max = max(p_lis[-1]*(k//n)+max(p_lis[0:k%n]),max(p_lis),p_lis[-1]*(k//n))
    else:
        pre_max = max(p_lis[0:k%n+1])
    print(pre_max)
    maxlis.append(pre_max)
print(max(maxlis))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#from itertools import accumulate
#from itertools import combinations
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

#N,K = 3,6
#P = [2,3,1]
#C = [-10,10,1]

visited = [False]*(N+1)
loops = []
for v in range(1,N+1):
    if visited[v]:
        continue
    l = [v]
    while True:
        v = l[-1]
        visited[v] = True
        nv = P[v-1]
        if visited[nv]:
            break
        l.append(nv)
    loops.append(l)

cand = []
for loop in loops:
    temp = 0
    vals = [C[i-1] for i in loop]
    l = len(vals)
    vals2 = vals+vals[:-1]
    cumsum = [0]
    for v in vals2:
        cumsum.append(cumsum[-1] + v)
    #cumsum = [0] + list(accumulate(vals2))
    gh = []
    #print(vals)
    if K <= l:
        temp = 0
        for left in range(0,2*l-K):
            for right in range(left+1,left+K+1):
                gh.append(cumsum[right] - cumsum[left])
        if gh:
            temp = max(gh)
    else:
        temp = 0
        s = sum(vals)
        q, r = divmod(K,l)
        if r == 0:
            q -= 1
            r += l
        for left in range(0,2*l-r):
            for right in range(left+1,left+r+1):
                #print(left,right)
                gh.append(cumsum[right] - cumsum[left])
        if gh:
            temp = max(gh)
        if s > 0:
            temp += q * s
    #print(temp)
    cand.append(temp)
if cand:
    print(max(cand))

Submission status: Wrong Answer

Solution code:
input = raw_input

n, k = map(int, input().split(" "))

ps= map(int, input().split(" "))
graph = {}
for i, out in enumerate(ps):
    in_ = i+1
    graph[in_] = out

cs= map(int, input().split(" "))
pos_points = [None] + cs


def f(si):
    points = [None] * (n+1)
    points[si] = 0

    times = [None] * (n+1)
    times[si] = 0

    cur_pos = si
    cur_point = 0
    loop_len = None
    cur_max_point = None
    for cur_time in range(1, k+1):
        next_pos = graph[cur_pos]

        cur_point += pos_points[next_pos]
        cur_max_point = cur_point if cur_time == 1 else max(cur_max_point, cur_point)

        if times[next_pos] is not None:
            loop_len = cur_time - times[next_pos]
            loop_sum_point = cur_point - points[next_pos]
            loop_start_pos = next_pos
            break

        times[next_pos] = cur_time
        points[next_pos] = cur_point

        cur_pos = next_pos

    if loop_len is None:
        return cur_max_point

    if loop_sum_point <= 0:
        return cur_max_point


    loop_points = []
    cur_point = 0
    cur_pos = loop_start_pos
    while True:
        next_pos = graph[cur_pos]
        cur_point += pos_points[next_pos]
        loop_points.append(cur_point)
        if next_pos == loop_start_pos:
            break
        cur_pos = next_pos

    assert loop_sum_point == loop_points[-1]
    loop_made_point = points[loop_start_pos]

    x = k-times[loop_start_pos]
    r = x // loop_len
    q = x % loop_len
    ret = loop_made_point + r * loop_sum_point + (0 if q == 0 else max( loop_points[:q] ) )

    ret = max(cur_max_point, ret)
    return ret



for si in range(1, n+1):
    if si == 1:
        out = f(si)
    else:
        out = max(out, f(si))
print(out)

Submission status: Wrong Answer

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

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

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

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 bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,K = isRaw()
    Ps = isRaw()
    Cs = isRaw()
    ans = -INF
    for n in range(N):
        curPos = n
        cycles =[]
        visited = {}
        lastCost = 0
        vidx = 0
        loopStart = -1
        while True:
            visited[curPos] = vidx
            cycles.append(lastCost+Cs[curPos])
            curPos= Ps[curPos]-1
            lastCost = cycles[-1]
            if curPos in visited:
                loopStart = visited[curPos]
                break
        
        lc = len(cycles)
        divK = K//lc
        score = 0
        cFlag = False
        if divK>=1:
            if cycles[-1]>=0:
                score+=cycles[-1]*divK
                cFlag =True
        if K%lc ==0:
            if cFlag:
                score += max(cycles+[0])
            else:
                score += max(cycles)
        else:
            if cFlag:
                score += max(cycles[:K % lc]+[0])
            else:
                score += max(cycles[:K % lc])
        


        ans = max(score,ans)
    print (ans)

         
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 = -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:
            print(cur, move_num)
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        ans = max(ans, i_s_score_max)
        temp = i_s_score*(k//move_num)
        rest = k%move_num
        print(rest)
        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: Wrong Answer

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

table=[0]*N
ans=-float("INF")
for i in range(N):
    L=[]
    count=0
    score=0
    max_score=-float("INF")
    now=i+1
    while count<K:
        now=P[now-1]
        add=C[now-1]
        score+=add
        max_score=max(score, max_score)
        L.append(add)
        count+=1
        if now==i+1:
            break
    #print("score", max_score)
    if sum(L)>0:
        max_score=sum(L)*((K-count)//count)
        res=count+K%count
        score=max_score
        #print("max_score", max_score)
        #print("res", res)
        while res>0:
            now=P[now-1]
            add=C[now-1]
            score+=add
            max_score=max(score, max_score)
            res-=1
            
        
    
    #idx=(K-count)%len(L)
    #if idx!=0:
    #    score+=L[idx-1]
    #print("max_score", max_score)
    ans=max(ans, max_score)
    
print(ans)

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):
    if num==0:
        return 0
    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 and k>=len(v):
        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,min(k,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 math


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


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


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

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


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

Submission status: Wrong Answer

Solution code:
import copy
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    P=LIST()
    C=LIST()
    lp=[]
    sc=[]
    check=[False]*n
    ans=-(10**9+1)
    le=0
    for i in range(n):
        #print(i)
        tl=[]
        tc=[]
        if check[i]==False:
            templ=P[i]-1
            tempc=C[i]
            check[i]=True
            while not(templ in tl):
                check[templ]=True
                tl.append(templ)
                tc.append(tempc)
                tempc=C[templ]
                templ=P[templ]-1
                
        else:
            continue
        lp.append(tl)
        sc.append(tc)
    
    l=len(lp)
    for i in range(l):
        loop=lp[i]
        score=sc[i]
        cycle=sum(score)
        score=score+score
        #print(lp,score)
        if cycle>=0:
            #flg=1
            remain = k %len(loop)
            cym=0
            for j in range(len(loop)):
                if score[j]<=0:
                    continue
                for ii in range(remain):
                    cym=max(sum(score[j:j+ii+1]),cym)
            ans=max(k//len(loop)*cycle+cym,ans)
        else:
            remain = k %len(loop)
            #flg=2
            cym=-(10**9+1)
            for j in range(len(loop)):
                if score[j]<=0:
                    continue
                for ii in range(remain):
                    cym=max(sum(score[j:j+ii+1]),cym)
            ans=max(cym,ans)
            
        #print(ans)
    
    if ans==0:
        ans=max(C)
    print(ans)
    
    
if __name__ == '__main__':
    do()

Submission status: Wrong Answer

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

score=[[0]*N]*N
ans=min(C)

for i in range(N):
  cnt=1
  index=i
  for j in range(K):
    index=P[index]-1
    score[i][j]=C[index]
    if cnt>1 and i==index:
      ans=max(ans,max(max(score[i]),sum(score[i])*(K//cnt)+sum(score[i][:K%cnt])))
      break
    cnt+=1
  else:
    ans=max(ans,max(score[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()))
ans=-10**18
for i in range(1,n+1):
  vis=set()
  now=i
  a=[0]
  m=k
  while m:
    vis.add(now)
    now=p[now]
    a+=[c[now]+a[-1]]
    m-=1
    if now in vis:break
  if m==0 or a[-1]<=0:
    cnt=max(a[1:])
  else:
    cnt=k//(k-m)*a[-1]
    if k%(k-m):cnt+=max(a[1:k%(k-m)+1])
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [int(p) - 1 for p in input().split()]
C = list(map(int, input().split()))

max_score = -10 ** 9
for i in range(N):
    memo = {P[i]}
    score = C[P[i]]
    cur = P[i]
    move = 1
    max_score = max(score, max_score)

    while move < K and P[cur] not in memo:
        cur = P[cur]
        memo.add(cur)
        score += C[cur]
        move += 1
        max_score = max(score, max_score)

    if move < K and score > 0:
        score = (K // move) * score
        move *= (K // move)
        max_score = max(score, max_score)

        cur = i
        while move < K:
            cur = P[cur]
            score += C[cur]
            move += 1
            max_score = max(score, max_score)

print(max_score)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p_lis = list(map(int, input().split()))
score_lis = list(map(int, input().split()))

visited = [False]*n
# same_group = [False]*n

ans = -10**9


for start in range(n):
    visited = [False]*n
    point_tmp = 0
    visited[start] = True
    # same_group[start] = True
    tmp = start

    for i in range(k):
        tmp = p_lis[tmp-1]
        point_tmp += score_lis[tmp-1]
        visited[tmp-1] = True
        # same_group[tmp-1] = True
        
        if point_tmp > ans:
            ans = point_tmp

        # ループ
        if tmp == start-1:
            if point_tmp > 0:
                p_cycle = point_tmp
                l = visited.count(True)
                t = k//l
                amari = k%l
                point_tmp = 0
                tmp = start
                for j in range(n):
                    tmp = p_lis[tmp-1]
                    point_tmp += score_lis[tmp-1]

                    if j+1 <= amari:
                        ans = max(ans, point_tmp+p_cycle*(t))
                    else:
                        ans = max(ans, point_tmp+p_cycle*(t-1))
            break

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()))
ans = 0
for j in range(n):
    score = 0
    next_i =  j
    for i in range(k):
        next_i =  p[next_i]  - 1
        score += c[next_i]
        if score > ans:
            ans = score
print(ans)

Submission status: Wrong Answer

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 = -50**13
for cc in CC:
    cca = list(accumulate(cc))
    sc = sum(cc)
    if k < len(cc):
        ans = max(ans, max(cca[:k]))
        continue
    if sc <= 0:
        # 1周分中のmax
        ans = max(ans, max(cca))
        continue
    else:
        kk, r = divmod(k, len(cc))
        if r == 0:
            ans = max(ans, kk*sc)
        else:
            ans = max(ans, kk * sc + max(cca[:r]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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()))
const = sum(C)
max_val = -inf
for i in range(n):
  now = i
  point = 0
  max_point = -inf
  j = k
  data = [[-1]*2 for i in range(n)]
  while j >0:
    j-=1
    now = P[now]
    point += C[now]
    max_point = max(max_point,point)
    if data[now][0] == -1:
      data[now][0] = j
      data[now][1] = point
    else:
      if j == 0:break
      elif point - data[now][1] > 0:
        point += (point - data[now][1]) * ((j-1)//(data[now][0]-j))
        if j % (data[now][0]-j) != 0:j %= (data[now][0]-j)
        else :j == (data[now][0]-j)
      else:
        if j % (data[now][0]-j) != 0:j %= (data[now][0]-j)
        else :j == (data[now][0]-j)
    max_point = max(max_point,point)
    # print(point)

  max_val = max(max_val,max_point)
  # print(max_point,i)
  # print(max_point)
  # print(max_point,point)
print(max_val)
# print(const,max_val,k)
# print(l*const)