HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC16 Group Contests > problem:


F2. 50936 - Saving the Soldiers

IMPC16 Group Contests

Start: Jan.16.2016 at 10:00:00 AM
Finish: Jan.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (3)

Contest problems

• 23. 50875 - Take m-out
• 24. 50876 - He is my cousin
• 25. 50877 - Friendly Queue
• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships
• 35. 50929 - Present from your uncles
• F1. 50841 - My grand-grand-grandfa...
• F2. 50936 - Saving the Soldiers
• F4. 50977 - Gaussian Elimination
• F5. 50978 - Albanian Coders
• F6. 50979 - Minimum access cost for...

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Saving the Soldiers

"Commander! The battle is continuing. When trying to conquer the island, several planes have crashed in the air, sir. And, the soldiers are falling down. Now, the navy fleet was sent to save the soldiers. "

You know the coordinates of and the capacity of all ships. You also follow positions of the soldiers from their GPS signals. If a soldier falls into the sea, he has to swim towards the land. If a soldier falls down on any part of a ship and if there is place in the ship, he can be saved (each ship can hold the size of ship times 2 soldiers. If the ship is full, then it cannot take any more soldiers because the ship may sink, then). If the ship is full, then the soldier has to swim towards land, again.

Question: On a 2D array, you are given the ship and sea information. Then you are also given the coordinates of the soldiers falling. Write a program that finds the number of soldiers saved by the ships.

Input specification
You will be first given two numbers: the size of 2D array (n) and the number of soldiers falling (m). Then, you will be given n lines with n space separated integers where 1 represents a part of a ship and 0 represents the sea. The following m lines will contain 2 integers: x and y coordinates of each soldier falling. Coordinates start from upper left corner (see the figure) where 0 ≤ n ≤ 100 and 0 ≤ m ≤ 10,000.

Output specification:
Show one number.

Sample Input
5 8
0 1 0 0 0
1 1 0 0 1
1 1 0 1 1
0 0 0 0 0
0 0 0 0 0
3 3
4 3
4 3
4 3
5 3
5 3
5 3
5 3
Sample Output
6

Explanation:
We are given 5x5 2D array in which there are two ships with the sizes 5 and 3. The ship with the size 5 can hold at most 10 (capacity times 2) soldiers, and the other ship can hold 6 soldiers.
Soldier 1 has fallen to the sea. The other 7 soldiers have fallen on the ships. But, only six of them were saved by the ships, because the ship2 can hold at most 6 soldiers.



Для отправки решений необходимо выполнить вход.

www.contester.ru