TopCoder

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

50.8% (62/122)

Description

上體育課的時候,老師放了一排下圖這個東西,然後說:「我放了一些三角錐,等一下……」但你完全沒有心思去聽等一下要做什麼,因為你發現這些東西根本就不是三角錐,而是圓錐(如果忽視它上面那個洞的話)!

到底是三角錐還是圓錐呢

忿忿不平的你,決定要來破壞這一排「圓錐」。體育老師放了 $N$ 個圓錐排成一列,由左至右依序編號為 $1,2,\dots,N$。你發現,體育老師在第 $i$ 個圓錐上寫了一個數字 $A_i$,表示他對這個圓錐的珍惜程度(雖然你認為一個把圓錐說成三角錐的人不可能珍惜它)。

為了避免被老師發現你在搞破壞,你每次都只能偷走相鄰的 2 個或 3 個圓錐。在你一次偷走的圓錐中,如果有任兩個圓錐上面寫的數字是互質的,你就會覺得很不滿意,而你偷一次圓錐的滿意度是「你這次偷的圓錐中,兩兩相鄰的圓錐上面寫的數字的最大公因數總和」。換句話說,如果你一次偷了 $k$ 個圓錐,第 $i$ 個上面寫的數字是 $s_i$,那麼必須滿足:

  • $k=2 \lor k=3$
  • $\forall 1 \leq i \leq j \leq k,\ \gcd(s_i, s_j) > 1$

並且你獲得的滿足度是 $\sum_{i=1}^ {k-1} \gcd(s_i, s_{i+1})$。

在偷完一次圓錐後,體育老師會挪動一下剩下的圓錐,以避免圓錐之間有太大的間隔,但是圓錐的相對順序不會改變。

你希望把這排圓錐全部偷走,並且最大化每次偷圓錐的滿足度總和。

測資限制

  • $2 \leq N \leq 500$
  • $2 \leq A_i \leq 10^ 9$

Input Format

第一行有一個整數 $N$,表示體育老師放的圓錐數量。

第二行有 $N$ 個整數 $A_1,A_2,\dots,A_N$,表示體育老師在每個圓錐上寫的數字。

Output Format

輸出一個整數,表示你偷完圓錐後,每次偷圓錐的滿足度總和最大值。如果你不可能偷完所有圓錐,輸出 $-1$。

Sample Input

// Sample input 1
7
2 3 3 2 5 5 2

// Sample input 2
5
2 3 12 6 4

// Sample input 3
5
10 9 3 10 10

// Sample input 4
5
2 3 8 6 4

Sample Output

// Sample output 1
12

// Sample output 2
11

// Sample output 3
23

// Sample output 4
-1

Hints

對於第一筆範測,你可以先偷走第 $2,3$ 個圓錐、再偷走第 $5,6$ 個圓錐,最後偷走第 $1,4,7$ 個圓錐。

Problem Source

2021 師大附中校隊培訓 模擬競賽
From NTU ADA 2021 Fall HW2

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 4~17 $N \le 10$ 9
3 18~23 $A_i$ 一定是質數,且若一種數字有出現,它會出現恰 $2$ 或 $3$ 次 11
4 4~17, 24~36 $N \le 100$ 31
5 0~47 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 5
1 1000 524288 65536 1 5
2 1000 524288 65536 1 5
3 1000 524288 65536 1 5
4 1000 524288 65536 2 4 5
5 1000 524288 65536 2 4 5
6 1000 524288 65536 2 4 5
7 1000 524288 65536 2 4 5
8 1000 524288 65536 2 4 5
9 1000 524288 65536 2 4 5
10 1000 524288 65536 2 4 5
11 1000 524288 65536 2 4 5
12 1000 524288 65536 2 4 5
13 1000 524288 65536 2 4 5
14 1000 524288 65536 2 4 5
15 1000 524288 65536 2 4 5
16 1000 524288 65536 2 4 5
17 1000 524288 65536 2 4 5
18 1000 524288 65536 3 5
19 1000 524288 65536 3 5
20 1000 524288 65536 3 5
21 1000 524288 65536 3 5
22 1000 524288 65536 3 5
23 1000 524288 65536 3 5
24 1000 524288 65536 4 5
25 1000 524288 65536 4 5
26 1000 524288 65536 4 5
27 1000 524288 65536 4 5
28 1000 524288 65536 4 5
29 1000 524288 65536 4 5
30 1000 524288 65536 4 5
31 1000 524288 65536 4 5
32 1000 524288 65536 4 5
33 1000 524288 65536 4 5
34 1000 524288 65536 4 5
35 1000 524288 65536 4 5
36 1000 524288 65536 4 5
37 1000 524288 65536 5
38 1000 524288 65536 5
39 1000 524288 65536 5
40 1000 524288 65536 5
41 1000 524288 65536 5
42 1000 524288 65536 5
43 1000 524288 65536 5
44 1000 524288 65536 5
45 1000 524288 65536 5
46 1000 524288 65536 5
47 1000 524288 65536 5