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(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC >= 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now, K):
        ret = -10**18
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -10**18
    for start in V:
        mx = max(mx, calc(start, K))
    return ans + mx

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)

Submission status: Wrong Answer

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

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC >= 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)

    def calc(now, K):
        ret = -10**18
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -10**18
    for start in V:
        mx = max(mx, calc(start, K))
    return ans + mx

ans = -10**18
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)

Submission status: Wrong Answer

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

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)

    def calc(now, K):
        ret = -10**18
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -10**18
    for start in V:
        mx = max(mx, calc(start, K))
    return ans + mx

ans = -10**18
for V in grp:
    ans = max(ans, solve(V, K))
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()))

dummy=set()
loop=[]
X=set(range(N))
while len(dummy)!=N:
  a=[]
  k=min(X-dummy)
  a.append(k)
  dummy.add(k)
  l=P[k]-1
  while l!=k:
    a.append(l)
    dummy.add(l)
    l=P[l]-1
  loop.append(a)

ans=-(10**300)
for l in loop:
  temp=0
  s=len(l)
  ssum=0
  k=0
  for i in range(s):
    ssum+=C[l[i]]
  if ssum>0:
    temp+=(K//s-1)*ssum
  k=min(K,s)
  kmax=-(10**300)
  for ii in range(1,k+1):
    for jj in range(s):
      tempscore=temp
      for kk in range(ii):
        tempscore+=C[l[(jj+kk)%s]]
      if tempscore>kmax:
        kmax=tempscore
  if kmax>ans:
    ans=kmax
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()))

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    loop = False
    left = k
    for j in range(n):
        if left <= 0:
            break

        now = p[now]
        score += c[now]
        ans = max(ans, score)
        left -= 1

        if score_cnt[now]:
            loop = True
            break

    if loop:
        times = left // score_cnt[now][1]
        score += score_cnt[now][0] * times
        left -= times * score_cnt[now][1]
        ans = max(ans, score)
        for _ in range(left):
            now = p[now]
            score += c[now]
            ans = max(ans, score)

print(ans)

Submission status: Wrong Answer

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

def solve(K, V):
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0

    if sumC >= 0:
        q, K = divmod(K, len(V))
        ans += sumC * q
    else:
        K = min(K, len(V))

    def calc(now):
        ret = -10**18
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = max(C)
    for start in V:
        mx = max(mx, calc(start))

    return ans + mx

ans = -10**18
visited = [False] * N
for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    ans = max(ans, solve(K, V))

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

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    loop = False
    left = k
    for j in range(n):
        if left < 0:
            break

        now = p[now]
        score += c[now]
        ans = max(ans, score)
        left -= 1

        if score_cnt[now]:
            loop = True
            break

    if loop:
        times = left // score_cnt[now][1]
        score += score_cnt[now][0] * times
        left -= times * score_cnt[now][1]
        ans = max(ans, score)
        for _ in range(left):
            now = p[now]
            score += c[now]
            ans = max(ans, score)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j >= K: break
    now = t
    if tot > 0:
      now += tot*(K-(j+1))//l
    ans = max(ans, now)

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()))
ans = -10 ** 18
for i in range(N):
    j = i
    s = []
    total = 0
    while True:
        j = P[j] - 1
        s.append(C[j])
        total += C[j]
        if i == j:
            break
    l = len(s)
    t = 0
    for k in range(l):
        t += s[k]
        print(k, K)
        if k + 1 > K: break
        now = t
        if total > 0:
            e = (K - (k + 1)) // l
            now += total * e
        ans = max(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  nex = P[i]
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(1,l+1):
    t += cycle[j-1]
    if j > K: break
    now = t
    if tot > 0:
      now += tot*(K-j)//l
    ans = max(ans, now)

Submission status: Wrong Answer

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

V=[0 for i in range(n+1)]
M=[0 for i in range(n+1)]
for i in range(1,n+1):
    M[P[i]]=i

SAV=[0 for i in range(n+1)]

lasans=-10**15

now=1

for now in range(1,n+1):
    if V[now]==0:
        ans=-10**15
        wans=-10**15
        cnt=0
        tot=0
        que=[]
        head=0
        while V[now]==0:
            V[now]+=1
            cnt+=1
            now=P[now]
        newk=k%cnt
        while V[now]<3:
            V[now]+=1
            que.append(C[now])
            now=P[now]
            tot+=C[now]
        s=[0]
        for i in range(len(que)):
            s.append(s[i]+que[i])
        for i in range(len(s)-1):
            for q in range(i+1,min(len(s),i+1+newk)):
                ans=max(ans,s[q]-s[i])
        for i in range(len(s)-1):
            for q in range(i+1,min(i+1+cnt,len(s))):
                wans=max(wans,s[q]-s[i])
        
        #print(cnt,ans,tot,que)
        lasans=max(max(0,(k//cnt)*sum(que)//2)+ans,lasans)
        if cnt>=k:
            lasans=max(lasans,wans)
print(lasans)

Submission status: Wrong Answer

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

V=[0 for i in range(n+1)]
M=[0 for i in range(n+1)]
for i in range(1,n+1):
    M[P[i]]=i

SAV=[0 for i in range(n+1)]

lasans=-10**15

now=1

for now in range(1,n+1):
    if V[now]==0:
        ans=-10**15
        wans=-10**15
        cnt=0
        tot=0
        que=[]
        head=0
        while V[now]==0:
            V[now]+=1
            cnt+=1
            now=P[now]
        newk=k%cnt
        while V[now]<3:
            V[now]+=1
            que.append(C[now])
            now=P[now]
            tot+=C[now]
        s=[0]
        for i in range(len(que)):
            s.append(s[i]+que[i])
        for i in range(len(s)-1):
            for q in range(i+1,min(len(s),i+1+newk)):
                ans=max(ans,s[q]-s[i])
        for i in range(len(s)-1):
            for q in range(i+1,min(i+1+cnt,len(s))):
                wans=max(wans,s[q]-s[i])
        
        #print(cnt,ans,tot,que)
        lasans=max(max(0,(k//cnt)*sum(que)//2)+ans,lasans)
        if k>=cnt:
            lasans=max(lasans,wans)
print(lasans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  nex = P[i]
  tot = 0
  while True:
    if nex == i: break
    tot += C[nex]
    cycle.append(C[nex])
    nex = P[nex]
  cycle.append(C[i])
  tot += C[i]

  l = len(cycle)
  t = 0
  for j in range(1,l+1):
    t += cycle[j-1]
    if j > K: break
    now = t
    if tot > 0:
      now += tot*(K-j)//l
    ans = max(ans, now)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  nex = P[i]
  tot = 0
  while True:
    if nex == i: break
    tot += C[nex]
    cycle.append(C[nex])
    nex = P[nex]
  cycle.append(C[i])
  tot += C[i]

  l = len(cycle)
  t = 0
  for j in range(1,l+1):
    t += cycle[j-1]
    if j > K: break
    now = t
    if tot > 0:
      now += tot*(K-j)//l
    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()))

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    cycle = 0
    for j in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        cycle += 1
        if pos == i: break
    q,r = divmod(k,cycle)
    if r == 0 and q > 1:
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = -float("inf")
    pos = n

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans = max(ans,tmp)
    
    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0 and K > cnt:
        pos = n
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans = max(ans,tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans = max(ans,tmp)

    return ans

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

print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = -float("inf")

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans = max(ans,tmp)
    
    pos = n
    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans = max(ans,tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans = max(ans,tmp)

    return ans

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

print(ans)

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

    for _ in range(myu):
        cirsum += C[tmp]
        tmp = P[tmp]
    tot = 0
    if cirsum <= 0:
        tmpmaxs = -10 ** 10
        tmp = s
        tmpsum = 0
        for _ in range(2 * myu):
            tmpsum += C[tmp]
            if tmpsum > tmpmaxs:
                tmpmaxs = tmpsum
            if tmpsum < 0:
                tmpsum = 0
            tmp = P[tmp] 
        tot = tmpmaxs
            
    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(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    p[i] -= 1
ans = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    t = 0
    for i in range(l):
        t += score[i]
        if i + 1 > k:
            break
        now = t
        if tot > 0:
            cycle_num = (k - (i)) // l
            now += tot * cycle_num
        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()))
for i in range(n):
    p[i] -= 1
ans = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    t = 0
    for i in range(l):
        now += score[i]
        if i + 1 > k:
            break
        now = t
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
        ans = max(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = []

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans.append(tmp)

    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0 and K > cnt:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans.append(tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)

    return max(ans)

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

print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = []

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans.append(tmp)

    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans.append(tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)

    return max(ans)

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

print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = []

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans.append(tmp)

    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ##ans.append(tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)

    return max(ans)

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

ans = -1e20
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    pos = n
    ans = []

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans.append(tmp)
    
    pos = n
    ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
    if tmp > 0:
        d = K%cnt
        tmp = (K//cnt)*tmp
        ans.append(tmp)
        for _ in range(d):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)

    return max(ans)

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

ans = -1e20
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Wrong Answer

Solution code:
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    pos = n
    ans = []

    if K <= cnt:
        ##Kがループ以下の場合,全部シミュレートして最大を返す
        for _ in range(K):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)
    else:
        ttmp = 0
        ##1ループをして得られるコスト
        for _ in range(cnt):
            pos = P[pos]-1
            ttmp += C[pos]
            ans.append(ttmp)

        ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
        if ttmp > 0:
            d = K%cnt
            tmp = (K//cnt)*ttmp
            ans.append(tmp)
            for _ in range(d):
                pos = P[pos]-1
                tmp += C[pos]
                ans.append(tmp)

    return max(ans)

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

ans = -1e20
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Wrong Answer

Solution code:
def read_input():

    n, k = map(int, input().split())
    p = list(map(lambda x : int(x) - 1, input().split()))
    c = list(map(int, input().split()))

    return n, k, p, c

def solve_i(i, k, p, c, n):
    
    points = None
    maxi = None
    s = i
    i = p[i]
    while i != s:
        
        if points is None:
            points = [c[i]]
        else:
            points.append(points[-1] + c[i])

        i = p[i]

    points.append(points[-1] + c[i])

    if k < len(points):
        return max(points[:k])

    if points[-1] <= 0:
        return max(points)
    else:
        cycles = k // len(points)
        remainder = k % len(points)

        potential = points[-1] * cycles
        if remainder != 0:
            potential += max(points[:remainder])
            
        maxi = max(points)
        return max(maxi, potential)



def solve(n, k, p, c):

    maxi = []
    for i in range(n):
        maxi.append(solve_i(i, k, p, c, n))

    return max(maxi)        


print(solve(*read_input()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque

def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    pos = n
    ans = []

    if K <= cnt:
        ##Kがループ以下の場合,全部シミュレートして最大を返す
        for _ in range(K):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)
    else:
        ttmp = 0
        ##1ループをして0以上ならループしまくる
        for _ in range(cnt):
            pos = P[pos]-1
            ttmp += C[pos]
            ans.append(ttmp)

        ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
        if ttmp >= 0:
            ans = []
            d = K%cnt
            tmp = (K//cnt)*ttmp
            ans.append(tmp)
            for _ in range(d):
                pos = P[pos]-1
                tmp += C[pos]
                ans.append(tmp)

    return max(ans)

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

ans = -1e20
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque

def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    pos = n
    ans = []

    if K <= cnt:
        ##Kがループ以下の場合,全部シミュレートして最大を返す
        for _ in range(K):
            pos = P[pos]-1
            tmp += C[pos]
            ans.append(tmp)
    else:
        ttmp = 0
        ##1ループをして0以上ならループしまくる
        for _ in range(cnt):
            pos = P[pos]-1
            ttmp += C[pos]
            ans.append(ttmp)

        ##ループして0以上なら(K//cnt)回ループしてあまりをシミュレーション
        if ttmp >= 0:
            ans = []
            d = K%cnt
            tmp = (K//cnt)*ttmp
            ans.append(tmp)
            for _ in range(d):
                pos = P[pos]-1
                tmp += C[pos]
                ans.append(tmp)

    return max(ans)

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

ans = -1e9
for i in range(N):
    ans = max(ans,res(i))

print(ans)

Submission status: Wrong Answer

Solution code:
"""
1. マス同士は有効グラフの一本道になっている。で、必ずどこかでループが発生している。

2. 各点から各点に移動する場合のスコアの合計とステップ数(ループ内の場合は一周以内のもの)を前処理(dfs)で求めておく。dp[i][j] => iからjまでのスコアとステップ数

3. K > N の場合、ループを通るとスコアがマイナスになるなら（dp[i][i]がマイナスになるようなiが存在するなら）、ループを一周しない方がよい。
ループを通るとスコアがプラスになるなら、

各iに対して地点iからスタートする場合というのをシミュレートすると実装が楽そう。
K <= Nの場合はi番目からスタートして、dfsでstep数がKに到達するまで進み続けて、スコアの最大値を図る。
Kが大きい場合は、dfsで道をたどっていってループを検出したら、その時点でループスコアがマイナスかプラスかを判断して、マイナスなら終了。
プラスならループスコア*(K//ループstep)を加算してできる限りKを減らす。そこからstep数がKに到達するまでdfsで道をたどっていって最大値を求める。
各スタート地点ごとにO(N)で処理可能なので、全体ではO(N^2)で処理できる
"""
import sys
sys.setrecursionlimit(10000)
def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))

    def dfs(cur,score,scores,step,steps):
        if scores[cur] == None:
            scores[cur] = score
            steps[cur] = step
        else:
            if scores[cur] >= score:
                return
            else:
                loopStep = step - steps[cur]
                loopScore = score - scores[cur]

                scores[cur] = score
                steps[cur] = step

                scores[cur] += ((K - steps[cur])//loopStep)*loopScore
                steps[cur] += ((K - steps[cur])//loopStep)*loopStep
                
        if steps[cur] < K:
            p = P[cur-1]
            c = C[p-1]
            dfs(p,scores[cur]+c,scores,steps[cur]+1,steps)
        else:
            return

    ans = -float("INF")
    for i in range(1,N+1):
        scores = [None]*(N+1)
        steps = [None]*(N+1)
        dfs(i,0,scores,0,steps)
        for j in range(N+1):
            if scores[j] != None and steps[j] != 0:
                ans = max(ans,scores[j])
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
def read_input():

    n, k = map(int, input().split())
    p = list(map(lambda x : int(x) - 1, input().split()))
    c = list(map(int, input().split()))

    return n, k, p, c

def solve_i(i, k, p, c, n):
    
    points = 0
    maxi = float('-Inf')

    s = i
    i = p[i]
    t = 0
    while i != s and t < k:
        
        points += c[i]
        i = p[i]
        t += 1
        maxi = max(maxi, points)

    if k == t:
        return maxi

    points += c[i]
    maxi = max(maxi, points)
    t += 1

    if points < 0:
        return maxi
    else:
        cycles = k // t
        remainder = k % t
        potential = points * cycles

        if remainder != 0:
            tmp_max = float('-Inf')
            i = s
            tmp_points = 0
            for _ in range(remainder):
                tmp_points += c[i]
                i = p[i]
                tmp_max = max(tmp_max, tmp_points)
            potential += tmp_max

        return max(maxi, potential)

def solve(n, k, p, c):

    maxi = float('-Inf')
    for i in range(n):
        maxi = max(maxi, solve_i(i, k, p, c, n))

    return maxi


print(solve(*read_input()))

Submission status: Wrong Answer

Solution code:
def read_input():

    n, k = map(int, input().split())
    p = list(map(lambda x : int(x) - 1, input().split()))
    c = list(map(int, input().split()))

    return n, k, p, c

def solve_i(i, k, p, c, n):
    
    points = 0
    maxi = float('-Inf')

    s = i
    i = p[i]
    t = 0
    while i != s and t < k:
        
        points += c[i]
        i = p[i]
        t += 1
        maxi = max(maxi, points)

    if k == t:
        return maxi

    points += c[i]
    maxi = max(maxi, points)
    t += 1

    if points < 0:
        return maxi
    else:
        cycles = k // t
        remainder = k % t
        potential = points * cycles

        if remainder != 0:
            tmp_max = float('-Inf')
            i = s
            tmp_points = 0
            for _ in range(remainder):
                i = p[i]
                tmp_points += c[i]
                tmp_max = max(tmp_max, tmp_points)
            potential += tmp_max

        return max(maxi, potential)

def solve(n, k, p, c):

    maxi = float('-Inf')
    for i in range(n):
        maxi = max(maxi, solve_i(i, k, p, c, n))

    return maxi


print(solve(*read_input()))