TopCoder

Thumb avatar
ToMmyDong
$$To(M^2)_y$$

User's AC Ratio

89.5% (17/19)

Submission's AC Ratio

34.6% (36/104)

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5