AtCoder Beginner Contest 175
翻译中…
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.
翻译中…
样例
Input #1
5 2
2 4 5 1 3
3 4 -10 -8 8
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$.
Input #2
2 3
2 1
10 -7
Output #2
13
Input #3
3 3
3 1 2
-1000 -2000 -3000
Output #3
-1000
We have to make at least one move.
Input #4
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
Output #4
29507023469
The absolute value of the answer may be enormous.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。