P1514 [NOIP 2010 Senior] Channeling Water into the City

NOIP 2010 Senior T4.

In a faraway country, a scenic lake lies on one side and a boundless desert on the other. The country’s administrative divisions form an $N$-by-$M$ rectangle, as shown above, where each cell represents a city, and each city has an elevation.  To let as many residents as possible drink clear lake water, water facilities will be built in some cities. There are two types of facilities: reservoir plants and transfer stations. A reservoir plant uses pumps to draw water from the lake into the reservoir of its city. Therefore, only cities in the first row, which border the lake, can build reservoir plants. A transfer station uses pipelines and elevation drop to convey lake water from higher places to lower places. Thus, a city can build a transfer station only if there exists an adjacent city sharing a side, with a strictly higher elevation, that already has a water facility. Because the cities in the $N$-th row are close to the desert and form the arid region, every city in that row is required to have a water facility. Can this requirement be satisfied? If yes, compute the minimum number of reservoir plants to build; if not, find how many cities in the arid region cannot possibly have any water facility.

The first line contains two positive integers $N, M$, representing the size of the rectangle. Then $N$ lines follow, each containing $M$ positive integers, which are the elevations of the cities in order.

Two lines. If the requirement can be met, output the integer $1$ on the first line, and output an integer on the second line representing the minimum number of reservoir plants. If the requirement cannot be met, output the integer $0$ on the first line, and output an integer on the second line representing the number of cities in the arid region that cannot possibly have any water facility.

Sample 1 explanation: You only need to build a reservoir plant in the city with elevation $9$ to satisfy the requirement. Sample 2 explanation:  In the three cities highlighted with thick borders in the figure above, building reservoir plants will satisfy the requirement. The transfer stations in the arid region fed by these three reservoir plants are marked in three colors. Of course, the construction plan may not be unique. Constraints This problem has 10 pieces of testdata, with limits as shown in the table below: | Testdata ID | Whether requirement can be met | $N\le$ | $M\le$ | | :----------: | :----------: | :----------: | :----------: | | 1 | No | $10$ | $10$ | | 2 | No | $100$ | $100$ | | 3 | No | $500$ | $500$ | | 4 | Yes | $1$ | $10$ | | 5 | Yes | $10$ | $10$ | | 6 | Yes | $100$ | $20$ | | 7 | Yes | $100$ | $50$ | | 8 | Yes | $100$ | $100$ | | 9 | Yes | $200$ | $200$ | | 10 | Yes | $500$ | $500$ | For all 10 testdata, each city’s elevation does not exceed $10^6$. Translated by ChatGPT 5