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: Runtime Error

Solution code:
n, k =map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
roop = []
seen = [0 for  _ in range(n)]
count = 0
for i in range(n):
    if seen[i]>0:
        continue
    else:
        count+=1
        seen[i] = count
        roop.append([c[i]])
        t = i
        while i!=p[t]-1:
            seen[p[t]-1]=count
            roop[-1].append(c[p[t]-1])
            t = p[t]-1
#print(seen)
#print(roop)
ans = max(c)

for i in roop:
    #print(ans)
    
    s = sum(i)
    ii = i+i
    #print(ii)
    if len(i)>=k:
        for j in range(1, k+1):
            temp = sum(ii[:j])
            for l in range(len(i)):
                if l!=0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                    #temp = sum(ii[l:l+j])
                #print(i, j, l, temp)
                ans  = max(ans, temp)
    else:
        for j in range(1, len(i)+1):
            temp=  sum(ii[:j])
            for l in range(len(i)):
                if l != 0:
                    temp+=ii[l+j-1]
                    temp-=ii[l-1]
                #print(temp)
                if s>0:
                    temp1 = temp+s*((k-j)//len(i))
                
                #print(i, j, l, temp)
                ans  = max(ans, temp)
                ans  = max(ans, temp1)
            
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))

def roop(i):
  if p[i]-1 not in visit:
    roopcnt.append(roopcnt[-1]+c[p[i]-1])
    global rooph
    rooph+=1
    visit.append(i)
    roop(p[i]-1)
  
l=[]
for i in range(n):
  visit=[i]
  roopcnt=[c[i]]
  rooph=1
  roop(i)
  roopcnt=roopcnt[1:]
  roopcnt.append(roopcnt[-1]+c[i])
  a=(k+1)%rooph
  b=(k+1)//rooph
  if sum(roopcnt)-c[i]>=0:
    if rooph<=k:
      if a!=0:
        l.append(b*roopcnt[-1]+max(roopcnt[:a])-c[i])
      else:
        l.append((b-1)*roopcnt[-1]+max(roopcnt)-c[i])
    else:
      l.append(max(roopcnt[:k])-c[i])
  else:
    if rooph<=k:
      l.append(max(roopcnt)-c[i])
    else:
      l.append(max(roopcnt[:k])-c[i])


print(max(l))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 4)

    def search_loop(now: int, loop: list):
        """iから探索を初めて，再びiに達するまでに通った点のスコアをリストとして返す"""
        seen[now] = True
        if now == i and loop:
            loops.append(loop)
            return
        loop.append(C[now])
        search_loop(P[now], loop)

    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    # ループを探す
    seen = [False] * N
    loops = []
    for i in range(N):
        if not seen[i]:
            search_loop(i, [])

    # ループごとの最大スコアを探す
    ans = -10 ** 9
    for loop in loops:
        length = len(loop)
        sum_loop = sum(loop)
        # ループ長よりも操作回数が多いか？，ループを周回すると得か？で場合分け
        res = 0 if sum_loop <= 0 else sum_loop * (K // length)
        limit = K if K <= length else K % length

        loop_temp = loop * 2  # loopリストに同じloopリストを接続する
        for i in range(length):
            lst = [res]
            # cal = res
            for k in range(limit):
                # cal += loop_temp[i + k]
                # ans = max(ans, cal)
                lst.append(lst[-1] + loop_temp[i + k])
            ans = max(ans, max(lst[1:]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
IN = list(map(int, input().split()))
N, K = IN[0], IN[1]
P = list(map(int, input().split()))
C = [None] + list(map(int, input().split()))

g = {}
for i in range(1, N+1): g.update({i: P[i-1]})

def cumsum(a):
    tmp = [0]
    for i in range(1, len(a)+1): tmp.append(a[i-1] + tmp[i-1])
    return tmp[1:]

maxsc = -10**9-1
for i in range(1, N+1):
    pos = i
    steps, scores = [], []
    path = set()
    while True:
        steps.append(pos)
        scores.append(C[pos])
        pos = g[pos]
        if pos in steps: break # found closure
    st = steps.index(pos) # start of closure
    closure_path = steps[st:]
    closure_score = scores[st:]
    closure_len = len(closure_path)
    cycles = int(K/closure_len)+1
    steps += closure_path * cycles
    scores += closure_score *cycles
    maxsc = max(max(cumsum(scores[0:K])), maxsc)

print(maxsc)

Submission status: Runtime Error

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


ans = -float('inf')
se = set()
for start in range(N):
    if start in se:
        continue
    now = start
    scores = []
    while True:
        if now == start:
            break
        se.add(now)
        scores += [C[now]]
        now = P[now]
    cyclelen = len(scores)
    cycle, residue = divmod(K, cyclelen)
    scores *= 3
    scores = list(itertools.accumulate(scores))
    st = SegmentTree(scores, max, -float('inf'))
    ans = max([ans] + [
        st.query(start2 + 1, start2 + min(K + 1, cyclelen)) - scores[start2]
        for start2 in range(cyclelen)
    ])
    scorelastcycle = scores[-1] * (cycle - 1) // 3
    if scorelastcycle > 0 and cycle > 0:
        d = 0
        for start2 in range(cyclelen):
            d = max(
                d,
                st.query(start2, start2 + cyclelen + residue + 1) -
                scores[start2])
        scorelastcycle += d
        ans = max(ans, scorelastcycle)
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
now=-100000000000
for i in range(1,n+1):
    retu=[]
    sum1=0
    sum2=0
    sum3=0
    max1=-1000000000000
    max2=-1000000000000
    flag=0
    x=i
    while(flag==0):
        x=p[x-1]
        sum1+=c[x-1]
        retu.append(c[x-1])
        if x==i:
            flag=1
    if n>=k:
        for j in range(k):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        ans=max1
    elif sum1<=0:
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        ans=max2
    else:
        w=k%len(retu)
        
        if w==0:
            w=len(retu)
        for j in range(w):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        if max1+sum1>max2:
            ans=sum1*(k-w)//len(retu)+max1
        else:
            ans=sum1*((k-w)//len(retu)-1)+max2
    now=max(now,ans)
print(now)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))

def roop(i):
  if p[i]-1 not in visit:
    roopcnt.append(roopcnt[-1]+c[p[i]-1])
    global rooph
    rooph+=1
    visit.append(i)
    roop(p[i]-1)
  
l=[]
for i in range(n):
  visit=[i]
  roopcnt=[c[i]]
  rooph=1
  roop(i)
  a=(k+1)%rooph
  b=(k+1)//rooph
  if roopcnt[-1]>=0:
    if a!=0:
      l.append(b*roopcnt[-1]+max(roopcnt[:a])-roopcnt[0])
    else:
      l.append((b-1)*roopcnt[-1]+max(roopcnt)-roopcnt[0])
  else:
    if rooph<=k:
      l.append(max(roopcnt))
    else:
      l.append(max(roopcnt[:k]))
print(max(l))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
now=-10000000000
for i in range(1,n+1):
    retu=[]
    sum1=0
    sum2=0
    sum3=0
    max1=-10000000000
    max2=-10000000000
    flag=0
    x=i
    while(flag==0):
        x=p[x-1]
        sum1+=c[x-1]
        retu.append(c[x-1])
        if x==i:
            flag=1
    if n>=k:
        for j in range(k):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        ans=max1
    elif sum1<=0:
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        ans=max2
    else:
        w=k%len(retu)
        
        if w==0:
            w=len(retu)
        for j in range(w):
            sum2+=retu[j]
            if sum2>max1:
                max1=sum2
        for j in range(len(retu)):
            sum3+=retu[j]
            if sum3>max2:
                max2=sum3
        if max1+sum1>max2:
            ans=sum1*(k-w)//len(retu)+max1
        else:
            ans=sum1*((k-w)//len(retu)-1)+max2
    now=max(now,ans)
print(now)

Submission status: Runtime Error

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


ans = -float('inf')
se = set()
for start in range(N):
    if start in se:
        continue
    now = start
    scores = []
    while True:
        if now in se:
            break
        se.add(now)
        scores += [C[now]]
        now = P[now]
    cyclelen = len(scores)
    cycle, residue = divmod(K, cyclelen)
    scores *= 2
    scores = list(itertools.accumulate(scores))
    st = SegmentTree(scores, max, -float('inf'))
    ans = max([ans] + [
        st.query(start2, start2 + K + 1) - scores[start2]
        for start2 in range(cyclelen)
    ])
    scorelastcycle = scores[-1] * cycle // 2
    if scorelastcycle > 0 and cycle > 0:
        d = 0
        for start2 in range(cyclelen):
            d = max(d, st.query(start2, start2 + residue + 1) - scores[start2])
        scorelastcycle += d
        ans = max(ans, scorelastcycle)
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))


def dfs(i):
    if 0 <= visited[i]:
        return
    visited[i] = idx
    cycle.append(i)
    global csum
    csum += C[i]
    dfs(P[i])


visited = [-1]*n
idx = 0
cycles = []
for i in range(n):
    if 0 <= visited[i]:
        continue
    cycle = []
    csum = 0
    dfs(i)
    cycles.append((cycle, csum))
    idx += 1


INF = 10**18
ans = -INF
for i in range(n):
    cycle, csum = cycles[visited[i]]
    cmem = len(cycle)

    if 0 < csum:
        a, b = divmod(k, cmem)
        scoreA = csum*a
        score = 0
        INF = 10**18
        scoreB = -INF
        for _ in range(b):
            i = P[i]
            score += C[i]
            if scoreB < score:
                scoreB = score
        X = scoreA+scoreB
    else:
        b = min(k, cmem)
        score = 0
        INF = 10**18
        X = -INF
        for _ in range(b):
            i = P[i]
            score += C[i]
            if X < score:
                X = score

    if ans < X:
        ans = X
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
# g = [[0]*(n) for _ in range(n)]
# A = [n]*n
# for i in range(n):
#     tmp = 0
#     idx = i
#     cnt = 0
#     set_ =set()
#     while cnt<n:
#         if C[idx] not in set_:
#             tmp += C[idx]
#             set_.add(C[idx])
#             g[i][cnt] = tmp
#             idx = P[idx]-1
#             cnt += 1
#         else:
#             p = len(set_)
#             A[i] = p
#             break
ans = -float('inf')

for i in range(n):
    S = []
    idx = P[i]-1
    S.append(C[idx])
    while idx != i:
        idx = P[idx]-1
        S.append(S[-1] +C[idx])
    v,w = k//len(S),k%len(S)
    if k<=len(S):
        val = max(S[:k])
    elif S[-1]<=0:
        val - max(S)
    else:
        val1 = S[-1] *(k//len(S)-1)
        val1 += max(S)
        val2 = S[-1]*(k//len(S))
        if w!=0:
            val2 += max(0,max(S[:w]))
        val = max(val1,val2)
    ans = max(ans,val)
# for i in range(n):
#     v,w = k//A[i],k%A[i]
#     if A[i]<k:
#         if g[i][A[i]-1]<=0:
#             val = max(g[i][:A[i]])
#         else:
#             val1 = (v-1)*g[i][A[i]-1]
#             val1 += max(g[i][:A[i]])
#             val2 = v*g[i][A[i]-1]
#             if w!=0:
#                 val2 += max(0,max(g[i][:w]))
#             val = max(val1,val2)
#     else:
#         val = max(g[i][:k])
#     ans = max(ans,val)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
# g = [[0]*(n) for _ in range(n)]
# A = [n]*n
# for i in range(n):
#     tmp = 0
#     idx = i
#     cnt = 0
#     set_ =set()
#     while cnt<n:
#         if C[idx] not in set_:
#             tmp += C[idx]
#             set_.add(C[idx])
#             g[i][cnt] = tmp
#             idx = P[idx]-1
#             cnt += 1
#         else:
#             p = len(set_)
#             A[i] = p
#             break
ans = -float('inf')

for i in range(n):
    S = []
    idx = P[i]-1
    S.append(C[idx])
    while idx != i:
        idx = P[idx]-1
        S.append(S[-1] +C[idx])
    v,w = k//len(S),k%len(S)
    if k<=len(S):
        val = max(S[:k])
    elif S[-1]<=0:
        val - max(S)
    else:
        val1 = S[-1] *(v-1)
        val1 += max(S)
        val2 = S[-1]*v
        if w!=0:
            val2 += max(0,max(S[:w]))
        val = max(val1,val2)
    ans = max(ans,val)
# for i in range(n):
#     v,w = k//A[i],k%A[i]
#     if A[i]<k:
#         if g[i][A[i]-1]<=0:
#             val = max(g[i][:A[i]])
#         else:
#             val1 = (v-1)*g[i][A[i]-1]
#             val1 += max(g[i][:A[i]])
#             val2 = v*g[i][A[i]-1]
#             if w!=0:
#                 val2 += max(0,max(g[i][:w]))
#             val = max(val1,val2)
#     else:
#         val = max(g[i][:k])
#     ans = max(ans,val)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
g = [[0]*(n) for _ in range(n)]
A = [n]*n
for i in range(n):
    tmp = 0
    idx = i
    cnt = 0
    set_ =set()
    while cnt<n:
        if C[idx] not in set_:
            tmp += C[idx]
            set_.add(C[idx])
            g[i][cnt] = tmp
            idx = P[idx]-1
            cnt += 1
        else:
            p = len(set_)
            A[i] = p
            break
ans = -float('inf')

for i in range(n):
    S = []
    idx = P[i]-1
    S.append(C[idx])
    while idx != i:
        idx = P[idx]-1
        S.append(S[-1] +C[idx])
    v,w = k//len(S),k%len(S)
    if k<=len(S):
        val = max(S[:k])
    elif S[-1]<=0:
        val - max(S)
    else:
        val1 = S[-1] *(v-1)
        val1 += max(S)
        val2 = S[-1]*v
        if w!=0:
            val2 += max(0,max(S[:w]))
        val = max(val1,val2)
    ans = max(ans,val)
# for i in range(n):
#     v,w = k//A[i],k%A[i]
#     if A[i]<k:
#         if g[i][A[i]-1]<=0:
#             val = max(g[i][:A[i]])
#         else:
#             val1 = (v-1)*g[i][A[i]-1]
#             val1 += max(g[i][:A[i]])
#             val2 = v*g[i][A[i]-1]
#             if w!=0:
#                 val2 += max(0,max(g[i][:w]))
#             val = max(val1,val2)
#     else:
#         val = max(g[i][:k])
#     ans = max(ans,val)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    def search_loop(now: int, loop: list):
        """iから探索を初めて，再びiに達するまでに通った点のスコアをリストとして返す"""
        seen[now] = True
        if now == i and loop:
            loops.append(loop)
            return
        loop.append(C[now])
        search_loop(P[now], loop)

    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    # ループを探す
    seen = [False] * N
    loops = []
    for i in range(N):
        if seen[i] is False:
            search_loop(i, [])

    # ループごとの最大スコアを探す
    ans = -10 ** 9
    for loop in loops:
        length = len(loop)
        sum_loop = sum(loop)
        # ループ長よりも操作回数が多く，ループを周回すると得な場合
        if K > length and sum_loop > 0:
            res = sum_loop * (K // length)
            limit = K % length
        # そうじゃない場合
        else:
            res = 0
            limit = K

        loop_temp = loop * 3  # loopリストに同じloopリストを接続する
        for k in range(1, limit + 1):
            for i in range(length):
                ans = max(ans, sum(loop_temp[i:i + k]) + res)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
def main():
    def search_loop(now: int, loop: list):
        """iから探索を初めて，再びiに達するまでに通った点のスコアをリストとして返す"""
        seen[now] = True
        if now == i and loop:
            loops.append(loop)
            return
        loop.append(C[now])
        search_loop(P[now], loop)

    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    # ループを探す
    seen = [False] * N
    loops = []
    for i in range(N):
        if seen[i] is False:
            search_loop(i, [])

    # ループごとの最大スコアを探す
    ans = -10 ** 9
    for loop in loops:
        length = len(loop)
        sum_loop = sum(loop)
        # ループ長よりも操作回数が多く，ループを周回すると得な場合
        if K > length and sum_loop > 0:
            res = sum_loop * (K // length)
            limit = K % length
        # そうじゃない場合
        else:
            res = 0
            limit = K

        loop_temp = loop * 2  # loopリストに同じloopリストを接続する
        for k in range(1, limit + 1):
            for i in range(length):
                ans = max(ans, sum(loop_temp[i:i + k]) + res)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = (int(x) for x in input().split())
P = list(int(x) - 1 for x in input().split())
C = list(int(x) for x in input().split())

ans = -1e18
for si in range(n):
    S = [C[si]]
    x = P[si]
    while x != si:
        S.append(S[-1] + C[x])
        x = P[x]
    m = len(S)
    if k <= m:
        tmp = max(S[:k])
    else:
        loop = k // m
        r = k % m
        tmp = max(S[-1] * loop + max(S[:r]), S[-1] * (loop - 1) + max(S), max(S))
    ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
  
using namespace std;
 
#define endl "\n"
#define JAM(x) cout<< #x <<" = "<<x<<"\n"
#define II() ( { int a ; read(a) ; a; } )
#define LL() ( { ll a ; read(a) ; a; } )
#define DD() ({double a; scanf("%lf", &a); a;})
 
 
//Fast Reader
template<class T>inline bool read(T &x){
    int c=getchar();int sgn=1;
    while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}
    for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; 
    x*=sgn; return ~c;
}
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPI;
 
const int INF=2e9;
const int MX=100005;
const int MOD=1000000007;
const double PI=acos(-1.0);
 
long long int power(long long int a,long long int b)
{
    a %= MOD;
    long long int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
 
/*_______________________________________________*/


int main()
{
    long long int n,i,j,k,temp,ans=LLONG_MIN,temp1;
    cin>>n>>k;
    vector<long long int > perm(n),C(n);
    for(i=0;i<n;i++)
    cin>>perm[i];
    for(i=0;i<n;i++)
    cin>>C[i];
    for(i=0;i<n;i++)
    {
        temp1=0;
        int cur=i;
        unordered_map<long long int ,long long int> mp,mp1;
        for(temp=1;temp<=k;temp++)
        {
            if(mp.find(cur)!=mp.end())
            {
                temp1=k/(temp-1)*temp1;
                temp1+=mp1[k%(temp-1)];
                ans=max(ans,temp1);
                break;
            }
            temp1+=C[perm[cur]-1];
            mp[cur]=temp1;
            mp1[temp]=temp1;
            cur=perm[cur]-1;
            ans=max(ans,temp1);
        }
        ans=max(ans,temp1);
    }
    cout<<ans;
}

Submission status: Runtime Error

Solution code:
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<=sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
kara=[-10000000000]
if n>k:
    for i in range(1,n+1):
        kara.append(find(i,i,k,c[p[i-1]-1],0,0,0)[0])
    result=max(kara)
else:
    for i in range(1,n+1):
        m=find(i,i,n,c[p[i-1]-1],0,0,0)
        if m[1]<=0:
            if m[0]>kara[0]:
                kara[0]=m[0]
        else:
            w=k%m[2]
            if w==0:
                w=m[2]
            spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
            if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>kara[0]:
                kara[0]=m[1]*(k-w)//m[2]+spe
            elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>kara[0]:
                kara[0]=m[1]*((k-w)//m[2]-1)+m[0]
    result=kara[0]
print(result)

Submission status: Runtime Error

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

ans = -10**18

for start in range(N):
    x = start
    s = []
    total = 0
    while True:
        x = P[x]
        s.append(x)
        total += C[x]
        if x == start:
            break #周期判定

    l = len(s)
    now = 0
    for i in range(l):
        now += s[i]
        if i+1 > k:
            break
        if total > 0:
            e = (K - i - 1)//l
            now += total * e
        ans = max(ans, now)

print(ans)

Submission status: Runtime Error

Solution code:
#import sys

import numpy as np


def main(n,k,p,c):
    ans = -10**9
    for i in range(n):
        x = i
        t = k
        count = 0
        l = True
        sub = 0
        ln = 0
        while True:
            x = p[x] - 1
            if l:
                count += c[x]
                ln += 1
                if x == i:
                    if t > ln:
                        if count > 0:
                            sub += (t // ln - 1) * count
                            t %= ln
                            t += ln
                        else:
                            t = 0
                    l = False
            sub += c[x]
            t -= 1
            ans = max(sub, ans)
            if t < 1:
                break
    return ans


# >>> numba compile >>>
#if sys.argv[-1]=='ONLINE_JUDGE':
#  from numba.pycc import CC
#  cc=CC('my_module')
#  cc.export('main','i8(i8,i8,i8[:],i8[:])')(main)
#  cc.compile()
#  exit()
#from my_module import main
# <<< numba compile <<<
(n, k), p, c = [np.int_(i.split()) for i in open(0)]
print(main(n,k,p,c))

Submission status: Runtime Error

Solution code:
import sys

import numpy as np


def main(n,k,p,c):
    ans = -10**9
    for i in range(n):
        x = i
        t = k
        count = 0
        l = True
        sub = 0
        ln = 0
        while True:
            x = p[x] - 1
            if l:
                count += c[x]
                ln += 1
                if x == i:
                    if t > ln:
                        if count > 0:
                            sub += (t // ln - 1) * count
                            t %= ln
                            t += ln
                        else:
                            t = 0
                    l = False
            sub += c[x]
            t -= 1
            ans = max(sub, ans)
            if t < 1:
                break
    return ans


# >>> numba compile >>>
#if sys.argv[-1]=='ONLINE_JUDGE':
#  from numba.pycc import CC
#  cc=CC('my_module')
#  cc.export('main','i8(i8,i8,i8[:],i8[:])')(main)
#  cc.compile()
#  exit()
#from my_module import main
# <<< numba compile <<<
(n, k), p, c = [np.int_(i.split()) for i in open(0)]
print(main(n,k,p,c))

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np


def solve(n,k,p,c):
    ans = -10**9
    for i in range(n):
        x = i
        t = k
        count = 0
        l = True
        sub = 0
        ln = 0
        while True:
            x = p[x] - 1
            if l:
                count += c[x]
                ln += 1
                if x == i:
                    if t > ln:
                        if count > 0:
                            sub += (t // ln - 1) * count
                            t %= ln
                            t += ln
                        else:
                            t = 0
                    l = False
            sub += c[x]
            t -= 1
            ans = max(sub, ans)
            if t < 1:
                break
    return ans


# >>> numba compile >>>
if sys.argv[-1]=='ONLINE_JUDGE':
  from numba.pycc import CC
  cc=CC('my_module')
  cc.export('solve','i8(i8,i8,i8[:],i8[:])')(main)
  cc.compile()
  exit()
from my_module import main
# <<< numba compile <<<
(n, k), p, c = [np.int_(i.split()) for i in open(0)]
print(solve(n,k,p,c))