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:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    N, K = mis()
    P = list(map(lambda x: x-1, mis()))
    C = lmis()
    ans = -INF
    for i in range(N):
        p = i
        tmp_score = 0
        k = K
        cycle = 0
        while k:
            p = P[p]
            tmp_score += C[p]
            ans = max(ans, tmp_score)
            k -= 1
            cycle += 1
            if p==i:
                if tmp_score < 0:
                    break
                elif k > cycle*10:
                    skip_loop = (k - cycle)//cycle
                    tmp_score *= skip_loop
                    k -= skip_loop * cycle
        ans = max(ans, tmp_score)
    print(ans)








main()

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

check_list = [0] * (N + 1)

ans = min(C)


def search_max(p_list, n):
    result = min(p_list)
    point_list = p_list[:] + p_list[:]
    for j in range(0, len(p_list)):
        total = 0
        for k in range(j, j + n):
            total += point_list[k]
            if total > result:
                result = total
    return result


for i in range(1, N + 1):
    if check_list[i] == 0:
        buf = i
        p = 0
        point = []

        while check_list[buf] == 0:
            check_list[buf] = 1
            buf = P[buf]
            p += C[buf]
            point.append(C[buf])

        len_p = len(point)
        division, mod = divmod(K, len_p)

        if p > 0:
            if len_p <= K:
                max_p_total = search_max(point, mod)
            else:
                max_p_total = search_max(point, K)
            point_buf = p * division + max_p_total
        else:
            if len_p <= K:
                max_p_total = search_max(point, len_p)
            else:
                max_p_total = search_max(point, K)
            point_buf = max_p_total

        if ans < point_buf:
            ans = point_buf

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

check_list = [0] * (N + 1)

ans = min(C)


def search_max(p_list, n):
    result = min(p_list)
    point_list = p_list[:] + p_list[:]
    for j in range(0, len(p_list)):
        total = 0
        for k in range(j, j + n):
            total += point_list[k]
            if total > result:
                result = total
    return result


for i in range(1, N + 1):
    if check_list[i] == 0:
        buf = i
        p = 0
        point = []

        while check_list[buf] == 0:
            check_list[buf] = 1
            buf = P[buf]
            p += C[buf]
            point.append(C[buf])

        len_p = len(point)
        division, mod = divmod(K, len_p)

        if len_p <= K:
            max_p_total = search_max(point, len_p)
        else:
            max_p_total = search_max(point, K)

        if p > 0:
            max_p_total = search_max(point, mod)
            point_buf = p * division + max_p_total
        else:
            point_buf = max_p_total

        if ans < point_buf:
            ans = point_buf

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

check_list = [0] * (N + 1)

ans = min(C)


def search_max(p_list, n):
    result = min(p_list)
    point_list = p_list[:] + p_list[:]
    for j in range(0, len(p_list)):
        total = 0
        for k in range(j, j + n):
            total += point_list[k]
            if total > result:
                result = total
    return result


for i in range(1, N + 1):
    if check_list[i] == 0:
        buf = i
        p = 0
        point = []

        while check_list[buf] == 0:
            check_list[buf] = 1
            buf = P[buf]
            p += C[buf]
            point.append(C[buf])

        len_p = len(point)
        division, mod = divmod(K, len_p)

        if p > 0:
            max_p_total = search_max(point, mod)
            point_buf = p * division + max_p_total
        else:
            if len_p <= K:
                max_p_total = search_max(point, len_p)
            else:
                max_p_total = search_max(point, K)
            point_buf = max_p_total

        if ans < point_buf:
            ans = point_buf

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

for i in range(n):
  P[i] -= 1
  
ans = -float('inf')

for i in range(n):
  
  cycle = 1
  next_v = P[i]
  cycle_sum = C[next_v]
  
  while next_v != i:
    cycle += 1
    next_v = P[next_v]
    cycle_sum += C[next_v]

  score = max(0, cycle_sum*(k//cycle))
  
  l = k - cycle*(k//cycle)
  if l == 0:
    l += cycle
    score = max(0, cycle_sum*((k//cycle)-1))
    
  r_score = 0
  r_max = -float('inf')
  next_v = P[i]
  
  for j in range(l):
    r_score += C[next_v]
    next_v = P[next_v]
    r_max = max(r_max, r_score)
    
  score += r_max
  ans = max(ans, score)
    
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
  ans = -float('inf')
  N, K = map(int, input().split())
  P = list(map(lambda x:int(x)-1, input().split()))
  C = list(map(int, input().split()))
  for i in range(N):
    score = 0
    now = i
    visited = [-1]*N
    scores = [0]*N
    visited[now] = 0
    for j in range(1,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
      if visited[now]>=0:
        cyc = j - visited[now]
        up = score - scores[now]
        break
      scores[now] = score
      visited[now] = j
    else:
      continue
    if up<=0:
      continue
    score += (K-j)//cyc * up
    ans = max(ans, score)
    cnt = j + (K-j)//cyc*cyc + 1
    for j in range(cnt,K+1):
      now = P[now]
      score += C[now]
      ans = max(ans, score)
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
N,K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

ans = 0
for i in range(1,N + 1):
    j = i
    k = 0
    S = 0
    T = 0
    L = 0
    while True:
        j = P[j - 1]
        S += C[j - 1]
        if T < S:
            k = j
        T = max(T, S)
        L += 1
        if j == i:
            break 
    if K <= L or S <= 0:
        ans = max(ans, T)
    else:
        e = (K - k + 1) // L
        ans = max(ans, T + e * S)

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()))
p.insert(0, 0)
c.insert(0, 0)
visit = [0] * (n + 1)
cyclelist = []
for i in range(1, n + 1):
    if visit[i] == 0:
        a = [c[i]]
        visit[i] = 1
        while visit[p[i]] == 0:
            i = p[i]
            visit[i] = 1
            a.append(c[i])
        cyclelist.append(a)
ans = -1145141919810
for cycle in cyclelist:
    s = sum(cycle)
    l = len(cycle)
    a, b = 0, -1145141919810
    if l == 1:
        if s > 0:
            ans = max(ans, s * k)
        else:
            ans = max(ans, s)
    else:
        if l < k and s > 0:
            a = s * (k // l)
        now = 0
        x = k % l
        if x == 0:
            x = l
        for i in range(min(k, l)):
            now += cycle[i]
            for j in range(l):
                now += cycle[(i + j + 1) % l] - cycle[j]
                if i < x:
                    ans = max(ans, a + now)
                else:
                    ans = max(ans, now)
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()))
p.insert(0, 0)
c.insert(0, 0)
visit = [0] * (n + 1)
cyclelist = []
for i in range(1, n + 1):
    if visit[i] == 0:
        a = [c[i]]
        visit[i] = 1
        while visit[p[i]] == 0:
            i = p[i]
            visit[i] = 1
            a.append(c[i])
        cyclelist.append(a)
ans = -1145141919810
for cycle in cyclelist:
    s = sum(cycle)
    l = len(cycle)
    a, b = 0, -1145141919810
    if l < k and s > 0:
        a = s * (k // l)
    now = 0
    x = k % l
    if x == 0:
        x = l
    for i in range(min(k, l)):
        now += cycle[i]
        for j in range(l):
            now += cycle[(i + j + 1) % l] - cycle[j]
            if i < x:
                ans = max(ans, a + now)
            else:
                ans = max(ans, now)
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()))
p.insert(0, 0)
c.insert(0, 0)
visit = [0] * (n + 1)
cyclecnt = 0
cyclelist = []
for i in range(1, n + 1):
    if visit[i] == 0:
        cyclecnt += 1
        a = [c[i]]
        visit[i] = 1
        while visit[p[i]] == 0:
            i = p[i]
            visit[i] = 1
            a.append(c[i])
        cyclelist.append(a)
ans = -1145141919810
for cycle in cyclelist:
    s = sum(cycle)
    l = len(cycle)
    a, b = 0, -1145141919810
    if l < k and s > 0:
        a = s * (k // l)
    now = 0
    for i in range(k % l if not k % l == 0 else l):
        now += cycle[i]
        for j in range(l):
            now += cycle[(i + j + 1) % l] - cycle[j]
            b = max(b, now)
    ans = max(ans, a + b)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j]
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] > 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur])
            cnt %= f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j]
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur])
            cnt %= f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [-float('inf')] * N
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j] - 1
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] > 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur])
            cnt %= f_cnt[cur]
            ret = ret_
        else:
            cnt = f_cnt[cur]

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur] - 1
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [-float('inf')] * N
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j] - 1
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] > 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur])
            cnt %= f_cnt[cur]
        else:
            cnt = f_cnt[cur]

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur] - 1
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
    sp=P[i]
    r=C[sp]
    L=[r]
    np=P[sp]
    while True:
        r+=C[np]
        L.append(r)
        np=P[np]
        if np==sp:
            break
    c=len(L)
    if c>=k:
        ANS=max(ANS,max(L))
    else:
        SL=L[-1]
        m=k//c
        y=k%c
        if SL<=0:
            ANS=max(ANS,max(L))
        else:
            if y==0:
                ANS=max(ANS,(m-1)*SL+max(L))
            else:
                ANS=max(ANS,m*SL+max(L[:y]))
print(ANS)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x) for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = [-float('inf')] * N
    def f(cur, cnt):
        f_cnt = [0] * N
        f_score = [0] * N
        ret = -float('inf')
        ret_ = 0
        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            if f_cnt[cur] and f_cnt[cur] - cnt <= cnt:
                if ret_ < f_score[cur]:
                    break
                ret_ += (cnt // (f_cnt[cur] - cnt)) * (ret_ - f_score[cur])
                cnt %= (f_cnt[cur] - cnt)
                ret = max(ret, ret_)
                continue

            f_cnt[cur] = cnt
            f_score[cur] = ret_
            cur = P[cur] - 1
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans[i] = f(i, K)
    
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
it = lambda: list(map(int, input().strip().split()))


def get(K, cycle):
    L = len(cycle)
    T = sum(cycle)

    if K > L:
        B = (K - 1) // L
        R = K - B * L
    else:
        B = 0
        R = K
        
    assert R <= L
    cur = 0
    ans = max(cycle)
    queue = deque([0])
    dp = [0] * (2 * L + 1)
    for i, num in enumerate(cycle + cycle):
        j = i + 1
        cur += num
        while queue and j - queue[0] > R:
            queue.popleft()
        if queue:
            ans = max(ans, cur - dp[queue[0]])
        while queue and dp[queue[-1]] >= cur:
            queue.pop()
        dp[j] = cur
        queue.append(j)
    
    return ans + max(0, B * T)


def solve():
    # square labelled from 1 to N
    N, K = it()
    P = it()
    C = it()

    for i in range(N):
        P[i] -= 1

    cycles = []
    seen = [False] * N
    for i in range(N):
        if not seen[i]:
            cycle = []
            first = curr = i
            while True:
                seen[curr] = True
                cycle.append(C[curr])
                curr = P[curr]
                if curr == first:
                    break
            cycles.append(cycle)
    
    # print(cycles)

    ans = float('-inf')
    for cycle in cycles:
        ans = max(ans, get(K, cycle))
    return ans


if __name__ == '__main__':
    ans = solve()
    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()))

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**20

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)):
            for j in range(len(li)):
                if k >= cnt:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**20

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)):
            for j in range(len(li)):
                if (cnt != 0 or j != 0) and k >= cnt:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**18

for i,li in enumerate(roop):
    t = -10**18
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)):
            for j in range(len(li)):
                if (cnt != 0 or j != 0) and k >= cnt:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**18

for i,li in enumerate(roop):
    t = -10**18
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for cnt in range(min(len(li), k)):
            for j in range(len(li)):
                if cnt != 0 and j != 0:
                    t = max(t, s2[i][cnt+j] - s2[i][j] + s[i] * ((k - cnt) // len(li)))
        ans = max(ans, t)

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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**18

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + len(li)):
                if k - (k1 - j) >= 0:
                    t = max(t, s2[i][k1] - s2[i][j] + s[i] * (k - (k1 - j)) // len(li))
        ans = max(ans, t)


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

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

v = [False] * n
roop = []

for i in range(n):
    if not v[i]:
        tmp = [i]
        while True:
            t = p[tmp[-1]]
            v[t] = True
            if tmp[0] == t:
                break
            else:
                tmp.append(t)
        roop.append(tmp)

s = []

for li in roop:
    s1 = 0
    for i in li:
        s1 += c[i]
    s.append(s1)

s2 = []

for li in roop:
    tmp = [0]
    for i in li:
        tmp.append(tmp[-1] + c[i])
    for i in li:
        tmp.append(tmp[-1] + c[i])
    s2.append(tmp)

v2 = [-1] * n

for i,li in enumerate(roop):
    for j in li:
        v2[j] = i

ans = -10**18

for i,li in enumerate(roop):
    t = -10**20
    if s[i] <= 0:
        for j in range(len(li)):
            for k1 in range(j+1, j + 1 + min(k, len(li))):
                t = max(t, s2[i][k1] - s2[i][j])
        ans = max(ans, t)
    else:
        cnt = k // len(li)
        if cnt == 0:
            for j in range(len(li)):
                for k1 in range(j+1, j + 1 + min(k, len(li))):
                    t = max(t, s2[i][k1] - s2[i][j])
                    print(j,k1,s2[i][k1] - s2[i][j])
            ans = min(ans, t)
        else:
            for j in range(len(li)):
                for k1 in range(j+1, j + 1 + len(li)):
                    t = max(t, s2[i][k1] - s2[i][j] + s[i] * (k - (k1 - j)) // len(li))
            ans = max(ans, t)

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 = -10**10
def cycle(k):
    mo=k
    clen=0
    cscore=0
    flg = True
    cmax=[-10**10]
    while (mo != k or flg):
        clen+=1
        cscore+=c[mo]
        mo = p[mo]
        cmax.append(max(cmax[-1],cscore))
        if mo == k:
            flg = False
    if cscore<0:
        return cmax[min(K-1,clen-1)],cmax
    return cscore*((K-1)//clen)+cmax[(K-1)%clen+1],cmax
for i in range(n):
    a,l=cycle(i)
    if a>ans:
        ans = a
print(ans)