P2038 [NOIP 2014 Senior] Wireless Network Transmitter Placement

NOIP 2014 Senior D2T1.

With the increasing popularity of smartphones, the demand for wireless networks is growing. A certain city decides to cover public places with a wireless network. Assume the city layout is a grid formed by $129$ east-west streets and $129$ north-south streets, and the distance between any two adjacent parallel streets is a constant $1$. The east-west streets are numbered $0,1,2 \dots 128$ from north to south, and the north-south streets are numbered $0,1,2 \dots 128$ from west to east. Intersections are formed where an east-west street meets a north-south street. The intersection of the north-south street numbered $x$ and the east-west street numbered $y$ has coordinates $(x, y)$. Some intersections have a certain number of public places. Due to budget constraints, only one large wireless network transmitter can be installed. Its coverage area is a square centered at the installation point with side length $2d$. The coverage includes the square’s boundary. Now the authorities plan to install a transmitter with parameter $d$. Please help them find a suitable intersection in the city as the installation location to maximize the number of public places covered.

The first line contains an integer $d$, the coverage parameter of the wireless network transmitter. The second line contains an integer $n$, the number of intersections that have public places. The next $n$ lines each contain three integers $x, y, k$ separated by a space, representing the intersection coordinates $(x, y)$ and the number of public places at that intersection. Each coordinate appears at most once.

Output one line containing two integers separated by a space: the number of installation locations that achieve the maximum coverage of public places, and the maximum number of public places covered.

For $100\%$ of the testdata, $1 \leq d \leq 20, 1 \leq n \leq 20, 0 \leq x \leq 128, 0 \leq y \leq 128, 0 < k \leq 10^6$. Translated by ChatGPT 5