4657 . 最大連續和

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

給你一個正整數$N$，以及一個長度是$N$的整數數列$a_0, a_1, a_2, \cdots , a_{N - 1}$，以及函數$f \colon \{ 0, 1, 2, \cdots , N - 1 \} \to \{ 0, 1, 2, \cdots , N - 1 \}$。對每個整數$k = 0, 1, 2, \cdots , N - 1$，請求出數列$a_k, a_{f(k)}, a_{f(f(k))}, a_{f^ {3} (k)}, a_{f^ {4} (k)} \cdots$的連續子序列（長度可能是$0$，有限或無限）的各項總和的最大值？

註：對於非負整數$m$，$f^ {m} $是函數$f$的$m$次迭代，也就是$f^ {0} (k) = k$，對於任意非負整數$m$，均有$f^ {m + 1} (k) = f(f^ {m} (k))$。

Input Format

每筆測資第零行是一個整數$N$
第一行是$N$個整數，以空格分開，依序是$a_0, a_1, a_2, \cdots , a_{N - 1}$
第二行是$N$個整數，以空格分開，依序是$f(0), f(1), f(2), \cdots , f(N - 1)$

$1 \le N \le 10^ {5} $
$\forall 0 \le i \le N - 1, -10^ {9} \le a_i \le 10^ {9}, 0 \le f(i) \le N - 1$

Output Format

輸出$N$行，第$i$行代表$k = i$時的答案，如果答案是有限值，輸出該答案，否則輸出Positive Infinity!!!

Sample Input 1

5
1 -1 1 -1 0
0 2 3 4 2

Sample Output 1

Positive Infinity!!!
1
1
1
1

Sample Input 2

8
777771449 8 7 0 -777777777 0 8 -8
3 2 5 4 0 7 6 2

Sample Output 2

777771449
15
7
777771449
777771449
7
Positive Infinity!!!
7

Sample Input 3

16
777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449 777771449
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 3

Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!
Positive Infinity!!!

Hints

裸題

Problem Source

TopCoder

owl
OWL

User's AC Ratio

100.0% (1/1)

Tags

建中資讀模競

Problem Setter

Created by owl

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 2~12 $\forall 0 \le i \le N - 1, a_i > 0$ 1
3 13~22 $\forall 0 \le i \le N - 1, a_i \le 0$ 1
4 23~32 $\forall 0 \le i \le N - 1, f(i) = (i + 1) \bmod N$ 9
5 0~2, 33~52 $N \le 3000$ 11
6 13~22, 53~72 若存在$m, k$使$f^ {m}(k) = k$，則$\displaystyle \sum_{i = 0}^ {m - 1} a_{f^ {i}(k)} \le 0$ 11
7 0~92 無特別限制 67

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 2000 512000 512000 65536 1 5 7
1 2000 512000 512000 65536 1 5 7
2 2000 512000 512000 65536 1 2 5 7
3 2000 512000 512000 65536 2 7
4 2000 512000 512000 65536 2 7
5 2000 512000 512000 65536 2 7
6 2000 512000 512000 65536 2 7
7 2000 512000 512000 65536 2 7
8 2000 512000 512000 65536 2 7
9 2000 512000 512000 65536 2 7
10 2000 512000 512000 65536 2 7
11 2000 512000 512000 65536 2 7
12 2000 512000 512000 65536 2 7
13 2000 512000 512000 65536 3 6 7
14 2000 512000 512000 65536 3 6 7
15 2000 512000 512000 65536 3 6 7
16 2000 512000 512000 65536 3 6 7
17 2000 512000 512000 65536 3 6 7
18 2000 512000 512000 65536 3 6 7
19 2000 512000 512000 65536 3 6 7
20 2000 512000 512000 65536 3 6 7
21 2000 512000 512000 65536 3 6 7
22 2000 512000 512000 65536 3 6 7
23 2000 512000 512000 65536 4 7
24 2000 512000 512000 65536 4 7
25 2000 512000 512000 65536 4 7
26 2000 512000 512000 65536 4 7
27 2000 512000 512000 65536 4 7
28 2000 512000 512000 65536 4 7
29 2000 512000 512000 65536 4 7
30 2000 512000 512000 65536 4 7
31 2000 512000 512000 65536 4 7
32 2000 512000 512000 65536 4 7
33 2000 512000 512000 65536 5 7
34 2000 512000 512000 65536 5 7
35 2000 512000 512000 65536 5 7
36 2000 512000 512000 65536 5 7
37 2000 512000 512000 65536 5 7
38 2000 512000 512000 65536 5 7
39 2000 512000 512000 65536 5 7
40 2000 512000 512000 65536 5 7
41 2000 512000 512000 65536 5 7
42 2000 512000 512000 65536 5 7
43 2000 512000 512000 65536 5 7
44 2000 512000 512000 65536 5 7
45 2000 512000 512000 65536 5 7
46 2000 512000 512000 65536 5 7
47 2000 512000 512000 65536 5 7
48 2000 512000 512000 65536 5 7
49 2000 512000 512000 65536 5 7
50 2000 512000 512000 65536 5 7
51 2000 512000 512000 65536 5 7
52 2000 512000 512000 65536 5 7
53 2000 512000 512000 65536 6 7
54 2000 512000 512000 65536 6 7
55 2000 512000 512000 65536 6 7
56 2000 512000 512000 65536 6 7
57 2000 512000 512000 65536 6 7
58 2000 512000 512000 65536 6 7
59 2000 512000 512000 65536 6 7
60 2000 512000 512000 65536 6 7
61 2000 512000 512000 65536 6 7
62 2000 512000 512000 65536 6 7
63 2000 512000 512000 65536 6 7
64 2000 512000 512000 65536 6 7
65 2000 512000 512000 65536 6 7
66 2000 512000 512000 65536 6 7
67 2000 512000 512000 65536 6 7
68 2000 512000 512000 65536 6 7
69 2000 512000 512000 65536 6 7
70 2000 512000 512000 65536 6 7
71 2000 512000 512000 65536 6 7
72 2000 512000 512000 65536 6 7
73 2000 512000 512000 65536 7
74 2000 512000 512000 65536 7
75 2000 512000 512000 65536 7
76 2000 512000 512000 65536 7
77 2000 512000 512000 65536 7
78 2000 512000 512000 65536 7
79 2000 512000 512000 65536 7
80 2000 512000 512000 65536 7
81 2000 512000 512000 65536 7
82 2000 512000 512000 65536 7
83 2000 512000 512000 65536 7
84 2000 512000 512000 65536 7
85 2000 512000 512000 65536 7
86 2000 512000 512000 65536 7
87 2000 512000 512000 65536 7
88 2000 512000 512000 65536 7
89 2000 512000 512000 65536 7
90 2000 512000 512000 65536 7
91 2000 512000 512000 65536 7
92 2000 512000 512000 65536 7
Submit
Back to Top