TopCoder

000000
Caidorz

User's AC Ratio

82.8% (24/29)

Submission's AC Ratio

43.1% (75/174)

Tags

Description

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

到底是三角錐還是圓錐呢

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

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

  • k=2k=3
  • 1ijk, gcd(si,sj)>1

並且你獲得的滿足度是 i=1k1gcd(si,si+1)

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

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

測資限制

  • 2N500
  • 2Ai109

Input Format

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

第二行有 N 個整數 A1,A2,,AN,表示體育老師在每個圓錐上寫的數字。

Output Format

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

Sample Input 1

7
2 3 3 2 5 5 2

Sample Output 1

12

Sample Input 2

5
2 3 12 6 4

Sample Output 2

11

Sample Input 3

5
10 9 3 10 10

Sample Output 3

23

Sample Input 4

5
2 3 8 6 4

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 N10 9
3 18~23 Ai 一定是質數,且若一種數字有出現,它會出現恰 23 11
4 4~17, 24~36 N100 31
5 0~47 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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