P4056 [JSOI2009] Mars Treasure Map

JSOI 2009 Round 3, second exam.

After traveling on Mars for many days, jyy accidentally discovered a treasure map. According to the map, the treasure is buried on $N$ islands $(2\le N \le 2 \times 10^{5})$ in a huge lake. For convenience, the map divides the entire lake into $M$ rows and $M$ columns $(1\le M\le 1000)$, a total of $M \times M$ cells, and numbers all islands from $1$ to $N$. The $i$-th island is located at row $X_i$, column $Y_i$ (that is, on the cell with coordinates $(X_i,Y_i)$, where $X_i,Y_i$ are integers satisfying $1

The first line contains two integers $N,M$. Lines $2$ to $N+1$: each line contains $3$ integers. On line $i+1$, the $3$ integers are $X_i$, $Y_i$, and $V_i$. Each island has distinct coordinates. It is guaranteed that there are islands at coordinates $(1,1)$ and $(M,M)$.

Output a single integer on the first line, representing the maximum net gain.

Sample Explanation: $20+60+10-\left ( \left(3-1 \right )^2+\left (5-1 \right )^2 \right )-\left ( \left (10-3 \right )^2+\left (10-5 \right )^2 \right )=-4$ Constraints: - For $20\%$ of the testdata, $M\le 200$, and $N\le 2\times 10^3$. - For $50\%$ of the testdata, $M\le 200$, and $N\le 2\times 10^4$. - For $100\%$ of the testdata, $M\le 1000$, and $N\le 2\times 10^5$. Translated by ChatGPT 5