AIOC Banner

Problem: Greed

Want to try solving this problem? You can submit your code online if you log in or register.


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 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.



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

Sample Output



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.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 25 March 2023,  7:31pm AEDT