TopCoder

fatman
2024北市賽rk.4不是我

User's AC Ratio

63.2% (36/57)

Submission's AC Ratio

22.5% (54/240)

Tags

Description

俄羅斯娃娃是一種特別的木製玩具,由一個大娃娃包住一個小娃娃。
可以向俄羅斯娃娃許願,每個娃娃有法力值,法力值越高,代表願望越有可能成真。

現在有 n 個大娃娃排成一圈,順時針數來的法力值為 a0an1;與 n 個小娃娃排成一圈,順時針數來的法力值為 b0bn1

因為某種特別的迷信(?),小娃娃的法力值是非嚴格遞增的,也就是 b0b1bn1

你可以將小娃娃順時針轉 k 格(0k<n),並將對應到的大娃娃包住小娃娃,也就是讓編號 (i+k) mod n 的大娃娃包住編號 i 的小娃娃。我們稱此俄羅斯娃娃的法力值為大娃娃與小娃娃的法力值總和,也就是 a(i+k) mod n+bi

願望成真的程度與 n 個俄羅斯娃娃法力值的最小值 S 有關,為了使願望成真,你想使 S 越大越好,請你輸出在適當的轉小娃娃後,S 最大可以是多少。

Input Format

第一行有一個正整數 n,代表大娃娃與小娃娃的數量。
第二行有 n 個正整數 a0an1,代表大娃娃的法力值。
第三行有 n 個正整數 b0bn1,代表小娃娃的法力值。

對於所有測試資料:

  • 3n105
  • 1ai,bi10180i<n
  • bibi+10in2

Output Format

輸出一個整數 S,代表在適當的轉小娃娃後,俄羅斯娃娃法力值的最小值 S 最大可以是多少。

Sample Input 1

3
20 10 30
1 3 15

Sample Output 1

23

Sample Input 2

10
395 846 120 567 719 523 162 99 48 311
74 85 241 322 341 415 421 595 705 720

Sample Output 2

440

Hints

x mod y 代表 xy 取模,也就是 x 除以 y 的餘數

在範例測資一中:
將小娃娃順時針轉 k=2 格會使 S 最大,此時 S=min(20+3,10+15,30+1)=23

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13, 38~39 n103 22
3 5~10, 17~22, 29~34 aiai+10in2 20
4 0~43 無其他限制 58

Testdata and Limits

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