TopCoder

Thumb avatar
ToMmyDong
高三生

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

35.0% (36/103)

Description

在一個「漸進式框架」當中,你想要找到一個最大面積的矩形位置放置你最喜愛的一幅畫。

當然地,畫框必須掛正,所以矩形的四個邊都必須與框架的邊平行或垂直。

所謂的「漸進式框架」,指的是任何一個水平線截出的框架區段是連續,並且由上往下該區段只會往右移動,如下圖。

Input Format

第一列有一個正整數$n$ ($n\leq 100,000$),代表從框架左上角開始,往右、往下、往右、...總共有幾條邊。
第$2~n+1$列總共有$n$個正整數,依序代表往右、往下、...的每邊邊長。
第$n+2$列有一個正整數$m$ ($m\leq 100,000$),代表從框架左上角開始,往下、往右、往下、...總共有幾條邊。
第$n+3~n+m+2$列有總共有$m$個正整數,依序代表往下、往右、...的每邊邊長。

你可以假設輸入的框架一定是正確的,而且畫框形成的多邊形不會自交、$n,m$都是偶數。
所有數字都不超過$10^ 9 $。

Output Format

請輸出最大矩形面積。

Sample Input

6
5
3
4
3
3
3
4
5
4
4
8

Sample Output

30

Hints

Problem Source

原TIOJ1283 / [TIOJ] IOI2008 暖身賽 1(prob I)。Problem setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144