Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

8

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

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

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

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

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

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

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

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

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



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


Sample output:
8

Submission status: Wrong Answer

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

loop_list = [] # ([indexes])
loop_score_list = []
loop_index_list = [0]*N
is_included_loop = [0] * N
num_loop = 0

for start in range(N):
    if is_included_loop[start]:
        continue
    now = start
    count = 1
    visited = [-1]*N # count
    visited[now] = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            terminate_count = count
            start_count = visited[now]
            loop_start_idx = now
            break
        visited[now] = count
        count += 1
    
    num_loop += 1
    now = loop_start_idx
    loop_indexes = [now]
    visited = [-1]*N
    visited[now] = 0
    count = 1
    loop_score = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            break
        loop_indexes.append(now)
        visited[now] = count
        loop_index_list[now] = num_loop
        loop_score += C[now]
        is_included_loop[now] = 1
    loop_list.append(loop_indexes)
    loop_score_list.append(loop_score)


scores = []
for start in range(N):
    tmp_score = 0
    rest = K
    now = start
    while not is_included_loop[now] and rest > 0:
        now = P[now]
        rest -= 1
        tmp_score += C[now]
        scores.append(tmp_score)
    
    if rest <= 0:
        scores.append(tmp_score)
        continue
    # loop
    number_of_loop = loop_index_list[now] - 1
    one_cicle_score = loop_score_list[number_of_loop]
    if one_cicle_score < 0:
        continue
    if rest <= len(loop_list[number_of_loop]):
        while rest >= 0:
            now = P[now]
            rest -= 1
            tmp_score += C[now]
            scores.append(tmp_score)
        continue
    else:
        n_l = rest // len(loop_list[number_of_loop])
        tmp_score += n_l * one_cicle_score
        rest -= n_l * len(loop_list[number_of_loop])
        while rest >= 0:
            now = P[now]
            rest -= 1
            tmp_score += C[now]
            scores.append(tmp_score)
        scores.append(tmp_score)
print(max(scores))

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 = -float("inf")
for i in range(N):
    hoge = []
    p = i
    s = 0
    for j in range(K):
        p = P[p]-1
        s += C[p]
        hoge.append(s)
        ans = max(ans,s)
        if p == i:
            s *= K//len(hoge)
            if K%len(hoge) != 0:
                s += max(hoge[0:K%len(hoge)])
            ans = max(ans,s)
            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=-float('inf')


x=[0]*n
for i in range(n):
    if x[i]==0:
        x[i]=1
        y=p[i]-1
        # 累積和を格納
        aa=[0,c[i]]
        # ２周させる
        life=2
        for j in range(2*n+2):
            x[y]=1
            if life>0:
                aa.append(aa[-1]+c[y])
                y=p[y]-1
                if y==i:
                    life-=1
            else:
                break
        # 各回数での取れるスコアの最大値
        a=[-float('inf')]*(len(aa))

        for ii in range(len(aa)-1):
            for j in range(ii+1,len(aa)):
                a[j-ii]=max(a[j-ii],aa[j]-aa[ii])
        print(aa)
        print(a)
        v=k//(len(aa)-1)
        w=k%(len(aa)-1)

        if k<=len(aa)-1:
            ans=max(ans,max(a[:k+2]))

        elif v<2:
            ans = max(ans, max(a), v * aa[-1] + max(a[:w + 1]))
        else:
            ans=max(ans,max(a),v * aa[-1] + max(a[:w + 1]),(v-1)*aa[-1]+max(a))
            print(a[:w+1])




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()))
maxsc = 0
for s in range(1,n+1):
  x = s
  sc = [0]
  i = 0
  while i<k:
    x = p[x]
    sc.append(sc[i]+c[x])
    i += 1
    if x == s:
      loop = i
      loopsc = sc[i]
      if loopsc > 0:
        baseup = loopsc * int((k-i)/loop)
        for j in range(loop):
          sc[j+1] += baseup
        for j in range((k-i)%loop):
          sc[j+1] += loopsc
      i=k
  sc[0] = -1e20
  maxsc = max(maxsc, max(sc))
print(maxsc)

Submission status: Wrong Answer

Solution code:
def input_list():
    return list(map(int, input().split()))


N, K = input_list()
P_LI = input_list()
C_LI = input_list()
if K <= N:
    ans = max(C_LI)
    for n in range(N):
        # スタート地点決める
        tmp_ans = C_LI[n]
        i = n
        for _ in range(K):
            # K回回す
            i = P_LI[i] - 1
            tmp_ans += C_LI[i]
            ans = max(ans, tmp_ans)
    print(ans)
else:
    """
    K // N 周回せる。
    K % N 回余るので、残り回数で取得可能な最大値を探す
    """
    # 周回しないほうが良いパターンを考慮する
    ans = max(C_LI)
    for n in range(N):
        # スタート地点決める
        tmp_ans = C_LI[n]
        i = n
        for _ in range(N):
            i = P_LI[i] - 1
            tmp_ans += C_LI[i]
            ans = max(ans, tmp_ans)

    # 周回したほうが良いパターン
    tmp_ans = max(C_LI)
    for n in range(N):
        # スタート地点決める
        tmp_total = C_LI[n]
        i = n
        for _ in range(K % N):
            i = P_LI[i] - 1
            tmp_total += C_LI[i]
            tmp_ans = max(tmp_total, tmp_ans)
    print(max(ans, sum(C_LI) * (K // N) + tmp_ans))

Submission status: Wrong Answer

Solution code:
def resolve():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  visit=[False]*n
  group_l=[[] for _ in range(n)]
  group_n=0
  for i in range(n):
    if visit[i]==True:
      continue
    group_l[group_n].append(c[i])
    visit[i]=True
    bp=p[i]-1
    while visit[bp]==False:
      group_l[group_n].append(c[bp])
      visit[bp]=True
      bp=p[bp]-1
    group_n+=1
  ans=[]
  for g in range(group_n):
    len_g=len(group_l[g])
    a=k//len_g
    b=k%len_g
    sum_g=sum(group_l[g])
    group_l[g]+=group_l[g]+group_l[g]
    sum_gl=[]
    s=1
    for i in group_l[g]:
      s+=i
      sum_gl.append(s)
    if a==0:
      m=b
    elif sum_g<0:
      m=len_g
    else:
      m=len_g+b
    x=-10**9-1
    for mi in range(1,m+1):
      csum=sum_gl[mi-1]
      msum=csum
      for i in range(1,len_g):
        csum=sum_gl[i+mi-1]-sum_gl[i-1]
        msum=max(msum,csum)
      x=max(x,msum)
    if sum_g>0 and a>0:
      x=sum_g*(a-1)+x
    ans.append(x)
  print(max(ans))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
ap = list(map(int, input().split()))
cp = list(map(int, input().split()))

score = []

for m in range(n):
  p = m
  s = []
  ss = 0
  np = -1
  while np != m:
    np = ap[p]-1
    ss = ss + cp[np]
    p = np
    s.append(ss)
  score.append(s)

max_s = -(10**9)
for m in range(n):
  loop = int(k / len(score[m]))
  sl = score[m][-1] * loop
  if sl < 0:
    sl = 0
  sm = score[m][0]
  y = k % len(score[m])
  for j in range(y):
    sm = max(sm, score[m][j])
  max_s = max(max_s, sm + sl)

print(max_s)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
P = [int(i)-1 for i in input().split()]
C = [int(i) for i in input().split()]
def f(s):
    slow = s
    fast = s
    counter = 0
    for _ in range(N):
        slow = P[slow]
        fast = P[P[fast]]
        counter += 1
        if slow == fast:
            break
    # counter = m = lambda + k * myu
    # m = lambda(開始地点) +(m - lambda)
    # lambda進むとmyuの定数倍のmがlambdaから進んだ事になるのでそこがスタート地点
    # get lambda
    slow2 = slow
    slow_start = s
    counter = 0
    for _ in range(K):
        slow2 = P[slow2]
        slow_start = P[slow_start]
        counter += 1
        if slow2 == slow_start:
            break
    lam = counter
    slow3 = slow
    counter = 0
    for _ in range(K):
        slow3 = P[slow3]
        counter += 1
        if slow3 == slow:
            break
    myu = counter
    return (lam, myu)

maxsum = -10 ** 10
for s in range(N):
    lam, myu = f(s)
    tmpmaxs = -10 ** 10
    tmp = s
    tmpsum = 0
    for _ in range(K%myu):
        tmpsum += C[tmp]
        if tmpsum > tmpmaxs:
            tmpmaxs = tmpsum
        if tmpsum < 0:
            tmpsum = 0
        tmp = P[tmp]
    # tmpmaxsは循環しない時の最大値
    tmp = s
    cirsum = 0
    cirmaxs = -10 ** 10
    cirtmps = 0

    for _ in range(myu):
        cirsum += C[tmp]
        cirtmps += C[tmp]
        if cirmaxs < cirtmps:
            cirmaxs = cirtmps
        if cirtmps < 0:
            cirtmps = 0
        tmp = P[tmp]
    tot = 0
    if cirsum < 0:
        tot = cirmaxs
    else:
        tot = tmpsum + (cirsum) * (K//myu)
    if maxsum < tot:
        maxsum = tot

print(maxsum)

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()))
scores = []


def max_sum(lst):
    maximum = 0
    temp = 0
    for i in lst:
        temp += C[i]
        maximum = max(maximum, temp)
    return maximum


for i in range(N):
    count = 0
    now = i
    passed = []
    while count <= K:
        nxt = P[now]
        count += 1
        if nxt in passed:
            break
        passed.append(nxt)
        now = nxt
    
    point = 0
    if count <= K:
        steps = len(passed)
        lp_points = sum(C[pos] for pos in passed)
        if lp_points > 0:
            lp_cnt = K // steps
            point += lp_points * lp_cnt
            rest = passed[:K - steps * lp_cnt]
            point += max_sum(rest)
        else:
            point = max_sum(passed)
    else:
        point = C[i]
        point += max_sum(passed)
    scores.append(point)

print(max(scores))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [p-1 for p in P]

check = [False] * n
loops = []

for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)


ans = 0

for loop in loops:

    num = len(loop)
    sho = k // num
    r = k % num
    if r == 0:
        r = num
        sho -= 1
    L = [C[p] for p in loop]

    ans_tmp = 0

    ryaku = 0
    if sum(L) > 0:
        ryaku = sum(L) * sho

    L += L[:r]
    ACC = [0] + list(accumulate(L))

    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j]-ACC[i]+ ryaku)

    ans = max(ans, ans_tmp)

if ans == 0:
    print(max(C))
    exit()
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 i in range(N):
    hoge = []
    p = i
    s = 0
    for j in range(K):
        p = P[p]-1
        s += C[p]
        hoge.append(s)
        ans = max(ans,s)
        if p == i:
            s *= K//len(hoge)
            if K%len(hoge) != 0:
                s += max(hoge[0:K%len(hoge)])
            ans = max(ans,s)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    p = LI()
    c = LI()

    hairetu = [[0] for i in range(n)]
    for i in range(n):
        next_idx = i + 1
        for times in range(1, n + 1):
            next_idx = p[next_idx - 1]
            hairetu[i].append(hairetu[i][times - 1] + c[next_idx - 1])
            if next_idx == i + 1:
                break

    lengths = [0] * n
    one_roop = list(map(lambda x: x[-1], hairetu))

    for i in range(n):
        lengths[i] = len(hairetu[i]) - 1

    maxs = list(map(lambda x: max(x, 0), one_roop))
    anss = [-1 * 10 ** 9]*n
    for i in range(n):
        length = lengths[i]
        amari = k % length
        shou = k // length
        maxs[i] = shou * maxs[i]

        for j in range(1, max(2, amari + 1)):
            anss[i] = max(maxs[i] + hairetu[i][j], anss[i])

    print(max(*anss))


main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
#入力
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
#入力終了
ans = -1 * (10 ** 10)
for i in range(n): #どのマスで始めるか
    l = [] #ループを見つけるための探索済みリスト
    ind = i #今いる位置
    loop = []
    for j in range(n): #n回繰り返す
        if ind in l: #もしすでにいまいる位置が探索済みだったら
            loop = l[l.index(ind):] #ループをリストに格納
            break
        l.append(ind)
        ind = p[ind]-1
    if len(loop) == 0 or len(loop) >= n: #もしループが無かったら普通にｋ回追う
        cnt = 0
        ind = i
        for j in range(k):
            ind = p[ind]-1
            cnt += c[ind]
            ans = max(ans, cnt)
        print(ans, "no loop")
        continue #この回は終わり
    if sum([c[i] for i in loop]) <= 0: #もしループの移動時のポイントの和が０以下だったら
        ans = max(ans, max(list(accumulate(loop)))) #ans, xの和, xの和とループの累積和のmax　でmaxを取る
    else:
        ans = max(ans, (k//len(loop))*sum([c[i] for i in loop])+sum([c[i] for i in loop[:k%len(loop)]]))
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**15

N,K = map(int,input().split())
P = [0]+list(map(int,input().split()))
C = [0]+list(map(int,input().split()))

moudeta = [0]*(N+1)

gogolist = []

for i in range(1,N+1):
    if moudeta[i]==1:
        continue
    gogolist.append([])
    now = i
    gogolist[len(gogolist)-1].append(now)
    moudeta[i]=1
    now = P[i]
    while now != i:
        gogolist[len(gogolist)-1].append(now)
        moudeta[now]=1
        now = P[now]
for i in range(len(gogolist)):
    gogolist[i] = gogolist[i]+gogolist[i]

ret = -INF

for golis in gogolist:
    around = 0
    for i in range(len(golis)//2):
        around += C[golis[i]]

    ans = -INF
    ansgo = -INF
    for i in range(len(golis)//2):
        tmpans = -INF
        tmp = 0
        for j in range(K%(len(golis)//2)):
            tmp+=C[golis[i+j]]
            tmpans = max(tmpans,tmp)    
        ans = max(ans,tmpans)
    
    for i in range(len(golis)//2):
        tmpansgo = -INF
        tmp = 0
        for j in range(min(len(golis)//2,K)):
            tmp+=C[golis[i+j]]
            tmpansgo = max(tmpansgo,tmp)
        ansgo = max(ansgo,tmpansgo)

    ret = max(around,ansgo,around*(K//(len(golis)//2))+ans,ret)


print(ret)

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 = -10000000

if K <= N:
    for i in range(N):
        count = 0
        tmp_point = 0
        nv = i
        while count < K:
            nvv = P[nv]
            nvv -= 1
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
    print(ans)
else:
    loop = [0]*N
    for i in range(N):
        count = 0
        check = [False]*N
        tmp_point = 0
        nv = i
        while True:
            nvv = P[nv]
            nvv -= 1
            if check[nvv] == True:
                break
            check[nvv] = True
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
        loop[i] = [tmp_point, count, i]
    loop.sort(reverse=True)
    #print(loop)
    new_ans = -10000000
    for value, counter, key in loop:
        if value < 0:
            break
        shou = K//counter
        amari = K%counter
        if amari == 0:
            amari = counter
            shou -= 1
        tmp_ans = value*shou
        new_ans = max(new_ans, tmp_ans)
        count = 0
        nv = key
        while count < amari:
            nvv = P[nv]
            nvv -= 1
            tmp_ans += C[nvv]
            count += 1
            nv = nvv
            new_ans = max(new_ans, tmp_ans)
        
    print(max(loop[0][0], ans, new_ans))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
pos = [0] + pos
score = [0] + score
max_point = -10 ** 10
for i in range(1, n + 1):
  point_l = []
  point = 0
  f_pos = i
  pos_l = set([f_pos])
  count = 0
  loop = 0
  #print('f_pos',f_pos)
  while count <= k:
    f_pos = pos[f_pos]
    point += score[f_pos]
    #print('pos', f_pos)
    #print(point)
    point_l.append(point)
    count += 1
    if point > max_point:
      max_point = point
    if f_pos in pos_l:
      loop = count
      break
    pos_l.add(f_pos)
  if loop != 0 and point > 0:
    loop_c = k // loop
    r = k % loop
    point *= loop_c
    #print(point)
    if point > max_point:
      max_point = point
    if r > 0:
      point += max(point_l[:r])
      #print(point)
      if point > max_point:
        max_point = point
print(max_point)

Submission status: Wrong Answer

Solution code:
def solve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pd = {i: x for i, x in enumerate(p, 1)}
    cd = {i: x for i, x in enumerate(c, 1)}
    ans = -10 ** 15
    for i in range(1, n + 1):
        res = 0
        x = i
        for j in range(1, min(5001, k + 1)):
            res += cd[x]
            x = pd[x]
            ans = max(res, ans)
    print(ans)


solve()

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 = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (0 if k > r else t))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    P = LI1()
    C = LI()

    ans = -INF
    for i in range(N):
        S = [0] * (N+1)
        used = [0] * N
        used[i] = 1
        mxs = [-INF] * (N+1)
        STEP = [-1] * N
        step = 0
        while 1:
            next = P[i]
            step = step + 1
            score = S[step-1] + C[next]
            S[step] = score
            mxs[step] = max(mxs[step-1], score)
            # ans_l = max(ans_l, S[step])
            if step == K:
                # print(mxs, mxs[K])
                ans = max(ans, mxs[K])
                break

            if used[next]:
                left = K - step
                # print(next, S, step, S[step], left)

                # print(mxs, p, q, mxs[step])
                # 現在の最高得点で打ち切る
                ans = max(ans, mxs[step])
                # print(next, S, STEP, step, STEP[next])
                if STEP[next] == -1:
                    loop_size = step
                    pre_idx = 0
                else:
                    loop_size = len(S[STEP[next]:S[step]])
                    pre_idx = STEP[next]
                ss = S[step] - S[pre_idx]


                if ss > 0:
                    p = left // loop_size
                    q = left % loop_size
                    ans = max(ans, S[step] + ss * p + max(0, mxs[q]))

                # plus = max(S[step] * p + max(0, mxs[q]), mxs[step])
                # ans = max(ans, max(mxs[step], S[step] + mxs[step] * p + mxs[q]))
                # ans = max(ans, max(mxs[step], S[step] + max(0, plus)))
                break
            STEP[next] = i
            used[next] = 1
            i = next
    print(ans)

    
if __name__ == '__main__':
    solve()

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 i in range(N):
    hoge = []
    p = i
    s = 0
    for j in range(K):
        p = P[p]-1
        s += C[p]
        hoge.append(s)
        ans = max(ans,s)
        if p == i:
            s *= K//len(hoge)
            if K%len(hoge) != 0:
                s += max(hoge[0:K%len(hoge)])
            ans = max(ans,s)
            break
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()))
maxsc = 0
for s in range(1,n+1):
  x = s
  sc = [-1E20]
  i = 0
  while i<k:
    x = p[x]
    sc.append(sc[i]+c[x])
    i += 1
    if x == s:
      loop = i
      loopsc = sc[i]
      if loopsc > 0:
        baseup = loopsc * int((k-i)/loop)
        for j in range(loop):
          sc[j+1] += baseup
        for j in range((k-i)%loop):
          sc[j+1] += loopsc
      i=k
  maxsc = max(maxsc, max(sc))
print(maxsc)

Submission status: Wrong Answer

Solution code:
INF = 10**15

N,K = map(int,input().split())
P = [0]+list(map(int,input().split()))
C = [0]+list(map(int,input().split()))

moudeta = [0]*(N+1)

gogolist = []

for i in range(1,N+1):
    if moudeta[i]==1:
        continue
    gogolist.append([])
    now = i
    gogolist[len(gogolist)-1].append(now)
    moudeta[i]=1
    now = P[i]
    while now != i:
        gogolist[len(gogolist)-1].append(now)
        moudeta[now]=1
        now = P[now]
for i in range(len(gogolist)):
    gogolist[i] = gogolist[i]+gogolist[i]

ret = -INF

for golis in gogolist:
    around = 0
    for i in range(len(golis)//2):
        around += C[golis[i]]

    ans = -INF
    ansgo = -INF
    for i in range(len(golis)//2):
        tmpans = -INF
        tmp = 0
        for j in range(K%(len(golis)//2)):
            tmp+=C[golis[i+j]]
            tmpans = max(tmpans,tmp)    
        ans = max(ans,tmpans)
    
    for i in range(len(golis)//2):
        tmpansgo = -INF
        tmp = 0
        for j in range(min(len(golis)//2,K)):
            tmp+=C[golis[i+j]]
            tmpansgo = max(tmpansgo,tmp)
        ansgo = max(ansgo,tmpansgo)

    ret = max(around,ansgo,around*(K//(len(golis)//2))+ans,ret,around*(K//N-1)+ansgo)


print(ret)

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 = max(C)
for i in range(N):
    s = i
    l = []
    while True:
        s = P[s]-1
        l.append(C[s])
        if s == i:
            break

    if sum(l) > 0:
        c = K//len(l)*sum(l)
        n = K%len(l)
        ans = max(ans,c)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,c+x)

    n = min(N,K)
    s = i
    x = 0
    for j in range(n):
        s = P[s]-1
        x += C[s]
        ans = max(ans,x)
            
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()))

max_score = -1000000000
for i in range(n):
    period = 0
    count = 0
    start = p[i]-1
    now = start
    for _ in range(k):
        period += c[now]
        now = p[now]-1
        count += 1
        if now == start:
            div = k // count
            break
    score = 0
    now = start
    for _ in range(k%count):
        score += c[now]
        max_score = max(max_score,score)
        now = p[now]-1

if period < 0:
    print(max_score)
else:
    print(max_score + period * div)

Submission status: Wrong Answer

Solution code:
# O(EV)
def bellman_ford(s):
    d = [0]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    x=s
    visited=[x]
    for tt in range(k):
        update = False # 更新が行われたか
        aa,bb,cc=g[x][0],g[x][1],g[x][2]
        if d[bb] < d[aa] + cc:
                d[bb] = d[aa] + cc
                update = True
                visited+=[bb]
            
        if not update:
            break

        if visited[0]==visited[-1]:
            if d[visited[-1]]>0:
                pin=len(visited)-1

                return [0,(k//pin)*d[visited[0]]+d[visited[k%pin]]]
                



        x=bb
    return d

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

g=[]
p=list(map(int,input().split()))
c=list(map(int,input().split()))

if max(c)<0:
    print(max(c))
    exit()

for i in range(n):
    g.append((i,p[i]-1,c[p[i]-1]))

ans=0

for i in range(n):
  ans=max(ans,max(bellman_ford(i)))

print(ans)

Submission status: Wrong Answer

Solution code:

def max2(x,y):
    return x if x > y else y

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

off = max(C)
m2 = off
for i in range(N):
    tmp = 0
    m1 = off
    l = i
    S = 0
    k = 0
    visited = [-1]*N
    for j in range(N):
        S += C[l]
        visited[l] = j
        l = P[l] - 1
        if visited[l] != -1:
            k = j - visited[l] + 1
            break
    cnt = K // k - (K % k == 0)
    a = K%k + (K % k == 0)*k
    for j in range(a):
        tmp += C[l]
        m1 = max2(m1, tmp)
        l = P[l] - 1
    if S > 0:
        m1 += cnt*S
    m2 = max2(m1, m2)

print(m2)
"""
4 10
2 1 4 3
1 2 3 -1
"""