HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50936 - Saving the Soldiers

Guest
• Review clarifications (3)

Section problems

• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk

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