## IOI '22 P1 - Catfish Farm

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
C++

Bu Dengklek owns a catfish farm. The catfish farm is a pond consisting of an grid of cells. Each cell is a square of the same size. The columns of the grid are numbered from to from west to east and the rows are numbered from to from south to north. We refer to the cell located at column and row of the grid (, ) as cell .

In the pond, there are catfish, numbered from to , located at distinct cells. For each such that , catfish is located at cell , and weighs grams.

Bu Dengklek wants to build some piers to catch the catfish. A pier in column of length (for any and ) is a rectangle extending from row to row , covering cells . For each column, Bu Dengklek can choose either to build a pier of some length of her choice or to not build a pier.

Catfish (for each such that ) can be caught if there is a pier directly to the west or east of it, and there is no pier covering its cell; that is, if

• at least one of the cells or is covered by a pier, and
• there is no pier covering cell .

For example, consider a pond of size with catfish:

• Catfish is located at cell and weighs grams.
• Catfish is located at cell and weighs grams.
• Catfish is located at cell and weighs gram.
• Catfish is located at cell and weighs grams.

One way Bu Dengklek can build the piers is as follows:

Before the piers are built After the piers are built

The number at a cell denotes the weight of the catfish located at the cell. The shaded cells are covered by piers. In this case, catfish (at cell ) and catfish (at cell ) can be caught. Catfish (at cell ) cannot be caught, as there is a pier covering its location, while catfish (at cell ) can not be caught as there is no pier directly to the west nor east of it.

Bu Dengklek would like to build piers so that the total weight of catfish she can catch is as large as possible. Your task is to find the maximum total weight of catfish that Bu Dengklek can catch after building piers.

#### Implementation Details

You should implement the following procedure:

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)

• : the size of the pond.
• : the number of catfish.
• , : arrays of length describing catfish locations.
• : array of length describing catfish weights.
• This procedure should return an integer representing the maximum total weight of catfish that Bu Dengklek can catch after building piers.
• This procedure is called exactly once.

#### Example

Consider the following call:

max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})


This example is illustrated in the task description above.

After building piers as described, Bu Dengklek can catch catfish and , whose total weight is grams. As there is no way to build piers to catch catfish with a total weight of more than grams, the procedure should return .

#### Constraints

• , (for each such that )
• (for each such that )
• No two catfish share the same cell. In other words, or (for each and such that ).

1. (3 points) is even (for each such that )
2. (6 points) (for each such that )
3. (9 points) (for each such that )
4. (14 points) , (for each such that )
5. (21 points)
6. (17 points)
7. (14 points) There are at most catfish in each column.
8. (16 points) No additional constraints.

• line :
• line :

• line : the return value of max_weights