PEG Judge - NOI '09 - Plants vs. Zombies

National Olympiad in Informatics, China, 2009

Day 2, Problem 1 - Plants vs. Zombies

Plants vs. Zombies (PvZ) is currently a very popular video game. Plants and Zombies are the main roles of the game. In the game, plants defend while zombies attack. This game contains many types of different challenge modes, including "Protect Your Brains", "Bowling", etc. The most classic of them all involves the player controlling the plants to defend the attack of the zombies, or contrarily to have the player control the attack of the zombies on the plants.

Now, our problem will concern the attack of the zombies on the plants. Please note, the rules used in this problem are not identical to those in the actual game. There are two roles, plants and zombies. Each plant has a set of attackable positions and will be able to provide defense to these positions. Each zombie's attack method is to walk to the positions where plants are located and eat them up.

The game's map can be represented as an N row by M column grid. The rows are numbered 0 to N−1 from top to bottom. The columns are numbered 0 to M−1 from left to right. A plant will be positioned at every cell on the grid for simplicity's sake, and we shall refer to the plant in row r, column c by P_{r, c}.

There are many types of plants, including attack types, defense types, money producing types, and so forth. To simplify the description of each plant, we define Score and Attack as follows:

`Score`[`P_{r, c}`]	Zombies can destroy plant `P_{r, c}` to obtain energy. If `Score`[`P_{r, c}`] is a nonnegative integer, then that means `Score`[`P_{r, c}`] of energy is obtained from destroying `P_{r, c}`. Otherwise if this is a negative integer, then that means destroying `P_{r, c}` will cost −`Score`[`P_{r, c}`] of energy.
`Attack`[`P_{r, c}`]	The set of positions that plant `P_{r, c}`'s attack range spans for defense against zombie attacks.

Zombies must enter from the right side of the map, and can only walk horizontally across it. The only way that zombies can attack is to walk to the locations of the plants and eat them. Thus, Zombies will always start attacking from the right side. In other words, for attacks in row r, zombies must first attack P_{r, M−1}. To attack plant P_{r, c}, they must first attack and destroy plants P_{r, M−1}, P_{r, M−2}, …, P_{r, c}. Only until they travel to position (r, c) can they start the attack on the plant there.

For the purposes of this problem, the attack power of plants is infinitely large. As soon as zombies enter the attack range of a plant, they will be instantly wiped out, and will not be given any time to perform any attack operations. Thus if a zombie were to enter a position occupied by a plant, but that position intersects with the attack range of some other plant(s), then the zombie will be instantly destroyed, leaving the plant at this position completely unharmed (in our setup, the attack range of a plant does not include its own position, or else no plants can ever be destroyed).

The objective of zombies is to attack plants on the field to obtain the greatest energy income. At each step, you can select an existing plant and initiate an attack. The objective of this problem is, design a zombie attacking scheme by selecting the order of specific plants to attack, such that the final energy income is as large as possible.

Input Format

The first line contains two integers N and M, representing the number of rows and columns in the map, respectively.
The next N×M lines will provide information about the plant at each position on the grid. Line r×M + c + 1 of the input will give information about plant P_{r, c} in the following format: The first integer on the line is Score[P_{r, c}], the second integer w is the number of positions in the set Attack[P_{r, c}]. On the same line, w pairs of numbers (r', c') will follow, each indicating that the attack range of P_{r, c} includes the position at row r', column c'.

Output Format

Output a single integer, the maximum energy income that can be obtained by the zombies. Note: you may also choose to not initiate any attacks, which will result in an energy income of 0.

Sample Input

Sample Output

Explanation

In the sample, plant P_{1, 1} can attack position (0, 0) while plant P_{2, 0} can attack position (2, 1).
One solution is, first attack plants P_{1, 1} and P_{0, 1} before attacking plant P_{0, 0}. The total energy obtained is (−5) + 20 + 10 = 25. Note: position (2, 1) is protected by plant P_{2, 0}, so it is not possible to attack any plant in row 2.

Constraints

About 20% of the test cases satisfy 1 ≤ N, M ≤ 5.
About 40% of the test cases satisfy 1 ≤ N, M ≤ 10.
About 100% of the test cases satisfy 1 ≤ N ≤ 20, 1 ≤ M ≤ 30, −10000 ≤ Score ≤ 10000.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Aug 04, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...