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: Time Limit Exceeded

Solution code:
from itertools import accumulate


def mod_max(loop, mod):
    if mod == 0:
        return 0
    return max(max(accumulate((loop[i:] + loop[:i])[:mod])) for i in range(len(loop)))


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(loop)

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

P = list(map(lambda x:x-1, P))

ans = -float('inf')
for si in range(N):
    s = []
    tot = 0
    x = si
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x==si:
            break
    l = len(s)
    now = 0
    t = 0
    for i in range(l):
        if i+1 > K: break
        t += s[i]
        now = t
        if tot >0:
            e = (K-(i+1))//l
            now += tot * e
        ans = max(ans, now)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,k = nm()
p = nl()
c = nl()

for i in range(n):
  p[i]-=1

ans = -10**(18)
for si in range(n):
  x = si
  s = []
  tot = 0
  while(True):
    x = p[x]
    s.append(c[x])
    tot += c[x]
    if x == si:
      break
  l = len(s)
  t = 0
  for i in range(l):
    t += s[i]
    if i+1>k:
      break
    now = t
    if tot > 0:
      e = (k-(i+1))//l
      now += tot*e
    ans = max(ans,now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import numpy as np


@lru_cache()
def mod_max(loop, mod):
    if mod == 0:
        return 0
    loop = np.array(loop)
    loop_len = loop.size
    sheet = np.zeros((mod, loop_len * 2), dtype=int)
    for i in range(mod):
        sheet[i:, i:i + loop_len] += loop
    return np.max(sheet[:, :loop_len] + sheet[:, loop_len:])


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(tuple(loop))

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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] = P[i] - 1

ans = -10**18
for i in range(N):
    s = []
    x = i
    while True:
        x = P[x]
        s.append(C[x])
        if x == i:
            break
    leng = len(s)
    total = sum(s)
    t = 0
    for j in range(leng):
        t += s[j]
        if j + 1 > K:
            break
        now = t
        if total > 0:
            e = (K - (j + 1)) // leng
            now += total*e
        ans = max(ans, now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def mod_max(loop, mod):
    if mod == 0:
        return 0
    loop_len = len(loop)
    mm = min(loop)
    sheet = np.zeros(loop_len * 2, dtype=int)
    for i in range(mod):
        sheet[i:i + loop_len] += loop
        mm = max(max(sheet[:loop_len] + sheet[loop_len:]), mm)
    return mm


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(np.array(loop))

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = loop.sum()
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    N, K = map(int, input().split())
    P = map(int, input().split())
    P = [x - 1 for x in P]
    P = np.array(P)
    C = np.array(input().split(), np.int64)
    ans = -(10 ** 18)
    for i in range(N):
        j = i
        S = 0
        L = 0
        for _ in range(K):
            j = P[j]
            S += C[j]
            L += 1
            ans = max(ans, S)
            if j == i:
                break
        if j == i:
            M = max(0, K // L - 1)
            T = S * M
            for _ in range(M * L, K):
                j = P[j]
                T += C[j]
                ans = max(ans, T)
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def mod_max(loop, mod):
    if mod == 0:
        return 0
    loop_len = len(loop)
    mm = min(loop)
    for start in range(loop_len):
        current_sum = 0
        for i in range(mod):
            current_sum += loop[(start + i) % loop_len]
            mm = max(current_sum, mm)
    return mm


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(loop)

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

        def find(self, x):
            if self.par[x] < 0:
                return x
            else:
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.par[x] > self.par[y]:
                x, y = y, x

            self.par[x] += self.par[y]
            self.par[y] = x

        def size(self, x):
            return -self.par[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ps = list(map(int, input().split()))
cs = list(map(int, input().split()))
memo = [[0]*(n+1)for _ in range(n+1)]

for i in range(1,n+1):
    memo[i][0] = [i,0]

to_do = []
res = -float('inf')
for i in range(1,n+1):
    tmp_dic = {i:(0,0,i)}
    for j in range(1,n+1):
        tmp_idx,tmp_val = ps[memo[i][j-1][0]-1],memo[i][j-1][1]+cs[ps[memo[i][j-1][0]-1]-1]
        memo[i][j] = [tmp_idx,tmp_val]
        res = max(res,tmp_val)
        if tmp_idx not in tmp_dic:
            tmp_dic[tmp_idx] = (j,tmp_val,tmp_idx)
        else:
            if tmp_val > tmp_dic[tmp_idx][1]:
                to_do.append([i,tmp_dic[tmp_idx][0],tmp_dic[tmp_idx][2],tmp_dic[tmp_idx][1],j-tmp_dic[tmp_idx][0],tmp_val-tmp_dic[tmp_idx][1]])
            else:
                break

if k <= n:
    print(res)
else:
    for do in to_do:
        itr = (k - do[1]) // do[4]
        remain = k - do[1] - do[4] * itr
        tmp_res = do[3] + itr * do[5]
        res = max(res,tmp_res)
        now = do[2]
        for i in range(remain):
            now = ps[now-1]
            tmp_res += cs[now-1]
            res = max(res, tmp_res)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        starts = [s]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            starts.append(v)
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        base = max(0, loop * d)

        for s in starts:
            v = ppp[s]
            score = base + ccc[ppp[s]]
            best_score = score
            for _ in range(m - 1):
                score += ccc[ppp[v]]
                v = ppp[v]
                best_score = max(best_score, score)
            ans = max(ans, best_score)

    return ans


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

print(solve(n, k, ppp, ccc))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P = [x - 1 for x in P]
    C = list(map(int, input().split()))
    ans = -(10 ** 18)
    for i in range(N):
        j = i
        S = 0
        L = 0
        for _ in range(K):
            j = P[j]
            S += C[j]
            L += 1
            ans = max(ans, S)
            if j == i:
                break
        if j == i:
            M = max(0, K // L - 1)
            T = S * M
            for _ in range(M * L, K):
                j = P[j]
                T += C[j]
                ans = max(ans, T)
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,k = readInts()
p = [0]+readInts()
c = [0]+readInts()

ans = -1*float("inf")
for i in range(1,n+1):
  j = p[i]
  t = [0]
  al = set()
  while j not in al:
    t.append(t[-1]+c[j])
    al.add(j)
    j = p[j]
  if t[-1]<=0:
    ans = max(ans, max(t[1:k+1]))
  else:
    kuri =(k-1)//(len(t)-1)
    s = kuri*t[-1]
    re = k -kuri*(len(t)-1)
    ans = max(ans, max(s,s+max(t[:re+1])))

print(ans)

Submission status: Time Limit Exceeded

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

ans = - 10 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt = p[nxt]
    nxt_tmp = nxt
    for j in range(min(extra, cnt)):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    #print("score = ", score, "ans = ", ans)
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    if extra % cnt == 0:
        a -= 1
    score += score * max(a, 0)
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

n,k = input().split(" ")
n,k = int(n), int(k)
P = input()
P = P.split(" ")
P = [int(x) for x in P]
C = input()
C = C.split(" ")
C = [int(x) for x in C]

score_list = []
for i in range(n):
    # print("i {}", i)
    score = 0
    p_ = P[i]
    for t in range(k):
        score += C[p_-1]
        score_list.append(score)
        p_ = P[p_-1]
        # print(score)

print(max(score_list))

Submission status: Time Limit Exceeded

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

ans = -1e18
for i in range(n):
  cur = p[i]
  loop = [c[cur]]
  cnt = 1
  ans = max(ans,c[cur])
  while cur != i and cnt<k:
    cur = p[cur]
    tmp = loop[-1]+c[cur]
    loop.append(tmp)
    ans = max(ans,tmp)
    cnt += 1
  #print(loop)
  if cnt==k or loop[-1]<=0:continue
  a = k//len(loop) * loop[-1]
  b = (k//len(loop)-1) * loop[-1]
  ans = max(ans,a,b)
  for _ in range(k%len(loop)):
    a += c[cur]
    ans = max(ans,a)
    cur = p[cur]
  cur = i
  for _ in range(len(loop)):
    b += c[cur]
    ans = max(ans,b)
    cur = p[cur]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [x - 1 for x in P]
C = list(map(int, input().split()))
ans = -(10 ** 18)
for i in range(N):
    j = i
    S = 0
    L = 0
    for _ in range(K):
        j = P[j]
        S += C[j]
        L += 1
        ans = max(ans, S)
        if j == i:
            break
    if j == i:
        M = max(0, K // L - 1)
        T = S * M
        for _ in range(M * L, K):
            j = P[j]
            T += C[j]
            ans = max(ans, T)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
(n, k), p, c = [[*map(int, i.split())] for i in open(0)]
 
def solve(x, t):
    visit = [0] * n
    visit[x] = 1
    loop = [0] * n
    count = 0
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        x = p[x] - 1
        if l:
            if visit[x]:
                if loop[x]:
                    ln = sum(loop)
                    if t > ln:
                        sub += (t//ln -1)*count*(count>0)
                        t %= ln
                        t += ln
                    l = False
                count += c[x]
                loop[x] = 1
            visit[x] = 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)
        if t < 1:
            return ans
 
 
print(max(solve(i, k) for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np


def solve(n,k,p,c):
    ans = -10**9
    for x in range(n):
        t = k
        visit = [0] * n
        visit[x] = 1
        loop = [0] * n
        count = 0
        l = True
        sub = 0
        while True:
            x = p[x] - 1
            if l:
                if visit[x]:
                    if loop[x]:
                        ln = sum(loop)
                        if t > l:
                            sub += (t // ln - 1) * count * (count > 0)
                            t %= ln
                            t += ln
                        l = False
                    count += c[x]
                    loop[x] = 1
                visit[x] = 1
            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))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]+readInts()
c = [0]+readInts()

past = [False]*(n+1)
ans = -1-float("inf")
for i in range(1,n+1):
	j = p[i]
	if past[j]: continue
	past[j] = True
	t = [0]
	al = []
	while j not in al:
		t.append(t[-1]+c[j])
		al.append(j)
		j = p[j]
	if t[-1]<0:
		ans = max(ans, max(t[1:k+1]))
	else:
		kuri = k//(len(t)-1)
		s = kuri*t[-1]
		ans = max(ans, max(s,s+max(t[:k-kuri*(len(t)-1)+1])))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n , k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
loop = []
visit = [False for i in range(n)]
for i in range(n):
    if visit[i]:
        continue
    tyu  = [i]
    now = i
    visit[i] = True
    while True:
        nex = p[now] - 1
        if nex == i:
            break
        visit[nex] = True
        tyu.append(nex)
        now = nex
    loop.append(tyu)

ans = []

for p in loop:
    kouho = []
    losum = 0
    lokz = len(p)
    kar = []
    for i in p:
        losum += c[i]
        kar.append(c[i])
    if losum > 0:
        kouho.append(losum*(k//lokz))
        for i in range(lokz):
            for j in range(lokz):
                if i < j:
                    amari = j - i
                    if amari <= k:
                        cou = losum*((k-amari)//lokz) + sum(kar[i:j])
                elif i == j:
                    continue
                elif i > j:
                    amari = lokz - (i-j)
                    if amari <= k:
                        cou = losum*((k-amari)//lokz) + sum(kar[:j]) + sum(kar[i:])
                kouho.append(cou)
    elif losum <= 0:
        for i in range(lokz):
            for j in range(lokz):
                if i <= j:
                    amari = j - i
                    if amari <= k:
                        cou = sum(kar[i:j+1])
                elif i > j:
                    amari = lokz - (i-j)
                    if amari <= k:
                        cou = sum(kar[:j+1]) + sum(kar[i:])
                kouho.append(cou)
    ans.append(max(kouho))
print(max(ans))

Submission status: Time Limit Exceeded

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

def check(cir,num):
    ans = -10**20
    l = len(cir)
    for start in range(l):
        a = 0
        for i in range(num):
            if start+i == l:
                start = -i
            a += cir[start + i]
            ans = max(ans,a)
    return ans

n,k = readints()
p = [x-1 for x in readints()]
c = readints()

circles = []
used = [0]*n

for i in range(n):
    if not used[i]:
        circles.append([c[i]])
        used[i] = 1
        j = p[i]
        while not used[j]:
            circles[-1].append(c[j])
            used[j] = 1
            j = p[j]

score = -10**20

for cir in circles:
    m = len(cir)
    a = sum(cir)
    if k>m:
        if a>0:
            score = max(score, (k//m)*a + check(cir,k%m), (k//m-1)*a + check(cir,m))
        else:
            score = max(score,check(cir,m))
    else:
        score = max(score,check(cir,k))

print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]
p.extend(readInts())
c = [0]
c.extend(readInts())

past = [False]*(n+1)
ans = -1*float("inf")
for i in range(1,n+1):
	j = p[i]
	if past[j]: continue
	past[j] = True
	t = [0]
	al = []
	while j not in al:
		t.append(t[-1]+c[j])
		al.append(j)
		j = p[j]
	if t[-1]<0:
		ans = max(ans, max(t[1:k+1]))
	else:
		kuri = k//(len(t)-1)
		s = kuri*t[-1]
		ans = max(ans, max(s,s+max(t[:k-kuri*(len(t)-1)+1])))

print(ans)

Submission status: Time Limit Exceeded

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

ans = -float('inf')
for th in range(1, k + 1):
	scores = []
	for i in range(n):
		loop = 0
		score = 0
		index = i
		while th > loop:
			score += c[p[index] - 1]
			loop += 1
			index = p[index] - 1
		scores.append(score)
	ans = max([ans, max(scores)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main(N, K, P, C):
    if sum([c <= 0 for c in C]) == len(C):  # すべて負の場合だけ例外処理
        print(max(C))
        exit()

    '''
    get_sum()
    何回も総和をとるとメモリきつそうだったのでメモ再帰化てきな処理してみた．
    s: 総和の始点
    l: 総和の終点 (その点は含まない e.g. s = 1, l = 2のときは1番目のやつだけ)
    '''
    def get_sum(s, l, lst, dic, max_lst): # メモ再帰化的な？
        # リストの長さ越えちゃうときにリスト内の値に変換する関数 (循環させてるイメージ)
        return_index_s = lambda x:x if x < len(lst) else x-len(lst)
        return_index_l = lambda x:x if x <= len(lst) else x-len(lst)

        # 再帰用の辞書のキー
        key = str(return_index_s(s))+'to'+str(return_index_l(l))

        if l - s == 1:  # 1個だけを足すとき (=まだ再帰化が行えないとき)
            dic[key] = C[lst[return_index_s(s)]]
        elif key not in dic:
            dic[key] = dic[str(return_index_s(s+1))+'to'+str(return_index_l(l))] + C[lst[return_index_s(s)]]

        # サイクルのあまりがそれぞれの数だったときに取れる最大値 (1個しかえらべないときが0番目に入ってて，2個しか選べないときが1番目...)
        max_lst[l-s-1] = max(max_lst[l-s-1], dic[key])
        return dic, max_lst # メモ再帰用


    # *** サイクルごとに分割 (必ずループに入るので，) ***
    st = {i for i in range(N)}
    circ = []

    for i in range(N):
        lst = []
        j = i
        while j in st:
            st.discard(j)
            lst.append(j)
            j = P[j] - 1
        else:
            if len(lst) != 0:
                circ.append(lst)
    # ********************************************

    # すべての組み合わせを探索
    ans = []    # 答えの候補となる， それぞれのサイクルでの最大値を保存しとくリスト
    for lst in circ:    # それぞれのサイクルについて
        dic = {}    # メモ再帰用の初期辞書
        if len(lst) <= K:    # サイクルを一回以上回せる (すきなところを選べる) 場合
            max_lst = [-float('inf') for _ in range(len(lst))]  # max_lstの初期リスト
            for i in range(1, len(lst)):   # サイクルのうち何個足すか
                for j in range(len(lst)):    # サイクルの始点をどこにするか
                    dic, max_lst = get_sum(j, j+i, lst, dic, max_lst)
            sum_all = 0
            for l in lst:
                sum_all += C[l]
            max_lst[-1] = sum_all
            shou = K // len(lst)    # 最大何周できるか
            amari = K % len(lst)    # 最大周回したときに余力で動けるマス数
            def f():
                memo = max_lst[:amari+1]
                memo[-1] = 0
                return max(memo)

            ans.append(max(max(sum_all, 0) * (shou - 1) + max(max_lst), max(sum_all, 0) * shou + f()))
            '''
            一番外のmax関数で比較している二つ
            前者：一周だけ減らして適度なとこで止める or サイクル回すと負になっちゃうケース
            後者：回せるだけ回して，余力も最大を選ぶ
            '''
        else:   # サイクル一回を回せない場合
            max_lst = [-float('inf') for _ in range(K)]   # max_lstの初期リスト
            for i in range(1, K+1):   # サイクルのうち何個足すか
                for j in range(len(lst)):    # サイクルの始点をどこにするか
                    dic, max_lst = get_sum(j, j+i, lst, dic, max_lst)
            ans.append(max(max_lst)) # 限られたマス数のなかで一番大きいスコアを返す．
    print(max(ans))



if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    main(N, K, P, C)

Submission status: Time Limit Exceeded

Solution code:
(n, k), p, c = [[*map(int, i.split())] for i in open(0)]

def solve(x, t):
    visit = [0] * n
    visit[x] = 1
    loop = [0] * n
    count = 0
    ans = c[p[x] - 1]
    l = True
    sub = 0
    while True:
        x = p[x] - 1
        if l:
            if visit[x]:
                if loop[x]:
                    ln = sum(loop)
                    if t > l:
                        sub += (t//ln -1)*count*(count>0)
                        t %= ln
                        t += ln
                    l = False
                count += c[x]
                loop[x] = 1
            visit[x] = 1
        sub += c[x]
        t -= 1
        ans = max(sub, ans)
        if t < 1:
            return ans


print(max(solve(i, k) for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]
p.extend(readInts())
c = [0]
c.extend(readInts())

ans = -1*float("inf")
for i in range(1,n+1):
	t = [0]
	al = []
	j = p[i]
	while j not in al:
		t.append(t[-1]+c[j])
		al.append(j)
		j = p[j]
	if t[-1]<0:
		ans = max(ans, max(t[1:k+1]))
	else:
		kuri = k//(len(t)-1)
		s = kuri*t[-1]
		ans = max(ans, max(s,s+max(t[:k-kuri*(len(t)-1)+1])))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math
import bisect

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]
p.extend(readInts())
c = [0]
c.extend(readInts())

score = [[0]]
for i in range(1,n+1):
	t = [0]
	al = []
	j = p[i]
	while j not in al:
		t.append(t[-1]+c[j])
		al.append(j)
		j = p[j]
	score.append(t)

ans = -1*float("inf")
for i in range(1,n+1):
	tar = score[i]
	if tar[-1]<0:
		ans = max(ans, max(tar[1:k+1]))
	else:
		kuri = k//(len(tar)-1)
		t = kuri*tar[-1]
		ans = max(ans, max(t,t+max(tar[:k-kuri*(len(tar)-1)+1])))

print(ans)