Chef And Hungry Birds
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef loves to listen bird's chirping. Now Chef is in his office and is missing the chirping of birds after getting bored with long hours of work. So, he wants to have some fun. He likes paper birds of special shape. Here is some examples of beautiful paper birds Chef likes.
As we can see, the stomach of each bird is a right angled isoceles triangle (highlighted in the figures).
Today morning, Chef had bought a rectangular piece of paper of height N and width M. For e.g. consider following rectangular paper of height N = 3 and width M = 5.
As you can see that, this is not an ordinary paper. This paper has some marked lines where each marked line joins two points available on the paper.
Now, Chef imagines creating birds for each possible right isoceles triangle whose sides are along the marked lines of the paper and its vertices are among the given points of the rectangular paper. See the sample test case for better understanding.
Each little bird has capacity to eat some grams of grain. Capacity of eating grains for a bird is defined by sum of hungriness of all the points included in triangle (including the corners of triangle) made by bird's stomach.
See the following images for some examples:
Now, Chef has G grams of grains at his house and wants to feed as many birds as possible. Can you help him in finding out the maximum number of birds he can feed?
First line of input contains three space separated integers N , M and Q denoting the length, width of the paper and number of chef's questions. Next N lines of input contains M space separated integers where the jth integer in the ith line denotes the hungriness of that point i.e Hi,j. Next Q lines of input contains a single integer G denoting the grams of grain available to the chef.
For each of the chef's question, Print the maximum number of birds he can feed.
- 1 ≤ N ≤ 335
- 1 ≤ N * M ≤ 112225
- 0 ≤ Hi,j ≤ 50
- 1 ≤ Q ≤ 105
- 0 ≤ G ≤ 109
- Subtask 1 (20 pts):
- 1 ≤ N, M, Q ≤ 50
- 0 ≤ Hi,j ≤ 50
- 0 ≤ G ≤ 109
- Subtask 2 (80 pts): Original Constraints
2 3 3 1 2 0 3 0 0 5 10 15Output
2 4 5
There are these 10 birds possible with their hungriness as follows:
(A) 4 (B) 6 (C) 3 (D) 5 (E) 5 (F) 2 (G) 2 (H) 2 (I) 0 (J) 3Note that bird (I) is not hungry and therefore we don't need to feed it.
|Tags||binary-search, dynamic-programming, easy, ma5termind, march16|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.