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:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):
    res = - 10 ** 10
    for i in range(N):
        lmax = - 10 ** 10
        nlmax = 0
        cp = P[i] - 1
        cl = 1
        cs = C[cp]
        while cp != i:
            if cs > lmax:
                lmax = cs
                nlmax = cl
            cp = P[cp] - 1
            cl += 1
            cs += C[cp]
        if cs > lmax:
            lmax = cs
            nlmax = cl
        syc = cs
        length = cl
        res = max(res, max(lmax, syc * ((K - nlmax) // length) + lmax))
        # print((i, syc, lmax, nlmax, length))
    print(res)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = min(c)

ans = minc


def get_loop(i):
    pos = i
    cnt = 0
    cur_score = 0
    max_score = minc
    while cnt == 0 or pos != i:
        pos = p[pos]
        cur_score = cur_score + c[pos]
        cnt += 1
        max_score = max(cur_score, max_score)
    return cnt, cur_score, max_score

# print(get_loop(2))

def solve(i):
    kk = k
    score = minc
    cur_score = 0
    pos = i
    loop_length, loop_score, max_loop_score = get_loop(i)
    cur_score = loop_score * (kk // loop_length)
    # print('loop', loop_length)
    if kk // loop_length > 0:
        # print("%s: %s // %s, %s, %s" % (i, kk, loop_length, cur_score, max_loop_score))
        score = max(cur_score, score)
    score = max(cur_score, max_loop_score)
    kk %= loop_length
    # print('rem k', kk, "cur_score", cur_score)
    for _ in range(kk):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    # print("%s: %s" % (i, score))
    return score

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
score = [0 for i in range(n)]
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = -(10**30)
for i in range(n):
    start = i
    cur = i
    i_s_score = 0
    i_s_score_max = C[P[cur]-1]
    move_num = 0
    for j in range(n):
        cur = P[cur]-1
        i_s_score += C[cur]
        i_s_score_max = max(i_s_score, i_s_score_max)
        move_num += 1
        if cur == start:
            break
    if i_s_score <= 0:
        ans = max(ans, i_s_score_max)
    else:
        temp = i_s_score*(k//move_num)
        rest = k%move_num
        ans = max(ans, temp)
        i_s_score = temp
        for j in range(rest):
            cur = P[cur]-1
            i_s_score += C[cur]
            ans = max(ans, i_s_score)
print(ans)

Submission status: Wrong Answer

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=Union_Find(N+1)

for i in range(1,N+1):
    U.union(i,P[i])

Cycle_Point={}
for a in U.roots():
    if a==0:
        continue

    b=P[a]
    S=C[a]
    while a!=b:
        S+=C[b]
        b=P[b]
    Cycle_Point[a]=S

Ans=-float("inf")
for i in range(1,N+1):
    group=U.find(i)
    length=U.size(i)

    rap,remain=divmod(K,length)

    if rap==0:
        Temp_Score=0
        Score=C[P[i]]

        p=i

        for _ in range(remain):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

    elif Cycle_Point[group]>0:
        Base_Score=Cycle_Point[group]*rap
        Temp_Score=Base_Score
        Score=Temp_Score

        p=i
        for _ in range(remain):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)
    else:
        Temp_Score=0
        Score=C[P[i]]

        p=i
        for _ in range(min(length,K)+1):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

    Ans=max(Ans,Score)

print(Ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
# print()
# print(*P)
# print(*C)
x = 0
used = [0] * N
root = [-1] * N
path = defaultdict(list)
score = defaultdict(list)
for i in range(N):
    if used[i]:
        continue
    x = i
    while used[x] == 0:
        used[x] = 1
        path[i].append(x)
        score[i].append(C[x])
        root[x] = i
        x = P[x]
ans = -float('inf')
for r in path:
    pa, sc, le = path[r], score[r], len(path[r])
    # print(pa, sc, le)
    for i in range(le-1):
        sc[i+1] += sc[i]
    tmp = sc[-1] * (K // le)
    if tmp < 0:
        m = -float('inf')
        for i in range(len(pa)):
            for j in range(i+1, len(pa)):
                if j - i <= K:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= K:
                    m = max(m, sc[le-1] - sc[j] + sc[i])
        ans = max(ans, m)
    else:
        k = K % le
        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= k:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= k:
                    m = max(m, sc[le-1] - sc[j] + sc[i])
        ans = max(ans, m + tmp)
        k = K % le + le
        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= k:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= k:
                    m = max(m, sc[le-1] - sc[j] + sc[i])
        # print(m)
        ans = max(ans, m + tmp - sc[-1])
print(ans)

Submission status: Wrong Answer

Solution code:
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))
    ans = -10**20
    for i in range(1,n+1):
        cou = 1
        se = {i}
        ne = p[i-1]
        su = [c[ne-1]]
        maxi=c[ne-1]
        while ne not in se and cou < k:
            se.add(ne)
            ne = p[ne-1]
            su.append(su[-1]+c[ne-1])
            maxi = max(maxi,su[-1])
            cou += 1
        if su[-1] > 0 and k:
            maxi = max(maxi,su[-1]*(k//len(su))+(0 if not k%len(su) else su[k%len(su)-1]))
        ans = max(ans,maxi)
    print(ans)


#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split()]
temp = [int(x) for x in input().split()]
p = [-1]
for x in temp:
    p.append(x)
c = [-1]
temp = [int(x) for x in input().split()]
for x in temp:
    c.append(x)

ans = -int(1e12)
# print(p)
# print(c)
# print()
for i in range(1, N+1):
    # print("i: ", i)
    visited = [False] * (N+1)
    cur_sum = 0
    cur_box = i
    l = 0
    k = K
    while True:
        if visited[cur_box]:
            break
        cur_sum += c[p[cur_box]]
        ans = max(ans, cur_sum)
        visited[cur_box] = True
        cur_box = p[cur_box]
        k -= 1
        l += 1
    # print(cur_sum)
    cur_sum = (cur_sum * (K // l))
    ans = max(ans, cur_sum)
    # print(cur_sum)
    k = K % l
    while k > 0:
        cur_sum += c[p[cur_box]]
        ans = max(ans, cur_sum)
        cur_box = p[cur_box]
        k -= 1
    # print(cur_sum)
    # print("i:", i , ", sum:", cur_sum)
    ans = max(ans, cur_sum)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = min(c)

ans = minc


def get_loop(i):
    pos = i
    cnt = 0
    cur_score = 0
    max_score = minc
    while cnt == 0 or pos != i:
        pos = p[pos]
        cur_score = cur_score + c[pos]
        cnt += 1
        max_score = max(cur_score, max_score)
    return cnt, cur_score, max_score

# print(get_loop(2))

def solve(i):
    kk = k
    score = minc
    cur_score = 0
    pos = i
    loop_length, loop_score, max_loop_score = get_loop(i)
    cur_score = loop_score * (kk // loop_length)
    # print('loop', loop_length)
    if kk // loop_length > 0:
        # print("%s: %s // %s, %s, %s" % (i, kk, loop_length, cur_score, max_loop_score))
        score = max(cur_score, score)
        score = max(cur_score, max_loop_score)
    kk %= loop_length
    # print('rem k', kk, "cur_score", cur_score)
    for _ in range(kk):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    # print("%s: %s" % (i, score))
    return score

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1回以上K回以下
ansF=-1000000000000000000
for i in range(n):
    #すでに辿ったもの
    check=[False]*n
    #辿った順番
    turns=[]
    #今
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    #答え(今の)
    ans=0
    #kのうち何回分
    #更新を毎回行う
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    #サイクルの長さ
    l=len(turns)
    #サイクルの和(あまりも)
    #サイクルどこで止めるか
    x=0
    for j in range(l):
        x+=c[turns[j]]
    #そもそもサイクル回らない場合
    if spare//l==0:
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    #サイクル回した方が良い場合
    if x>=0:
        ans+=(x*(spare//l))
        ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    #サイクル回さない方がいい場合
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    ans = -float('inf')
    for n in range(N):
        m = n
        ans_tmp = 0
        cnt = 0
        for k in range(K):
            nxt = P[m]
            score = C[nxt-1]
            ans_tmp += score
            ans = max(ans, ans_tmp)
            m = nxt-1
            cnt += 1
            if m == n:
                break
        divK = K//cnt
        if ans_tmp <= 0:
            continue
        repeat_ans_tmp = ans_tmp * divK
        for k in range(K%cnt):
            nxt = P[m]
            score = C[nxt-1]
            repeat_ans_tmp += score
            ans = max(ans, repeat_ans_tmp)
            m = nxt-1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

#高々N回で1周する
class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1] * n
 
    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
 
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u == v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u # size[u] <= size[v]
        self.size[v] += self.size[u]
        self._par[u] = v
 
    def same(self, u, v):
        return self.root(u) == self.root(v)

uf = UnionFind(n)
for i in range(n):
    uf.unite(i, p[i])

ans = []
for i in range(n):
    ite = uf.size[uf.root(i)]
    #print(ite)
    if k > ite:
        memo = [0 for _ in range(ite+1)]
        tmp = i
        for j in range(ite):
            tmp = p[tmp]
            memo[j+1] = memo[j] + c[tmp]
        div = k // ite
        mod = k % ite
        #print(memo)
        if memo[-1] <= 0:
            ans.append(max(memo[:mod+1]))
        else:
            m = max(memo[1:])
            ans.append(max(max(memo[:mod+1]) + div * memo[-1], (div-1) * memo[-1] + m))
    
    else:
        memo = [0 for _ in range(k+1)]
        tmp = i
        for j in range(k):
            tmp = p[tmp]
            memo[j+1] = memo[j] + c[tmp]
        ans.append(max(memo[1:]))
        

print(max(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**18

for i in range(N):
    cnt=K
    pos=i
    tmp=[0]
    base=C[pos]
    while cnt and P[pos]!=i:
        pos=P[pos]
        tmp.append(tmp[-1]+C[pos])
        base+=C[pos]
        cnt-=1
    if base>0:
        test=base*(K//len(tmp))
        cnt=K%len(tmp)
        if cnt:
            ttt=max(tmp[j] for j in range(1,cnt+1))
            if test:
                ttt=max(ttt,0)
            test+=ttt
        ans=max(ans,test)
    else:
        cnt=min(K,len(tmp)-1)
        if cnt:
            test=max(tmp[j] for j in range(1,cnt+1))
            ans=max(ans,test)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, K = read_values()
    P = read_list()
    C = read_list()

    res = V(max)
    for i in range(N):
        t = []
        c = 0
        p = i
        while len(t) == 0 or p != i:
            p = P[p] - 1
            c += C[p]
            t.append(c)

        m = len(t)
        # print(t, c)
        if m > K or c <= 0:
            res.ud(max(t))
        else:
            s = K // m * c
            k = K % m
            # print(f"s: {s}, k: {k}")
            tmp = V(max)
            for i in range(k):
                tmp.ud(s + t[i])
            
            s -= c

            for v in t:
                tmp.ud(s + v)
            
            res.ud(tmp.v)

    print(res)


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()))
if max(c) <= 0:
    print(max(c))
    exit()
ans = 0
for begin in range(n):
    i = p[begin]
    s = c[i]
    round = 1
    score = 0
    while i != begin:
        i = p[i]
        s += c[i]
        round += 1
    if s > 0 and k >= round:
        score += s * (k//round)
        kk = k - round * (k//round)
    elif k >= round:
        kk = round-1
    else:
        kk = k
    smax = 0
    now = 0
    i = begin
    while kk > 0:
        i = p[i]
        now += c[i]
        smax = max(now, smax)
        kk -= 1
    score += smax
    ans = max(ans, score)
#    print('{} {} {} {} {} {}'.format(score, smax, round, kk, s, begin))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    P = tuple(map(lambda x: int(x) - 1, input().split()))
    C = tuple(map(int, input().split()))
    ans = -10**18

    for i in range(N):
        k = K
        D = [[0, 0] for i in range(N)]
        x = i
        X, Y = 0, 0
        count = 0
        score = 0
        for j in range(K):
            if D[P[x]][0] == 0:
                score += C[P[x]]
                D[P[x]][0] = score
                D[P[x]][1] = count
                x = P[x]
                count += 1
            else:
                X = D[P[x]][0] - C[P[x]]
                score -= X

                L = (count - D[P[x]][1])
                k -= D[P[x]][1]
                score *= k // L

                l = K % L
                for i in range(N):
                    if D[i][1] == l + D[P[x]][1] - 1:
                        score += D[i][0] - X
                        break
                score += X
                ans = max(ans, score)
                break
            ans = max(ans, score)
    print(ans)


main()

Submission status: Wrong Answer

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

# score[i][j] = i-th score, position when start from j
score = [[(-(10**9), j) for j in range(N)] for i in range(N+1)]
T = [0 for i in range(N)]
for i in range(1, N+1):
	for j in range(N):
		if T[j] > 0:
			continue
		(s,p) = score[i-1][j]
		next_p = P[p]
		score[i][j] = (s + C[next_p], next_p)
		if j == next_p:
			T[j] = i

if K <= N:
	print(max([max([s[i][0] for i in range(N)]) for s in score[1:K+1]]))
	exit()

ans = -(10 ** 9)
for i in range(N):
	t = T[i]
	S = score[t][i][0]
	if S > 0:
		base = S * (K // t)
		r = K % t
		ad = max([s[i][0] for s in score[:r + 1]])
		ans = max(ans, base + ad)
	else:
		ans = max(ans, max([s[i][0] for s in score[1:]]))
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()]
dp = {}
maxall = -10**10
for i in range(N):
    maxc = -10**10
    s = i
    tmpc = 0
    for j in range(2 * N):
        tmpc += C[s]
        if maxc < tmpc:
            maxc = tmpc
        if tmpc < 0:
            tmpc = 0
        s = P[s]
    if maxc > maxall:
        maxall = maxc
print(maxc)

Submission status: Wrong Answer

Solution code:
def solve(shoki):
    global n,k,p,c
    sude=[-1]*n
    sude[shoki]=0
    ten=[0]
    now=shoki
    ishuu_kai=0
    ishuu_ten=0
    for i in range(n):
        now=p[now]
        if(sude[now]<0):
            sude[now]=i+1
            ten.append(ten[-1]+c[now])
        else:
            ten.append(ten[-1]+c[now])
            ishuu_kai=i+1-sude[now]
            ishuu_ten=ten[-1]-ten[sude[now]]
            break
    if(ishuu_ten>0):
        now=shoki
        for i in range(ishuu_kai):
            ten[i]+=((k-i)//ishuu_kai)*ishuu_ten
            now=p[now]
    if(k>ishuu_kai):
        return max(ten[1:])
    else:
        return max(ten[1:k+1])


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=[]
for i in range(n):
    ans.append(solve(i))

print(max(ans))

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    uf = UnionFind(n)
    for i in range(n):
        uf.union(i, p[i]-1)
    G = [[] for _ in range(uf.group_count())]
    idx = 0
    st = set()
    for i in range(n):
        if not i in st:
            x = i
            while not x in st:
                G[idx].append(c[x])
                st.add(x)
                x = p[x] - 1
            idx += 1
    ans = max(c) #1回動かした時の最大
    for i in range(len(G)):
        sum_g = sum(G[i])
        tmp_k = k
        if sum_g > 0:
            tmp = sum_g * (tmp_k // len(G[i]))
            tmp_k %= len(G[i])
            csum = [0]
            for v in G[i]:
                csum.append(v)
            for v in G[i]:
                csum.append(v)
            for j in range(len(csum)-1):
                csum[j+1] += csum[j]
            tmp_tmp = 0
            for j in range(len(G[i])):
                for l in range(1, tmp_k+1):
                    if tmp_tmp < csum[j+l] - csum[j]:
                        tmp_tmp = csum[j+l] - csum[j]
            tmp += tmp_tmp
            if ans < tmp:
                ans = tmp
        else:
            tmp_k %= len(G[i])
            csum = [0]
            for v in G[i]:
                csum.append(v)
            for v in G[i]:
                csum.append(v)
            for j in range(len(csum)-1):
                csum[j+1] += csum[j]
            for j in range(len(G[i])):
                for l in range(1, tmp_k+1):
                    if ans < csum[j+l] - csum[j]:
                        ans = csum[j+l] - csum[j]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
*P, = map(int, input().split())
*C, = map(int, input().split())

P = [p-1 for p in P]

used = [0]*N
ans = -float('inf')
for x in range(N):
    if used[x]:
        continue
    used[x] = 1
    Q = [C[x]]

    while not used[P[x]]:
        x = P[x]
        used[x] = 1
        Q.append(C[x])

    M = len(Q)
    acc = list(accumulate(Q*2))
    if acc[M-1] > 0:
        ret = acc[M-1]*(K//M)
        ret += max(acc[K % M+i] - acc[i] for i in range(M))

    else:
        R = Q*2
        l = 0
        r = 0
        ret = -float('inf')
        while True:
            for i in range(r, M):
                if R[i] >= 0:
                    l = i
                    break
            else:
                break

            for j in range(l+1, 2*M):
                if R[j] < 0:
                    r = j
                    break
            else:
                break
            if l == 0:
                tot = acc[r-1]
            else:
                tot = acc[r-1] - acc[l-1]

            if tot > ret:
                ret = tot

    if ret > ans:
        ans = ret

print(ans if ans > -float('inf') else max(C))

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 = []
for u in range(N):
    v = P[u] - 1
    cnt = C[v]
    val = cnt
    jump = 1

    # Jump to limit or loop
    while u != v and jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    # Reduce residual to < K
    if jump < K:
        res = K // jump - 1
        cnt += cnt * res
        val = max(val, cnt)
        jump += jump * res

    # Residual steps
    v = u
    while jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    ans.append(val)

print(max(ans))

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()))
if max(c) <= 0:
    print(max(c))
    exit()
ans = 0
print(p)
for begin in range(n):
    i = p[begin]
    s = c[i]
    round = 1
    score = 0
    while i != begin:
        i = p[i]
        s += c[i]
        round += 1
    if s > 0 and k >= round:
        score += s * (k//round)
        kk = k - round * (k//round)
    elif k >= round:
        kk = round-1
    else:
        kk = k
    smax = 0
    now = 0
    i = begin
    while kk > 0:
        i = p[i]
        now += c[i]
        smax = max(now, smax)
        kk -= 1
    score += smax
    ans = max(ans, score)
    print('{} {} {} {} {} {}'.format(score, smax, round, kk, s, begin))

print(ans)