852 . 切蛋糕 2
TopCoder
Tags
Description
為了慶祝你終於在 APCS 測驗中拿下實作題滿分的佳績，你決定買一個大蛋糕來與眾人分享你的喜悅。
在眾人分切完蛋糕後，最後留下了兩條長度 $N$ 的蛋糕。你利用神秘的蛋糕透視儀器得到了每一段蛋糕的真實好吃程度。第一條蛋糕的第 $i$ 段好吃程度為 $a_i$，第二條蛋糕的第 $i$ 段好吃程度為 $b_i$。
俗話說好東西就該和好朋友分享，為了表示你的慷慨，你想將其中的一條長度 $N$ 的蛋糕送給你最好的朋友，但同時你又希望自己留下的蛋糕好吃程度總和盡量大。你決定在兩條蛋糕上動一點手腳，並留下好吃程度總和比較高的蛋糕：你可以選擇一段連續的區間 $[l, r]\ (1 \le l \le r \le N)$，並將兩塊蛋糕的第 $l$ 到第 $r$ 段切下來並交換。也就是說，交換過後的第一條蛋糕每一段的好吃程度會變成 $a_1, a_2, \cdots, a_{l-1}, b_l, b_{l+1}, \cdots, b_{r-1}, b_r, a_{r+1}, \cdots, a_{N-1}, a_N$，而第二條蛋糕每一段的好吃程度則是 $b_1, b_2, \cdots, b_{l-1}, a_l, a_{l+1}, \cdots, a_{r-1}, a_r, b_{r+1}, \cdots, b_{N-1}, b_N$。請注意你不一定要進行交換蛋糕的操作。
請你寫一支程式算算看，你應該要交換兩條蛋糕的哪一段區間，或不需要進行交換，才能讓自己留下的蛋糕好吃程度總和最大。相信這樣的問題對已經在 APCS 實作題拿下滿分的你來說一定是一塊小蛋糕。
Input Format
第一行為一正整數 $N$，表示兩條蛋糕的長度。
第二行包含 $N$ 個正整數 $a_1, a_2, \cdots a_N$，表示第一條蛋糕每一段的好吃程度。
第三行包含 $N$ 個正整數 $b_1, b_2, \cdots b_N$，表示第二條蛋糕每一段的好吃程度。
- $1 \le N \le 10 ^ 6$
- $1 \le a_i, b_i \le 200$
Output Format
輸出一行，包含三個整數，第一個整數表示進行完操作（或不進行操作）後，你留下的蛋糕的好吃程度總和。如果你交換了兩條蛋糕的某一段區間，接下來請依序輸出 $l, r$，表示交換的區間；如果你沒有交換蛋糕，請輸出兩個整數 $-1$。
如果有多種可以留下好吃程度總和最大的蛋糕的方式，你可以輸出任意一種。
Sample Input 1
3 1 4 1 5 9
2 6 5 3 5 8
Sample Output 1
Sample Input 2
7 2 7
6 1 6
Sample Output 2
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 | $N \le 200$ | 5 |
| 3 | 0~35 | $N \le 2000$ | 15 |
| 4 | 0~52 | 無額外限制 | 80 |