TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

70.4% (19/27)

Tags

Description

為了慶祝你終於在 APCS 測驗中拿下實作題滿分的佳績,你決定買一個大蛋糕來與眾人分享你的喜悅。

眾人分切完蛋糕後,最後留下了兩條長度 N 的蛋糕。你利用神秘的蛋糕透視儀器得到了每一段蛋糕的真實好吃程度。第一條蛋糕的第 i 段好吃程度為 ai,第二條蛋糕的第 i 段好吃程度為 bi

俗話說好東西就該和好朋友分享,為了表示你的慷慨,你想將其中的一條長度 N 的蛋糕送給你最好的朋友,但同時你又希望自己留下的蛋糕好吃程度總和盡量大。你決定在兩條蛋糕上動一點手腳,並留下好吃程度總和比較高的蛋糕:你可以選擇一段連續的區間 [l,r] (1lrN),並將兩塊蛋糕的第 l 到第 r 段切下來並交換。也就是說,交換過後的第一條蛋糕每一段的好吃程度會變成 a1,a2,,al1,bl,bl+1,,br1,br,ar+1,,aN1,aN,而第二條蛋糕每一段的好吃程度則是 b1,b2,,bl1,al,al+1,,ar1,ar,br+1,,bN1,bN。請注意你不一定要進行交換蛋糕的操作。

請你寫一支程式算算看,你應該要交換兩條蛋糕的哪一段區間,或不需要進行交換,才能讓自己留下的蛋糕好吃程度總和最大。相信這樣的問題對已經在 APCS 實作題拿下滿分的你來說一定是一塊小蛋糕。

Input Format

第一行為一正整數 N,表示兩條蛋糕的長度。

第二行包含 N 個正整數 a1,a2,aN,表示第一條蛋糕每一段的好吃程度。

第三行包含 N 個正整數 b1,b2,bN,表示第二條蛋糕每一段的好吃程度。

  • 1N106
  • 1ai,bi200

Output Format

輸出一行,包含三個整數,第一個整數表示進行完操作(或不進行操作)後,你留下的蛋糕的好吃程度總和。如果你交換了兩條蛋糕的某一段區間,接下來請依序輸出 l,r,表示交換的區間;如果你沒有交換蛋糕,請輸出兩個整數 1

如果有多種可以留下好吃程度總和最大的蛋糕的方式,你可以輸出任意一種。

Sample Input 1

6
3 1 4 1 5 9
2 6 5 3 5 8

Sample Output 1

31 2 4

Sample Input 2

3
7 2 7
6 1 6

Sample Output 2

16 -1 -1

Hints

本題輸入資料量較大,建議 C++ 輸入輸出使用者加上 cin.tie(0); 以及 ios_base::sync_with_stdio(0); 兩行,並以 \n 代替 endl 以加速輸入。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~18 N200 5
3 0~35 N2000 15
4 0~52 無額外限制 80

Testdata and Limits

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