G - Palace of King
All submissions for this problem are available.
A king in a distant land wants to build a new palace for himself. There are some plots of land in the country. Some of them don't have any owner, some of the plots are owned by the citizens of the country. Being a good person, the king wants to pay the appropriate amount of money for the land he uses. If he uses some portion of a plot, he needs to buy the whole plot. Also, this is a weird country where the plots owned by the citizens may overlap. For an area, the king needs to buy all the overlapping plots to use that area. To use some area not owned by any citizen, the king doesn't need to spend any money.
Formally, the country is an M × N grid with L plots owned by the citizens. Each of these plots is rectangular in shape. The ith plot has its lower left corner at (xi, yi), length li (along with the x-axis), width wi (along with the y-axis), and price pi. The palace the king is going to build should be rectangular in shape as well. Please help him to find the rectangular place with the largest area which he can use without spending more than C amount of money.
(0,0) is the lower left corner of the country and (M, N) is the upper right corner. All the plots owned by the citizens are inside this area. The palace should be inside this area as well. The sides of the palace should be axis-parallel.
- The first line of the input contains an integer T denoting the number of test cases. Description of each test case is given below.
- The first line of each test case contains three integers M, N, and C.
- The second line contains L.
- Each of next L lines contains the description of a plot owned by a citizen. ith of these line has five integers: xi, yi, li, wi, and pi.
For each test case, print "Case i: ", and then the answer (mod 109 + 7), where i is the testcase number, 1-indexed. The answer should be the largest area of the rectangular shaped land that can be used without spending more than C amount of money.
- 1 ≤ T ≤ 10
- 1 ≤ M, N ≤ 1000
- 0 ≤ C ≤ 1000000000
- 0 ≤ xi ≤ M - li
- 0 ≤ yi ≤ N - wi
- 1 ≤ li, wi
- 1 ≤ pi ≤ 100000
- 1 ≤ L ≤ 1000
Input: 1 4 4 6 3 1 0 2 1 2 2 0 1 4 2 0 3 3 1 4 Output: Case 1: 12
The image above shows the lands owned by the citizens and the palace with area 12 (lower left corner at (0,0) and upper right corner at (4,3)).
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.