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: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    N, K = map(int, input().split())
    Ps = list(map(lambda x: int(x)-1, input().split()))
    Cs = list(map(int, input().split()))

    cycless = [[] for _ in range(N)]
    useds = [0] * N
    for no in range(N):
        if useds[no]: continue
        x = no
        while True:
            useds[x] = 1
            cycless[no].append(Cs[x])
            x = Ps[x]
            if x == no:
                break

#    for no in range(N):
#        print('# no:', no, '/ cycless[no]:', cycless[no], file=sys.stderr)

    ans = -float('inf')
    for no in range(N):
        if not cycless[no]: continue
        L = len(cycless[no])
        accCycles = list(accumulate([0]+cycless[no]+cycless[no]+cycless[no]))
        sumC = sum(cycless[no])
#        print('\n# no:', no, '/ sumC:', sumC, file=sys.stderr)
        if sumC > 0:
            num = K//L
            if num > 0:
                num -= 1
                if num == 0:
                    fr = 1
                else:
                    fr = 0
                score = -float('inf')
                for M in range(fr, (L + K%L)+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
                score += sumC * num
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        else:
            score = -float('inf')
            for M in range(1, (K if K <= L else L)+1):
                for st in range(L):
                    s = accCycles[st+M] - accCycles[st]
                    if s > score:
                        score = s
        if score > ans:
            ans = score
#        print('# no:', no, '/ score:', score, file=sys.stderr)

    print(ans)


solve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
p = LIST()
c = LIST()

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

ans = -inf
for i in range(n):
    visit = [inf]*n
    reg_score = [-inf]*n

    now = i
    count = 0
    score = 0
    while visit[now] == inf:
        visit[now] = count
        reg_score[now] = score
        count += 1
        now = p[now]
        score += c[now]

    x = visit[now]
    y = count - visit[now]
    X = reg_score[now]
    Y = score - reg_score[now]

    for j in range(n):
        if visit[j] == inf:
            continue
        if j != i and k >= visit[j]:
            tmp0 = reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)
        elif (k-x)//y>0:
            tmp0 = Y + reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    ans = -inf
    for si in range(n):
        cs = [0]
        i = si
        for _ in range(k):
            i = pp[i]
            cs.append(cs[-1] + cc[i])
            if i == si: break
        cur = max(cs[1:])
        if len(cs) < k + 1:
            d = len(cs) - 1
            c = k // d
            r = k - d * c
            cur1=cs[-1] * c + max(cs[:r+1])
            cur2=cs[-1]*(c-1)+max(cs)
            cur = max(cur,cur1,cur2)
        #print(cs)
        ans = max(ans, cur)
    print(ans)

inf=10**16
n,k=MI()
pp=LI1()
cc=LI()
solve()

Submission status: Accepted

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

cycles = []
seen = set()
for p in pp:
    i = p
    tmp = []
    while i not in seen:
        v = cc[i]
        tmp.append(v)
        seen.add(i)
        i = pp[i]
    if tmp:
        cycles.append(tmp)

ans = -float('inf')

def calc(resid, cycle):
    if resid == 0:
        return 0
    m = len(cycle)
    dp = [cycle[:]]
    for k in range(1, resid):
        tmp = [0] * m
        for j in range(m):
            tmp[j] = dp[k-1][j] + cycle[(j + k)%m]
        dp.append(tmp)
    mx_resid = max(map(max, dp))
    return mx_resid

for cycle in cycles:
    per_cycle = sum(cycle)
    m = len(cycle)
    if per_cycle > 0:
        cnt_cycle, resid = divmod(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)
        
        cnt_cycle = max(0, k // m - 1)
        resid = min(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)
    else:
        cnt_cycle = 0
        resid = min(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)


print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**20

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        if K==1:
            output=max(output,C[P[i]-1])
            continue

        while True:
            count+=1
            now=P[now]-1

            if now in st:
                count-=1
                break
    
            lst[i][count]=lst[i][count-1]+C[now]
            st.add(now)
            
            if count==K:
                break


        if lst[i][count]>0:
            m=max(lst[i][1:count+1])
            
            if K%count:
                p=max(lst[i][1:K%count+1])
                if p>0:
                    s=lst[i][count]*(K//count)+p
                else:
                    s=lst[i][count]*(K//count-1)+m
            else:
                s=lst[i][count]*(K//count-1)+m
        else:
            s=max(lst[i][1:count+1])
        
        output=max(output,s)

    print(output)

main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
p = lr()
c = lr()
visited = [True for i in range(n)]
ans = -inf

for i in range(n):
    if visited[i]:
        add_list = [i+1]
        visited[i] = False
        tmp = p[i]-1
        pre = 0
        while visited[tmp]:
            pre+=1
            visited[tmp] = False
            add_list.append(tmp+1)
            tmp = p[tmp]-1
        pre_ans = -inf
        length = len(add_list)
        a1 = [0]
        for m in range(2*length):
            a1.append(a1[-1]+c[add_list[m%length]-1])
        pre_total = a1[length]
        full_count = 0
        ret_ind = length

        for ind in range(1, ret_ind+1):
            for m in range(length):
                if ind <= k:
                    tmp = a1[m+ind]-a1[m]
                    pre_ans = max(pre_ans, a1[m+ind]-a1[m])
                    u = (k-ind) // length
                    if pre_total > 0:
                        tmp += (u*pre_total)
                    pre_ans = max(pre_ans, tmp)
        ans = max(ans, pre_ans)
print(ans)

Submission status: Accepted

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

data = [[0 for i in range(n+1)] for j in range(n)]
loop = [10**10 for i in range(n)]
for i in range(n):
    j = i
    for t in range(1,n+1):
        j = p[j]
        data[i][t] += data[i][t-1] + c[j]
        if j == i:
            loop[i] = min(loop[i],t)

ans = -10**10
#print(data)
#print([data[i][loop[i]] for i in range(n)])

for i in range(n):
    for j in range(1,min(n,k)+1):
        if j > loop[i]:break
        if data[i][loop[i]] <= 0:
            ans = max(ans,data[i][j])
        else:
            ans = max(ans,data[i][loop[i]]*((k-j)//loop[i])+data[i][j])

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N + 1))
        self._rank = [0] * (self.N + 1)
        self._size = [1] * (self.N + 1)

    def find(self, x):
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


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

    uf = UnionFind(N)
    for i, p in enumerate(P, 1):
        uf.union(i, p)

    ans = -float("inf")
    visited_cc = set()
    for i in range(1, N + 1):
        cc = uf.find(i)
        if cc in visited_cc:
            continue
        visited_cc.add(cc)

        CC = []
        j = P[i - 1]
        while True:
            CC.append(C[j - 1])
            if i == j:
                break
            j = P[j - 1]
        n_CC = len(CC)
        loop_cost = sum(CC)
        CC = list(accumulate([0] + CC * 2))

        if K < n_CC:
            cost = [-float("inf")] * n_CC
            for n_move in range(1, K + 1):
                for j in range(n_CC):
                    tmp = CC[j + n_move] - CC[j]
                    cost[n_move - 1] = max(cost[n_move - 1], tmp)
            res = max(cost)
        else:
            cost = [-float("inf")] * n_CC
            for n_move in range(1, n_CC):
                for j in range(n_CC):
                    tmp = CC[j + n_move] - CC[j]
                    cost[n_move - 1] = max(cost[n_move - 1], tmp)
            q, r = divmod(K, n_CC)
            if loop_cost > 0:
                if r > 0:
                    res = max(loop_cost * q + max(cost[:r]), loop_cost * (q - 1) + max(cost))
                else:
                    res = max(loop_cost * q, loop_cost * (q - 1) + max(cost))
            else:
                res = max(cost)

        ans = max(ans, res)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#from itertools import accumulate
#from itertools import combinations
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

#N,K = 4,4
#P = [2,3,4,1]
#C = [-9,9,1,-1]
#N = 5000
#K = 10**8
#P = [i+1 for i in range(1,5000)] + [1]
#C = [10**9] * N

visited = [False]*(N+1)
loops = []
for v in range(1,N+1):
    if visited[v]:
        continue
    l = [v]
    while True:
        v = l[-1]
        visited[v] = True
        nv = P[v-1]
        if visited[nv]:
            break
        l.append(nv)
    loops.append(l)

cand = []
for loop in loops:
    temp = 0
    vals = [C[i-1] for i in loop]
    l = len(vals)
    vals3 = vals+vals+vals[:-1]
    cumsum = [0]
    for v in vals3:
        cumsum.append(cumsum[-1] + v)
    gh = []
    #print(vals)
    if K <= l:
        temp = 0
        ma = min(vals)
        for left in range(0,2*l-K):
            for right in range(left+1,left+K+1):
                ma = max(ma,(cumsum[right] - cumsum[left]))
        temp += ma
    else:
        temp = 0
        s = sum(vals)
        q, r = divmod(K,l)
        q -= 1
        r += l
        ma = min(vals)
        for left in range(0,3*l-r):
            for right in range(left+1,left+r+1):
                ma = max(ma,(cumsum[right] - cumsum[left]))
        temp += ma
        if s > 0:
            temp += q * s
    cand.append(temp)
print(max(cand))