Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Wrong Answer

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


def f(c):
    visited = [False]*N

    # 1周のスコア
    cycle = 0
    cscore = 0
    while True:
        if visited[c]:
            break
        visited[c] = True
        cycle += 1
        cscore += C[c]
        c = P[c]

    MP = [C[c]]
    c = P[c]

    Y = K if K % cycle == 0 else K % cycle
    for _ in range(Y-1):
        MP.append(MP[-1]+C[c])
        c = P[c]

    # print(MP)

    if K <= cycle:
        return max(MP)
    else:
        return max(0, cscore)*(K//cycle)+max(MP)


ans = -10**20
for i in range(N):
    ans = max(ans, f(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()))
def func(i):
  max=C[i]
  sum=C[i]
  for j in range(k-1):
    sum+=C[P[i]-1]
    if sum>max:
      max=sum
  return max
ans=func(0)
for i in range(1,n):
  if func(i)>ans:
    ans=func(i)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
p=list(map(int,input().split()))
c=list(map(int,input().split()))
result=-1000000001
pli=[]
cli=[]

for i in range(n):
    if p[i]==0:
        continue
    pli.clear()
    cli.clear()
    pli.append(p[i])
    cli.append(c[i])
    for j in range(n):
        nextp=p[pli[-1]-1]
        if nextp==pli[0]:
#            print("pli",*pli)
#            print("cli",*cli)
#            print("clisum",sum(cli))
            
            for s in range(len(pli)):
                score=0
                for t in range(len(pli)-1):
                    score+=cli[(s+t)%len(pli)]
                    if result<score+int((k-t)%n)*sum(cli)*(sum(cli)>0):
                        result=score+int((k-t)%n)*sum(cli)*(sum(cli)>0)
#                    print(s,t,cli[(s+t)%len(pli)],score,result)
                    
            for k in pli:
                p[k-1]=0
#            print("p",*p)
            break
        cli.append(c[pli[-1]-1])
        pli.append(nextp)
        
print(result)

Submission status: Wrong Answer

Solution code:
import sys

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

r = []

_max = - (sys.maxsize - 1);
for i in range(n):
    currentmax = - (sys.maxsize - 1)
    current = i
    acc = 0
    ca = 0
    costs = []
    x = 0
    while x < k:
        current = p[current] - 1
        if current == i:
            break
        acc += c[current]
        costs.append(acc)
        currentmax = max(currentmax, acc)
        x += 1
    acc += c[current]
    costs.append(acc)

    if x+1 < k:
        r = k // len(costs)
        for j in range(k % len(costs)):
            tmp = costs[-1] * r + costs[j]
            _max = max(_max, currentmax, tmp)
    else:
        _max = max(_max, currentmax)

print(_max)

Submission status: Wrong Answer

Solution code:
from numba import njit,i8
import numpy as np


n,k = map(int,input().split())
p = np.array([int(i)-1 for i in input().split()],np.int64)
c = np.array(list(map(int,input().split())),np.int64)

@njit(i8(i8,i8[:],i8[:]), cache = True)
def calc_score(x,p,c):
    n = p.size
    score = 0
    score_max = -10**10
    score_list = np.zeros(n)
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_max = max(score_max, score)
            score_list[cnt-1] = score
        else:
            return score_max
    
    if score>0:
        if k%cnt>0:
            tmp_max = score_list[:k%cnt].max()
        else:
            tmp_max = 0
        return tmp_max + (k//cnt) * score
    else:
        return score_max

ans = max(calc_score(i,p,c) for i in range(n))
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()))

pos = 0

ans = 0
for i in range(n):
  start = pos = i
  tmp_score = 0
  tmp_score_max = 0
  for j in range(k):
    pos = p[pos-1]
    
    if pos == start:
      if tmp_score <= 0:
        break
      loop_count = k // j
      loop_rest = k % j
      tmp_score *= loop_count
      for j in range(loop_rest):
        tmp_score += c[pos-1]
        if j == 0:
          tmp_score_max = tmp_score
        else:
          tmp_score_max = max(tmp_score_max, tmp_score)
    
    else:
      tmp_score += c[pos-1]
      if j == 0:
        tmp_score_max = tmp_score
      else:
        tmp_score_max = max(tmp_score_max, tmp_score)
        
    if i == 0:
      ans = tmp_score_max
    else:
      ans = max(ans, tmp_score_max)
    
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()))

pos = 0

ans = 0
for i in range(n):
  start = pos = i
  tmp_score = 0
  tmp_score_max = 0
  for j in range(k):
    pos = p[pos-1]
    
    if pos == start:
      if tmp_score <= 0:
        break
      loop_count = k // j
      loop_rest = k % j
      tmp_score *= loop_count
      for j in range(loop_rest):
        tmp_score += c[pos-1]
      if j == 0:
        tmp_score_max = tmp_score
      else:
        tmp_score_max = max(tmp_score_max, tmp_score)
    
    else:
      tmp_score += c[pos-1]
      if j == 0:
        tmp_score_max = tmp_score
      else:
        tmp_score_max = max(tmp_score_max, tmp_score)
    if i == 0:
      ans = tmp_score_max
    else:
      ans = max(ans, tmp_score_max)
    
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()))

score = []
ans = -10 ** 10
o = k // n
z = k % n

for i in range(n):
    score.append(0)
    if k <= n or sum(c) <= 0:
        a = p[i] - 1
        for j in range(k):
            score[i] += c[a]
            a = p[a] - 1
            if score[i] > ans:
                ans = score[i]

if k > n and sum(c) > 0:
    for l in range(n):
        score[l] += sum(c) * o
        print(score[l],sum(c),o)
        b = p[l] - 1
        for m in range(z):
            score[l] += c[b]
            b = p[b] - 1
            if score[l] > ans:
                ans = score[l]
    
    for q in range(n):
        score[q] = sum(c) * (o-1)
        d = p[q] - 1
        for r in range(n):
            score[q] += c[d]
            d = p[d] - 1
            if score[q] > ans:
                ans = score[q]

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()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, K + 1):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(K + 1):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

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()))
dic = {}
for i in range(1, n+1):
  dic[i] = [p[i-1], c[i-1]]
INF = 10**20
ans = -INF
for j in range(1, n+1):
  state = [True] * 5001
  max_score = -INF
  max_idx = 0
  score = 0
  now = dic[j][0]
  cnt = 0
  flg = True
  for _ in range(k):
    if not state[now]:
      flg = False
      break
    score += dic[now][1]
    cnt += 1
    if max_score < score:
      max_score = score
      max_idx = cnt
    state[now] = False
    now = dic[now][0]
  if score <= 0 or flg:
    ans = max(max_score, ans)
  else:
    q = k // cnt
    r = k % cnt
    if r >= max_idx:
      x = score * q + max_score
      ans = max(ans, x)
    else:
      if q >= 1:
        x = score * (q - 1) + max_score
        ans = max(ans, x)
      else:
        ans = max(ans, max_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()))
dic = {}
for i in range(1, n+1):
  dic[i] = [p[i-1], c[i-1]]
INF = 10**20
ans = -INF
for j in range(1, n+1):
  state = [True] * 5001
  max_score = -INF
  max_idx = 0
  score = 0
  now = dic[j][0]
  cnt = 0
  flg = True
  for _ in range(k):
    if not state[now]:
      flg = False
      break
    score += dic[now][1]
    cnt += 1
    if max_score < score:
      max_score = score
      max_idx = cnt
      state[now] = False
    now = dic[now][0]
  if score <= 0 or flg:
    ans = max(max_score, ans)
  else:
    q = k // cnt
    r = k % cnt
    if r >= max_idx:
      x = score * q + max_score
      ans = max(ans, x)
    else:
      if q >= 1:
        x = score * (q - 1) + max_score
        ans = max(ans, x)
      else:
        ans = max(ans, max_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()))
dic = {}
for i in range(1, n+1):
  dic[i] = [p[i-1], c[i-1]]
ans = 0
for j in range(1, n+1):
  state = [True] * 5001
  max_score = 0
  max_idx = 0
  score = 0
  now = dic[j][0]
  cnt = 0
  flg = True
  for _ in range(k):
    if not state[now]:
      flg = False
      break
    score += dic[now][1]
    cnt += 1
    if max_score < score:
      max_score = score
      max_idx = cnt
      state[now] = False
    now = dic[now][0]
  if score <= 0 or flg:
    ans = max(max_score, ans)
  else:
    q = k // cnt
    r = k % cnt
    if r >= max_idx:
      x = score * q + max_score
      ans = max(ans, x)
    else:
      if q >= 1:
        x = score * (q - 1) + max_score
        ans = max(ans, x)
      else:
        ans = max(ans, max_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()))
dic = {}
for i in range(1, n+1):
  dic[i] = [p[i-1], c[i-1]]
ans = 0
for j in range(1, n+1):
  state = [True] * 5001
  max_score = 0
  max_idx = 0
  score = 0
  now = j
  cnt = 0
  flg = True
  for _ in range(k):
    if not state[now]:
      flg = False
      break
    score += dic[now][1]
    cnt += 1
    if max_score < score:
      max_score = score
      max_idx = cnt
    now = dic[now][0]
    state[now] = False
  if score <= 0 or flg:
    ans = max(max_score, ans)
  else:
    q = k // cnt
    r = k % cnt
    if r >= max_idx:
      x = score * q + max_score
      ans = max(ans, x)
    else:
      if q >= 1:
        x = score * (q - 1) + max_score
        ans = max(ans, x)
      else:
        ans = max(ans, max_score)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
# 先頭に0番要素を追加すれば、配列の要素番号と入力pが一致する
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -1e9
#s = [None] * n
# 開始ノードをsi
for si in range(1, n+1):

    # 閉ループのスコアを取り出す
    x = si
    s = list()  # ノードの各スコアを保存
    #s_len = 0
    tot = 0     # ループ1周期のスコア
    while 1:
        x = p[x]
        s.append(c[x])
        #s[s_len] = c[x]
        #s_len += 1
        tot += c[x]
        if (x == si): break # 始点に戻ったら終了
    
    # siを開始とする閉ループのスコア(s)を全探
    s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   # i回移動したときのスコア
        if (i+1 > k): break # 移動回数の上限を超えたら終了
        # 1周期のスコアが正ならば、可能な限り周回する
        if tot > 0:
            e = (k-(i+1))//s_len # 周回数
            now = t + tot*e      # i回移動と周回スコアの合計
        else:
            now = t
        ans = max(ans, now)

print(ans)

Submission status: Wrong Answer

Solution code:

from numba import jit
@jit


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        l = len(c_rev)
        if k <= l:
            ans = max(t_senni[0:k])
        elif t > 0:
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod
            ans = (k // l - 1) * t + t_senni[pn - 1] + mod
        else:
            ans = max(t_senni)

        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

from numba import jit
@jit


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        l = len(c_rev)
        if k <= l:
            ans = max(t_senni[0:l+1])
        elif t > 0 and k > l:
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod
            ans = (k // l - 1) * t + t_senni[pn - 1] + mod
        else:
            ans = max(t_senni)
            
        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

from numba import jit
@jit


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        l = len(c_rev)
        if t > 0:
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod

            ans = (k // l - 1) * t + t_senni[pn - 1] + mod

        else:
            if k >= l:
                ans = max(t_senni)
            else:
                ans = max(t_senni[0:l+1])

        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

from numba import jit
@jit


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        l = len(c_rev)
        if t > 0:
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod

            ans = (k // l - 1) * t + t_senni[pn - 1] + mod

        else:
            if k >= l:
                ans = max(t_senni)
            else:
                ans = max(t_senni[0:k+1])

        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        if t > 0:
            l = len(c_rev)
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod

            ans = (k // l - 1) * t + t_senni[pn - 1] + mod

        else:
            ans = max(t_senni)

        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=[*map(int,input().split())]
c=[*map(int,input().split())]
sp=[]
sc=[]
for i in range(n):
    j=i
    bc=[]
    while not j in sp:
        sp.append(j)
        bc.append(c[p[j]-1])
        j=p[j]-1
    if len(bc)>0: sc.append(bc)
a=-1*(10**8)
for sp in sc:
    for i in range(len(sp)):
        j=i
        v=0
        for _ in range(k%len(sp) if sum(sp)>0 else len(sp)):
            v+=sp[j]
            j+=1
            if j>=len(sp): j=0
            a=max(a,v)
    a=sum(sp)*(k//len(sp))+a if sum(sp)>0 else a
print(a)

Submission status: Wrong Answer

Solution code:


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    f_ans = -float('inf')

    for i in range(n):
        c_rev = []
        t_senni = []
        t = 0
        pi = p1 = p[i]

        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

        while pi != p1:
            c_rev.append(c[pi - 1])
            t += c[pi - 1]
            t_senni.append(t)
            pi = p[pi - 1]

        if t >= 0:
            l = len(c_rev)
            pn = k % l
            c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
            t_mod = 0
            mod = -float('inf')

            for j in range(l):
                t_mod += c_rev_mod[j]
                if mod < t_mod:
                    mod = t_mod

            ans = (k // l - 1) * t + t_senni[pn - 1] + mod

        else:
            ans = max(t_senni)

        if f_ans < ans:
            f_ans = ans

    print(f_ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
f_ans = -float('inf')

for i in range(n):
    c_rev = []
    t_senni = []
    t = 0
    pi = p1 = p[i]

    c_rev.append(c[pi - 1])
    t += c[pi - 1]
    t_senni.append(t)
    pi = p[pi - 1]

    while pi != p1:
        c_rev.append(c[pi - 1])
        t += c[pi - 1]
        t_senni.append(t)
        pi = p[pi - 1]

    if t >= 0:
        l = len(c_rev)
        pn = k % l
        c_rev_mod = c_rev[pn:l] + c_rev[0:pn]
        t_mod = 0
        mod = -float('inf')

        for j in range(l):
            t_mod += c_rev_mod[j]
            if mod < t_mod:
                mod = t_mod

        ans = (k // l - 1) * t + t_senni[pn-1] + mod

    else:
        ans = max(t_senni)

    if f_ans < ans:
        f_ans = ans

print(f_ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
next_map = list(map(int, input().split()))
score_ls = list(map(int, input().split()))
for i in range(n):
    next_map[i] -= 1

def max_of_the_start(start):
    # 同じますにたどり着くまで
    max1 = -float('inf')
    now_place = start
    # 一回も動かない可能性あるのでここ修正
    now_score = 0
    done_ls = [0] * n
    place_score = [0] * n
    place_times = [0] * n
    t = 0
    while True:
        # きたところの処理
        if done_ls[now_place]:
            break
        done_ls[now_place] = 1
        place_score[now_place] = now_score
        place_times[now_place] = t

        # 次の移動
        now_place = next_map[now_place]
        t += 1
        now_score += score_ls[now_place]
        max1 = max(now_score, max1)
        if t == k:
            return max1
    score_per_loop = now_score - place_score[now_place]
    times_per_loop = t - place_times[now_place]
    remain = k - t 
    # ここまでが最初に同じところにたどり着くまで
    
    # ループでのポイントがプラスなら、最大限ループする
    if score_per_loop >= 0:
        q,remain = divmod(remain, times_per_loop)
        now_score += score_per_loop*q
    max2 = now_score
    
    # 余った回数
    while remain > 0:
        now_place = next_map[now_place]
        now_score += score_ls[now_place]
        max2 = max(max2,now_score)
        remain -= 1

    return max(max1,max2)

ans = -float('inf')
for i in range(n):
    ans = max(ans, max_of_the_start(i))
print(ans)

Submission status: Wrong Answer

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

# D - Moving Piece
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)

# マス目を周期ごとに分割する
groups = []
appeared = set()

for i in range(1, N + 1):
	if not i in appeared:
		group = []
		s = set()
		j = i

		while not j in s:
			group.append(j)
			s.add(j)
			appeared.add(j)
			j = P[j]

		groups.append(group)

MIN = -sys.maxsize
ans = MIN

# 周期ごとにハイスコアを算出
for group in groups:
	n = len(group)

	# スタート位置を1マスずつズラす
	for g in group:
		score = 0
		max_score = MIN
		scores = []
		scores.append(MIN)
		Pi = P[g]

		for j in range(n):
			score += C[Pi]
			max_score = max(max_score, score)
			scores.append(max_score)
			Pi = P[Pi]

		if K > n and score > 0:
			s = scores[K % n] + score * (K // n)
			ans = max(ans, s)
		elif K > n:
			ans = max(ans, scores[n])
		else:
			ans = max(ans, scores[K])

print(ans)

Submission status: Wrong Answer

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

# D - Moving Piece
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)

# マス目を周期ごとに分割する
groups = []
appeared = set()

for i in range(1, N + 1):
	if not i in appeared:
		group = []
		s = set()
		j = i

		while not j in s:
			group.append(j)
			s.add(j)
			appeared.add(j)
			j = P[j]

		groups.append(group)

MIN = -sys.maxsize
ans = MIN

# 周期ごとにハイスコアを算出
for group in groups:
	n = len(group)

	# スタート位置を1マスずつズラす
	for g in group:
		score = 0
		max_score = MIN
		scores = []
		scores.append(MIN)
		Pi = P[g]

		for j in range(n):
			score += C[Pi]
			max_score = max(max_score, score)
			scores.append(max_score)
			Pi = P[Pi]

		if K > n and score > 0:
			s = scores[K % n] + score * (K // n)
			ans = max(ans, s)
		elif K > n:
			ans = max(ans, max_score)
		else:
			ans = max(ans, scores[K])

print(ans)

Submission status: Wrong Answer

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

# D - Moving Piece
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)

# マス目を周期ごとに分割する
groups = []
appeared = set()

for i in range(1, N + 1):
	if not i in appeared:
		group = []
		s = set()
		j = i

		while not j in s:
			group.append(j)
			s.add(j)
			appeared.add(j)
			j = P[j]

		groups.append(group)

ans = -sys.maxsize

# 周期ごとにハイスコアを算出
for group in groups:
	# スタート位置を1マスずつズラす
	for g in group:
		score = 0
		max_score = -sys.maxsize
		scores = []
		scores.append(-sys.maxsize)
		Pi = P[g]

		for j in range(len(group)):
			score += C[Pi]
			max_score = max(max_score, score)
			scores.append(max_score)
			Pi = P[Pi]

		if K > len(group) and score > 0:
			s = scores[K % len(group)] + score * (K // len(group))
			ans = max(ans, s)
		elif K > len(group):
			ans = max(ans, max_score)
		else:
			ans = max(ans, scores[K])

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

g = [v for v in range(n + 1)]
s = [0] * (n + 1)
r = [0] * (n + 1)
seen = set()
for i in range(1, n + 1):
    if i in seen:
        s[i] = s[g[i]]
        r[i] = r[g[i]]
        continue
    ni = i
    sm = 0
    cnt = 0
    while True:
        ni = p[ni]
        sm += c[ni]
        cnt += 1
        g[ni] = i
        seen.add(ni)
        if ni == i:
            break
    s[i] = sm
    r[i] = cnt

ans = -(10 ** 9 + 1)
for i in range(1, n + 1):
    ni = i
    sm = 0
    cnt = 0
    while True:
        ni = p[ni]
        sm += c[ni]
        cnt += 1
        ans = max(ans, sm, sm + (k - cnt) // r[i] * s[i])
        if ni == i:
            break
print(ans)