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:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

max_point = -(10**9)

for i in range(N):
    point = 0
    p_num = P[i]
    for j in range(K):
        point += C[p_num-1]
        p_num = P[p_num-1]
        if max_point < point:
            max_point = point            
print(max_point)

Submission status: Time Limit Exceeded

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

ans = -(10 ** 17)

for i in range(n):
    now = i
    cycle_sum = 0
    cycle_len = 0

    while True:
        cycle_sum += c[now]
        cycle_len += 1
        now = next[now]
        if now == i:
            break

    sum = 0
    cnt = 0

    while True:
        sum += c[now]
        cnt += 1

        if cnt > k:
            break

        laps = (k - cnt) // cycle_len
        score = sum + max(0, cycle_sum) * laps
        ans = max(ans, score)

        now = next[now]
        if now == i:
            break

print(ans)

Submission status: Time Limit Exceeded

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

ans = -(10 ** 17)

for i in range(n):
    now = i
    cycle_sum = 0
    cycle_len = 0

    while True:
        cycle_sum += c[now]
        cycle_len += 1
        now = next[now]
        if now == i:
            break

    sum = 0
    cnt = 0

    while cnt < k and cnt < cycle_len:
        sum += c[now]
        cnt += 1
        laps = (k - cnt) // cycle_len
        score = sum + max(0, cycle_sum) * laps
        ans = max(ans, score)

        now = next[now]
        if now == i:
            break

print(ans)

Submission status: Time Limit Exceeded

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

ans = -(10 ** 17)

for i in range(n):
    now = i
    cycle_sum = 0
    cycle_len = 0

    while True:
        cycle_sum += c[now]
        cycle_len += 1
        now = next[now]
        if now == i:
            break

    sum = 0
    cnt = 0

    while cnt < k:
        sum += c[now]
        cnt += 1
        laps = (k - cnt) // cycle_len
        score = sum + max(0, cycle_sum) * laps
        ans = max(ans, score)

        now = next[now]
        if now == i:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def D():
    N, K = map(int, input().split())
    P = [int(n) for n in input().split()]
    C = [int(n) for n in input().split()]
    cycle_sums = [float('-inf')]*N
    cycle_length = [-1]*N
    for i in range(N):
        # every element is guaranteed to be in a cycle
        if cycle_sums[i] == float('-inf'): #have not been processed, g
            points = 0
            visited_set = set()
            visited_order = []
            while P[i] not in visited_set:
                visited_set.add(P[i])
                visited_order.append(P[i])
                i = P[i]-1
            _sum = 0
            for j in range(len(visited_order)):
                _sum += C[visited_order[j]-1]
            for j in range(len(visited_order)):
                cycle_sums[visited_order[j]-1] = _sum
                cycle_length[visited_order[j]-1] = len(visited_order)
    #print(cycle_sums, cycle_length)

    ans = float('-inf')
    for j in range(N):
        i = j
        k = K
        points = 0
        if cycle_sums[i] > 0:
            num_cycles, remainder = divmod(k, cycle_length[i])
            if num_cycles > 0:
                num_cycles -= 1
                remainder += cycle_length[i]
            points += cycle_sums[i] * num_cycles
            k = remainder
        else:
            #make at least one move
            i = P[i]-1
            points += C[i]
            k = min(k, cycle_length[i]-1)
        #print(j, points)
        _sum = points

        while k > 0:
            i = P[i]-1
            _sum += C[i]
            points = max(points, _sum)
            k -= 1
        #print(j, points)
        ans = max(ans, points)

    return ans
        # visited_dict = {}
        # visited_order = []
        # while K > 0 and P[i] not in visited_dict:
        #     visited_dict[P[i]] = len(visited_order)
        #     visited_order.append(P[i])
        #     i = P[i]-1
        #     points += C[i]
        # if K > 0: #cycle found
        #     cycle_len = len(visited_order) - visited_dict(P[i])
        #     num_cycles_left, remainder = divmod(K, cycle_len)
        #     _sum = 0
        #     for j in range(visited_dict(P[i]), len(visited_order)):
        #         _sum += C[visited_order[j]]
        #         if j - visited_dict(P[i]) == remainder-1:
        #             points += _sum
        #     points += num_cycles_left*_sum

print(D())

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

a = [[] for i in range(n)]
ans = -1000000000

for i in range(n):
  x = i
  y = 0
  cg = []
  while True:
    y += c[x]
    cg.append(y)
    x = p[x] - 1
    if x == i:
      break

  if cg[-1] < 0:
    ans = max(ans, max(cg))
  else:
    ka = k // len(cg)
    kb = k % len(cg)
    if kb == 0:
      ans = max(ans, (ka - 1) * cg[-1] + max(cg))
    else:
      ans = max(ans, ka * cg[-1] + max(cg[0:kb]))
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()))

a = [[] for i in range(n)]
cg = [[] for i in range(n)]

for i in range(n):
  x = i
  y = 0
  while True:
    y += c[x]
    cg[i].append(y)
    x = p[x] - 1
    if x == i:
      break

ans = -1000000000
for i in cg:
  if i[-1] < 0:
    ans = max(ans, max(i))
  else:
    ka = k // len(i)
    kb = k % len(i)
    if kb == 0:
      ans = max(ans, (ka - 1) * i[-1] + max(i))
    else:
      ans = max(ans, ka * i[-1] + max(i[0:kb]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
(n,k),p,c,*a=[[*map(int,t.split())]for t in open(0)]
while n:
 n-=1;s,x,*l=0,n;f=j=k
 while f:x=p[x]-1;s+=c[x];l+=s,;f=x!=n
 for t in l[:k]:j-=1;a+=t+j//len(l)*s*(s>0),
print(max(a))

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 ** 9
for i in range(1, N + 1):
    start = i
    next_ = start
    loop_score = 0
    loop_count = 0
    while True:
        loop_count += 1
        loop_score += C[next_]
        next_ = P[next_]
        if next_ == start:
            break
    in_score = 0
    in_count = 0

    for k in range(K):
        in_count += 1
        in_score += C[next_]

        loop_num = (K - in_count) // loop_count
        score = in_score + max(0, loop_score) * loop_num
        ans = max(ans, score)

        next_ = P[next_]
        if next_ == start:
            break

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()))
p = list(map(lambda x: x - 1, p))

ans = -1 * 10 ** 18

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = -(1e9 + 5)
for i in range(N):
    x = i
    S = deque()
    s = 0
    while True:
        x = P[x] - 1
        S.append(C[x])
        s += C[x]
        if x == i:
            break
    l = len(S)
    a = 0
    for i in range(l):
        a += S[i]
        if i + 1 > K:
            break
        An = a
        if s > 0:
            An += s * ((K - i - 1) // l)
        A = max(A, An)
print(A)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

N, K, *PC = map(int, open(0).read().split())
P, C = [0] + PC[:N], [0] + PC[N:]

ans = float("-inf")
for start in range(1, N + 1):
    path = []

    cur = P[start]
    path = [C[start]]
    while cur != start:
        path.append(C[cur])
        cur = P[cur]

    A = list(accumulate(path))
    q, r = divmod(K, len(path))
    res = 0
    if A[-1] >= 0:
        if r == 0:
            q -= 1
            r += len(path)
        res += A[-1] * q
    elif q >= 1:
        r = len(path)

    ans = max(ans, res + max(A[:r]))

print(ans)

Submission status: Time Limit Exceeded

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

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * ((K//k)-1)
                NumberOfCycle = (K%k) + k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
P=[i-1 for i in P]
C=list(map(int,input().split()))
import math
ans=-10**18
for i in range(N):
  x=i
  tot=0
  cycle=[]
  while True:
    x=P[x]
    cycle.append(C[x])
    tot+=C[x]
    if x==i:
      break
  L=len(cycle)
  t=0
  for i in range(L):
    t+=cycle[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:
N,K= map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000

for i in range(N):
    S = []
    j = P[i]-1
    S.append(C[j])

    while i != j:
        j = P[j]-1
        S.append(S[-1] + C[j])

    if K <= len(S):
        score = max(S[:K])

    elif S[-1] <= 0:
        score = max(S)
    
    else:
        score1 = K//len(S) * S[-1]
        r = K%len(S)
        if r != 0:
            score1 += max(0, max(S[:r]))
        score2 = (K//len(S)-1)*S[-1] + max(S)
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

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

for sp in range(N):
    np = sp
    total = 0
    path = []
    
    while 1:
        np = P[np]
        path.append(C[np])
        total += C[np]
        if np == sp:
            break
    
    l = len(path)
    t = 0 
    for cl in range(l):
        t +=  path[cl]
        if cl+1 > K:
            break
        cur = t
        if total > 0:
            e = (K-(cl+1))//l
            cur += total * e
        ans = max(ans, cur)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=input().split()
N=int(N)
K=int(K)
P=input().split()
C=input().split()
for i in range(N):
    P[i]=int(P[i])-1
for i in range(N):
    C[i]=int(C[i])
ans=-1000000001
for i in range(N):
    x=0
    n=i
    sum=0
    period=0
    while period<=N:
        sum+=C[n]
        n=P[n]
        period+=1
        if n==i:
            break
    m=int(K/period)
    K2=K
    if m>1 and sum>0:
        x=(m-1)*sum
        K2-=(m-1)*period
    elif K2>N and sum<=0:
        K2=N
    for j in range(K2):
        x+=C[n]
        n=P[n]
        ans=max(ans,x)
        if j>=2*N:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))
    C = list(map(int, readline().split()))
    P = [i-1 for i in P]
    Position_list=[P]
    Score_list=[[0 for i in range(N)]]
    Max_list=[]

    for j in range(K):
        Updated_Position=[]
        Updated_Score=[]
        Current_Position=Position_list[j]
        Current_Score=Score_list[j]
        for i in range(N):
            Position=P[i]
            Updated_Position.append(Current_Position[Position])
            Updated_Score.append(Current_Score[i]+C[Current_Position[i]])
        Position_list.append(Updated_Position)
        Score_list.append(Updated_Score)
        Max_list.append(max(Score_list[j+1]))
   
    print(max(Max_list))
main()

Submission status: Time Limit Exceeded

Solution code:
N,K=input().split()
N=int(N)
K=int(K)
P=input().split()
C=input().split()
for i in range(N):
    P[i]=int(P[i])-1
for i in range(N):
    C[i]=int(C[i])
ans=-1000000001
for i in range(N):
    x=0
    n=i
    sum=0
    period=0
    while period<=N:
        sum+=C[n]
        n=P[n]
        period+=1
        if n==i:
            break
    m=int(K/period)
    K2=K
    if m>1 and sum>0:
        x=(m-1)*sum
        K2-=(m-1)*period
    elif K2>N and sum<=0:
        K2=N
    for j in range(K2):
        x+=C[n]
        n=P[n]
        ans=max(ans,x)
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    P = [i-1 for i in P]
    Position_list=[P]
    Score_list=[[0 for i in range(N)]]
    Max_list=[]

    for j in range(K):
        Updated_Position=[]
        Updated_Score=[]
        Current_Position=Position_list[j]
        for i in range(N):
            Position=P[i]
            Updated_Position.append(Current_Position[Position])
            Updated_Score.append(Score_list[j][i]+C[Current_Position[i]])
        Position_list.append(Updated_Position)
        Score_list.append(Updated_Score)
        Max_list.append(max(Score_list[j+1]))
   
    print(max(Max_list))
main()

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N, K = map(int, input().split())
P = [int(x) for x in input().split()]
p = [0 for _ in range(N)]
for i in range(N):
    p[i] = P[i] - 1
C = [int(x) for x in input().split()]

A = -INF
for i in range(N):
    s = []
    c = []
    l = [0]

    i = p[i]
    while i not in s:
        s.append(i)
        c.append(C[i])
        l.append(l[-1] + C[i])
        i = p[i]

    ls = len(s)
    if K < ls or l[-1] > 0:
        ans = l[-1]*(K//ls) + max(l[1:K%ls+1], default=0)

    else:
        ans = -float('inf')
        res = 0
        for _ in range(2):
            for j in range(ls):
                res += c[j]
                ans = max(ans, res)

    A = max(A, ans)
print(A)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
P = [i-1 for i in P]
Position_list=[P]
Score_list=[[0 for i in range(N)]]
Max_list=[]

for j in range(K):
    Updated_Position=[]
    Updated_Score=[]
    Current_Position=Position_list[j]
    for i in range(N):
        Position=P[i]
        Updated_Position.append(Current_Position[Position])
        Updated_Score.append(Score_list[j][i]+C[Position_list[j][i]])
    Position_list.append(Updated_Position)
    Score_list.append(Updated_Score)
    Max_list.append(max(Score_list[j+1]))
   
print(max(Max_list))

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

graphs = []
vGraphs = []
flags = [False]*n
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):
    index = ps[i] - 1
    value = cs[index]

    searchI = 0
    while True:
        vg = vGraphs[searchI]
        if value in vg:
            currentGraph = vg
            break
        searchI += 1

    total = sum(currentGraph)

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // len(currentGraph)
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
p = list(int(x)-1 for x in input().split())
c = list(map(int, input().split()))
score = -10**9
loop = [[] for _ in range(n+1)]
group = [0]*n
while 0 in group:
  i = group.index(0)
  here = i
  while group[i]==0:
    here = p[here]
    loop[i+1].append(here+1)
    group[here] = i+1
while [] in loop:
  loop.remove([])
for i in loop:
  s = [0]
  cc = []
  for j in i:
    s.append(s[-1]+c[j-1])
    cc.append(c[j-1])
  s.remove(0)
  l = k%len(s)
  resd = -10**9-1
  cum = -10**9-1
  cc = cc + cc[:-1]
  for j in range(len(s)):
    resd = max(sum(cc[j:j+l]),resd)
  for j in range(1,min(k,len(s))+1):
    for m in range(len(s)):
      cum = max(sum(cc[m:m+j]),cum)
  if s[-1]>0 and len(s)<k:
    sc = s[-1]*(k//len(s))+resd
  else:
    sc = cum
  score = max(sc,score)
print(score)

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

visited=[True for _ in range(N)]
tempv=[]
sets=[]
if sum(1 for i in C if i<=0)==N:
    print(max(C))
    exit()
i=0
total=0
while True:
    if visited[i]:
        visited[i]=False
        tempv.append(i)
        i=P[i]-1
        total+=1
    elif total==N:
        sets.append(tempv)
        tempv=[]
        break
    else:
        sets.append(tempv)
        tempv=[]
        for k in range(N):
            if visited[k]:
                i=k
                break


# print(sets)
nofsets=len(sets)
nax=0
for i in range(nofsets):
    tempv=[C[j] for j in sets[i]]
    length=len(tempv)
    quot=K//length
    if quot!=0:
        remainder=length
    else:
        remainder=K%length
    onecycle=sum(tempv)
    if onecycle<0:
        onecycle=0
    tempv=tempv+tempv
    for i in range(length):
        for j in range(remainder):
            total=sum([tempv[i+s] for s in range(j+1)])
            nax=max(nax,total+onecycle*((K-j-1)//length))
    


print(nax)

Submission status: Time Limit Exceeded

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

A = []

for i in range(N):
    s = []
    c = []
    l = [0]
    i = graph[i]
    while i not in s:
        s.append(i)
        c.append(C[i])
        l.append(l[-1] + C[i])
        i = graph[i]
    ls = len(s)

    if K <= ls:
        ans = max(l[1:K+1])
    else:
        if l[-1] > 0:
            ans = l[-1] * (K//ls)
            res = ans
            for j in range(K%ls):
                res += c[j]
                ans = max(ans, res)
        else:
            ans = -float('inf')
            res = 0
            for _ in range(2):
                for j in range(ls):
                    res += c[j]
                    ans = max(ans, res)

    A.append(ans)
print(max(A))

Submission status: Time Limit Exceeded

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

Position_list=[P]
Score_list=[[0 for i in range(N)]]
Max_list=[]

for j in range(K):
    Updated_Position=[]
    Updated_Score=[]
    Current_Position=Position_list[j]
    for i in range(N):
        Position=P[i]
        Updated_Position.append(Current_Position[Position])
        Updated_Score.append(Score_list[j][i]+C[Position_list[j][i]])
    Position_list.append(Updated_Position)
    Score_list.append(Updated_Score)
    Max_list.append(max(Score_list[j+1]))
   
print(max(Max_list))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
P=[int(a)-1 for a in input().split()]
C=[int(a) for a in input().split()]
ans=-10**30
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:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [None] + P
C = [None] + C

all_max = C[1]
for st in range(1, N + 1):
    scores = []
    visit = set()
    p = st

    while p not in visit and len(visit) < K:
        next_p = P[p]
        scores.append(C[next_p])
        visit.add(p)
        p = next_p

    num_elem = len(scores)
    all_sum = sum(scores)

    q, r = divmod(K, num_elem)

    max_ = scores[0]
    temp = scores[0]

    max_r = scores[0]
    temp_r = scores[0]
    for x in range(1, num_elem):
        if x < r:
            temp_r += scores[x]
            max_r = max(max_r, temp_r)

        temp += scores[x]
        max_ = max(max_, temp)

    temp_max = scores[0]
    if all_sum > 0 and q > 0:
        if r > 0:
            temp_max = max(all_sum * (q - 1) + max_, all_sum * q + max_r)
        else:
            temp_max = all_sum * (q - 1) + max_
    else:
        temp_max = max_

    all_max = max(all_max, temp_max)

print(all_max)

Submission status: Time Limit Exceeded

Solution code:
#import random

IN = list(map(int, input().split()))
N, K = IN[0], IN[1]
P = [None] + list(map(int, input().split()))
C = [None] + list(map(int, input().split()))
#N = 4500
#K = 10**9
#P = [None] + random.sample(range(1, N+1), k=N)
#C = [None] + random.choices(range(-10**9, 10**9), k=N)

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

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

maxsc = -10**9-1
done = [False] * (N+1)
for i in range(1, N+1):
    if verbose: print('entering', i)
    if done[i]: continue
    pos = i
    cnt = 0
    steps, scores = [0]*(N+N+N+N), [0]*(N+N+N+N)
    path = [False] * (N+1)
    while True:
        steps[cnt] = pos
        scores[cnt] = C[pos]
        pos = P[pos]
        cnt += 1
        if path[pos]:
            break # found closure
        else:
            path[pos] = True
    if verbose: print('closure found')
    st = steps.index(pos) # start of closure
    if verbose: print('closure steps identified')
    closure_path = steps[st:cnt]
    closure_scores = scores[st:cnt]
    closure_score = sum(closure_scores)
    preclosure_len = st
    score_len = 0
    if verbose: print('closure path:', closure_path)
    closure_len = len(closure_path)
    cycles = (K-preclosure_len-closure_len)//closure_len
    resid = (K-preclosure_len)%closure_len
    if cycles >= 1: cycles -= 1
    if cycles<1:
        score_len = K
    else:
        score_len = preclosure_len + closure_len + 1 + closure_len + resid
#        score_len = K - closure_len*cycles + 1
    if (cycles > 0):
        scores[cnt] = closure_score*cycles
        cnt+=1
    for j in range(closure_len*3):
        if cnt+j>=len(scores): break
        scores[cnt+j] = closure_scores[j%closure_len]
    if verbose: print('preclosure:', preclosure_len,
                      'cycle len', closure_len,
                      'cycles:', cycles, 'resid:', resid)
    if verbose: print(i, ':', scores)
    localmax = max(cumsum(scores[0:(score_len)]))
    maxsc = max(localmax, maxsc)
    if verbose: print(i, ': done with', localmax, 'score_len:', score_len)

    if verbose: print('going greedy')
    for j in range(1, closure_len):
        target = steps[j]
        if done[target]: continue
        localmax = max(cumsum(scores[j:(score_len+j)]))
        maxsc = max(localmax, maxsc)
        done[target] = True
        if verbose: print('done:', target, 'with', localmax)

print(maxsc)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, K = map(int, input().split(" "))
 
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))


max_points = []
heapq.heapify(max_points)
for now_point in range(2, N+1):
    max_point = -float('inf')
    C_point = 0
    max_point = []
    heapq.heapify(max_point)
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        
        heapq.heappush(max_point, -C_point)
        now_point = next_point
    
    max_point_ = heapq.heappop(max_point)
    heapq.heappush(max_points, max_point_)
 
print(-heapq.heappop(max_points))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, K = map(int, input().split(" "))
 
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))


max_points = []
heapq.heapify(max_points)
for now_point in range(2, N+1):
    max_point = -float('inf')
    C_point = 0
    for _ in range(K):
        next_point = Ps[now_point-1]
        C_point += Cs[next_point-1]
        if C_point > max_point:
            max_point = C_point
        now_point = next_point
    
    heapq.heappush(max_points, -max_point)
 
print(-heapq.heappop(max_points))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    # 全ての点を始点とした場合を考える(N通り)
    for start in range(N):
        # 始点を含むループを探す，スコアの累積和も勘定しておく
        now = start
        loop = []
        total = 0
        while now != start or not loop:
            loop.append(C[now])
            now = P[now]
            total += C[now]
        # ループごとの最大スコアを探す
        length = len(loop)
        t = 0
        for i in range(length):
            t += loop[i]
            # ループ長 > Kなら，ループ途中で探索終了
            if i + 1 > K:
                break
            # ループ長 <= Kなら，ループを周回するので
            # それを利用して探索を省略
            now = t
            if total > 0:
                e = (K - (i + 1)) // length
                now += total * e
            ans = max(ans, now)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
P = LIST()
C = LIST()

loop_point = [0]*N
loop_count = [0]*N
searched = [0]*N

for i in range(N):
	if searched[i]:
		continue
	idx = i
	points = 0
	cnt = 0
	while not searched[P[idx]-1]:
		idx = P[idx]-1
		searched[idx] = 1
		cnt += 1
		points += C[idx]
	loop_count[i] = cnt
	loop_point[i] = points

	while not loop_point[P[idx]-1]:
		idx_next = P[idx]-1
		loop_count[idx_next] = loop_count[idx]
		loop_point[idx_next] = loop_point[idx]
		idx = idx_next

ans = -INF
for i in range(N):
	p = 0
	idx = i
	loop = loop_point[i] > 0 and K > loop_count[i]
	for j in range(1, min(K+1, loop_count[i]+1)):
		idx = P[idx] - 1
		p += C[idx]
		if loop:
			final_p = p + loop_point[i]*((K-j)//loop_count[i])
		else:
			final_p = p
		ans = ans if ans > final_p else final_p
print(ans)