Problem: Greed
Want to try solving this problem? You can submit your code online if you log in or register.
Greed
Input File: standard input
Output File: standard output
Time Limit: 3.5 seconds
Memory Limit: 256 MB
Happy birthday! It is time to cut your cake! Including you, there are
K+1 hungry people who are eager for some of your R row by C column
rectangular cake. To ensure fairness, there are some rules about how you may cut
your cake.
- You must make K cuts, in order to split the cake into K+1 pieces.
- Every cut must be made parallel to the sides of the rectangle.
- Every cut must begin on either the left or bottom side of the
cake, and must continue until it hits either the opposite side of
the cake or an existing cut.
- There are H allowed locations for horizontal cuts and V locations
allowed for vertical cuts.
- Once all cuts have been made, you will receive the largest piece of
cake.
You love cake, but do not wish to be seen to be greedy. In order to avoid this
fate, you must make the area of the largest piece of cake as small as possible.
Input
- The first line of input contains five integers R,C,K,H,V.
- The following H lines contain one integer each, the i-th of which
being yi. This indicates a horizontal cut can be made yi units up
from the bottom side of the cake. These will be distinct and strictly
increasing.
- The following V lines contain one integer each, the i-th of which
being xi. This indicates a vertical cut can be made xi units to
the right of the left side of the cake. These will be distinct and
strictly increasing.
Output
Output must consist of a single integer representing the area of the smallest
possible largest slice of cake.
Sample Input
6 8 2 2 3
3
5
2
5
6
Sample Output
18
Explanation
In this example, it is possible for us to create vertical cuts at 2, 5, and
6, as well as horizontal cuts at 3 and 5.
By first cutting the cake vertically at position 5, and then horizontally at
position 3, we can produce two slices of area 15 and once slice of area
18. This is the smallest we can make the largest slice, and so we output
18.
Subtasks & Constraints
For all subtasks, 1 ≤ K ≤ H + V, 0 ≤ H, V ≤ 1500, 2 ≤ R,
C, 4 ≤ RC ≤ 230, 1 ≤ xi < C and 1 ≤ yi < R.
- For Subtask 1 (10 points), H, V ≤ 10.
- For Subtask 2 (15 points), K = H + V ≤ 40.
- For Subtask 3 (15 points), H, V ≤ 40.
- For Subtask 4 (20 points), H, V ≤ 100.
- For Subtask 5 (20 points), K ≤ 100, H, V ≤ 300.
- For Subtask 6 (20 points), no additional constraints.