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]*N
    flag = [False]*N
    locate = [i for i in range(N)]
    ans = max(C)
    for k in range(31)[::-1]:
        if K&(1<<k)>0:
            for i in range(N):
                if score_doubling[k+1][locate[i]]>0:
                    score[i] += score_doubling[k+1][locate[i]]
                    locate[i] = locat_doubling[k+1][locate[i]]
                else:
                    flag[i] = True
        else:
            for i in range(N):
                if flag[i] and score_doubling[k + 1][locate[i]]>0:
                    score[i] += score_doubling[k + 1][locate[i]]
                    locate[i] = locat_doubling[k + 1][locate[i]]
    for s in score:
        ans = max(ans,s)
    print(ans)
    return

def examE():
    R, C, K = LI()

    ans = 0
    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 = [int(a)-1 for a in input().split()]
C = [int(a) for a in input().split()]
ma = -10 ** 10
for i in range(N):
    l = 1
    j = P[i]
    s = C[j]
    ma = max(ma, s)
    while j != i:
        j = P[j]
        s += C[j]
        l += 1
        ma = max(ma, s)
    
    c = 1
    j = P[j]
    t = C[j]
    if K >= c:
        ma = max(ma, t + (K - c) // l * s)
    
    while j != i:
        j = P[j]
        t += C[j]
        c += 1
        if K >= c:
            ma = max(ma, t + (K - c) // l * s)

print(ma)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if m == 0:
            m = l

        scores += scores[:m]
        scores.insert(0, 0)
        acc = list(accumulate(scores))
        tmp = NINF
        for i in range(l):
            tmp = max(tmp, max(acc[i + 1:i + m + 1]) - acc[i])
        ans = max(ans, tmp, loop * d + tmp)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))

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)
  kk=k-d*len(x)
  anss=-10**20
  s=x[0]
  anss=max(anss,s)
  for i in x[1:kk]:
    s+=i
    anss=max(anss,s)
  ans=max(ans,anss,d*sum(x)+s)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

@njit((i8, i8[:], i8[:]), cache=True)
def main(K, P, C):
    N = len(P)
    INF = 1 << 60
    P = P - 1
    best_score = -INF
    for v in range(N):
        w = v
        L = 0
        S = 0
        while True:
            S += C[w]
            L += 1
            w = P[w]
            if v == w:
                break
        score = 0
        w = v
        for n in range(1, L + 1):
            # はじめに n 個とったあと、周期
            score += C[w]
            w = P[w]
            if n > K:
                break
            max_add = (K - n) // L
            x = score + S * max(0, max_add)
            best_score = max(best_score, x)
    return best_score

N, K = map(int, readline().split())
P = np.array(readline().split(), np.int64)
C = np.array(readline().split(), np.int64)

print(main(K, P, C))

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)
            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:
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
        if sum(A) > 0:
            anb += sum(A) * (k//len(A))
            k %= len(A)
        A += A
        S = [A[0]]
        # print(an,k)
        for i in range(1,len(A)):
            S.append(S[-1]+A[i])
        # print(S)
        
        for i in range(len(S)):
            for j in range(i+1, min(i+k+1,len(S))):
                an = max(an,S[j]-S[i])

        ans = max(an+anb,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(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))
D = [-1]*n
ans = -float("inf")
for i, p in enumerate(P):
    ans = max(ans, C[p])
    temp = p
    res = C[p]
    cnt = 1
    while temp != i and cnt < k:
        temp = P[temp]
        res += C[temp]
        cnt += 1
        ans = max(ans, res)
    D[i] = (cnt, res)
for i in range(n):
    a, b = D[i]
    ans = max(ans, b)
    if a == k:
        continue
    if b < 0:
        continue
    temp = b * (k//a)
    rest = k%a
    now = i
    for _ in range(rest):
        now = P[now]
        temp += C[now]
        ans = max(ans, temp)
print(ans)

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 = max(c)
if(ans <= 0):
    print(ans)
    exit()

for i in range(n):
    now = i
    score = [0]
    while(p[now] != i ):
        now = p[now]
        score.append(score[-1] + c[now])
    cyc_score = score[-1] + c[i]
    cyc = len(score)

    tmp = max(score[:(k%cyc) + 1])
    tmp += max(0,cyc_score) * (k//cyc)
    ans = max(ans,tmp)
print(ans)

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]*N
    locate = [i for i in range(N)]
    ans = max(C)
    for k in range(31):
        if K&(1<<k)>0:
            for i in range(N):
                score[i] += score_doubling[k+1][locate[i]]
                locate[i] = locat_doubling[k+1][locate[i]]
    for s in score:
        ans = max(ans,s)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    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 = [int(a)-1 for a in input().split()]
C = [int(a) for a in input().split()]
ma = -10 ** 10
for i in range(N):
    l = 1
    j = P[i]
    s = C[j]
    ma = max(ma, s)
    while j != i:
        j = P[j]
        s += C[j]
        l += 1
        ma = max(ma, s)
    
    c = 1
    j = P[j]
    t = C[j]
    ma = max(ma, t + (K - c) // l * s)
    
    while j != i:
        j = P[j]
        t += C[j]
        c += 1
        ma = max(ma, t + (K - c) // l * s)

print(ma)

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 = scores[-1] * (K // len(scores)) + max(scores[: K % len(scores)], 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(lambda x: int(x) - 1,input().split()))
c = list(map(int,input().split()))
res = max(c)

def solve(d):
    ret = res
    sz = len(d)
    for i in range(sz):     # iから
        tmp = 0
        for j in range(min(k, sz)):
            tmp += d[(i + j) % sz]
            ret = max(ret, tmp)
    sm = sum(d)
    a,b = divmod(k, sz)
    if a > 0:
        ret = max(ret, a * sm)
        for i in range(sz):
            tmp = 0
            for j in range(b):
                tmp += d[(i + j) % sz]
                ret = max(ret, a * sm + tmp)
    return ret

done = [False for _ in range(n)]
for i in range(n):
    if done[i]:
        continue
    d = []
    cur = i
    while 1:
        done[cur] = True
        d.append(c[cur])
        cur = p[cur]
        if cur == i:
            break
    res = max(res, solve(d))

print(res)

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:
    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
    ans = max(ans, max(b))

    for i in range(n):
        i = a[i]
        co = b[i]
        for _ in range(n):
            i = p[i]
            co += c[i]
            ans = max(ans, co)


print(ans)

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()))
res = [0] * N
for i in range(N):
  x = p[i] - 1
  score = c[x]
  loopscore = c[x]
  loop = 1
  while x != i:
    loop += 1
    x = p[x] - 1
    loopscore += c[x]
    if loop <= K: score = max(score, 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

print(max(res))

Submission status: Wrong Answer

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


def solve(v):
    pos = [v]
    res = []
    set_ = set()
    tot = 0
    while True:
        nxt_v = p[v] - 1
        cost = c[nxt_v]
        if nxt_v not in set_:
            pos.append(nxt_v)
            set_.add(nxt_v)
            v = nxt_v
            tot += cost
            res.append(tot)
        else:
            break
    return pos, res, tot


ans = -INF
for v in range(n):
    pos, res, tot = solve(v)
    if tot <= 0:
        for i in range(min(k, len(res))):
            ans = max(res[i], ans)
    else:
        lap, rem = divmod(k, len(res))
        tmp = lap * tot
        if lap > 0:
            ans = max(ans, tmp)
        for i in range(min(rem, len(res))):
            ans = max(tmp + res[i], ans)
print(ans)

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()))
res = max(c)

def solve(d):
    ret = res
    sz = len(d)
    for i in range(sz):     # iから
        tmp = 0
        for j in range(min(k, sz)):
            tmp += d[(i + j) % sz]
            ret = max(ret, tmp)
    sm = sum(d)
    a,b = divmod(k, sz)
    for i in range(sz):
        tmp = 0
        for j in range(b):
            tmp += d[(i + j) % sz]
            ret = max(ret, a * sm + tmp)
    return ret

done = [False for _ in range(n)]
for i in range(n):
    if done[i]:
        continue
    d = []
    cur = i
    while 1:
        done[cur] = True
        d.append(c[cur])
        cur = p[cur]
        if cur == i:
            break
    res = max(res, solve(d))

print(res)

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()))
D = [-1]*n
ans = -float("inf")
for i, p in enumerate(P):
    ans = max(ans, C[p])
    if C[p] < 0:
        continue
    temp = p
    res = C[p]
    cnt = 1
    while temp != i and cnt < k:
        temp = P[temp]
        res += C[temp]
        cnt += 1
        ans = max(ans, res)
    D[i] = (cnt, res)
for i in range(n):
    if D[i] == -1:
        continue
    a, b = D[i]
    if a == k:
        continue
    if b < 0:
        continue
    temp = b * (k//a)
    rest = k%a
    now = i
    for _ in range(rest):
        now = P[now]
        temp += C[now]
        ans = max(ans, temp)
print(ans)

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
            score += score * loop
            rem -= loop * cnt
            for j in range(rem + 1):
                st = score + score_dict[j]
                ans = max(ans, st)

    print(ans)


if __name__ == '__main__':
    main()

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)

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
ans = max(ans, max(b))


print(ans)

Submission status: Wrong Answer

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

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

    print(ma)




    return None

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()))
for i in range(N):
  P[i]-=1
INF=-(10**20)
X=[[INF]*(N+1) for i in range(N)]
Y=[0]*N
Z=[0]*N
R=[0]*N
S=set()
V=0
for i in range(N):
  S=set()
  V=i
  S.add(i)
  for j in range(N):
    V=P[V]
    if V in S:
      Z[i]=V
      break
  X[i][0]=0
  for j in range(N):
    Y[i]+=1
    V=P[V]
    X[i][j+1]=X[i][j]+C[V]
    if Z[i]==V:
      R[i]=X[i][j+1]
      break
A=INF
Q=0
T=0
U=0
for i in range(N):
  if R[i]<=0:
    for j in range(1,min(N,K)+1):
      A=max(A,X[i][j])
  else:
    Q=R[i]*max((K//Y[i])-1,0)
    T=0
    U=INF
    V=i
    for j in range(min((K%Y[i])+Y[i],K)):
      V=P[V]
      T+=C[V]
      U=max(T,U)
    Q+=T
    A=max(A,Q)
print(A)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, k = na()
f = na()
c = na()

for i in range(n):
    f[i] -= 1

def mx(a, inf, sup):
    n = len(a)
    b = a + a
    ret = -1000000009 if inf > 0 else 0
    for i in range(n):
        s = 0
        for j in range(sup):
            s += b[i+j]
            if j >= inf-1:
                ret = max(ret, s)
    return ret

done = [False] * n
ans = -1000000007
for i in range(n):
    if not done[i]:
        a = []
        cur = i
        while not done[cur]:
            done[cur] = True
            a.append(c[cur])
            cur = f[cur]
        s = sum(a)
        need = k
        if need >= len(a):
            if s >= 0:
                can = need//len(a)*s + mx(a, 0, need % len(a))
                if need > 1:
                    can = max(can, (need//len(a)-1)*s + mx(a, 0, len(a)))
                else:
                    can = max(can, mx(a, 1, len(a)))
            else:
                can = mx(a, 1, len(a))
        else:
            can = mx(a, 1, need+1)
        ans = max(ans, can)

print(ans)

Submission status: Wrong Answer

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

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

    print(ma)




    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    p = LI()
    for i in range(n):
        p[i] -= 1
    c = LI()
    bfs = [0]*n
    lis = []
    for i in range(n):
        if not bfs[i]:
            bfs[i] = 1
            x = i
            path = [c[x]]
            while 1:
                x = p[x]
                if bfs[x]:
                    break
                path.append(c[x])
                bfs[x] = 1
            lis.append([0]+list(accumulate(path*2)))
    ans = -float("inf")
    for path in lis:
        n = len(path) >> 1
        m = k//n
        s = m*path[n]
        if s < 0:
            s = 0
            res = n
        else:
            res = k-m*n
        for l in range(n):
            for j in range(1,res+1):
                ns = s+path[l+j]-path[l]
                if ans < ns:
                    ans = ns
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [int(a)-1 for a in input().split()]
C = [int(a) for a in input().split()]
ma = -10 ** 10
for i in range(N):
    l = 1
    j = P[i]
    s = C[j]
    ma = max(ma, s)
    while j != i:
        j = P[j]
        s += C[j]
        l += 1
        ma = max(ma, s)
    
    c = 1
    j = P[j]
    t = C[j]
    ma = max(ma, t + s * (K - c) // l)
    while j != i:
        j = P[j]
        t += C[j]
        c += 1
        ma = max(ma, t + s * (K - c) // l)

print(ma)

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")
for i in range(n):
    if seen[i]:
        continue
    v = []
    s = i
    while True:
        s = p[s]
        v.append(c[s])
        if s==i:
            break
    v.sort(reverse=True)
    ss =sum(v)
    val = -float("inf")
    if ss>=1:
        val = ss*(k//len(v))
        for i in range(k%len(v)):
            if v[i]<0:
                break
            val += v[i]
    val2 = 0
    if v[0]<0:
        val2 = v[0]
    else:
        for i in range(len(v)):
            if v[i]<0:
                break
            val2 += v[i]
    
    val = max(val, val2)
#     print(val, v, k)
    ans = max(ans, val)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    permu = list(map(int, input().split()))
    points = list(map(int, input().split()))
    max_score = -10**10
    for i in range(n):
        temp = i #スタートマス
        score = [0]
        for j in range(k):
            temp = permu[temp - 1]
            score.append(score[j] + points[temp - 1])
        if(max(score[1:]) > max_score):
            max_score = max(score[1:])
    print(max_score)
if __name__ == '__main__':
    main()