UCRPC F21 I - Sphere Mongers

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Drag the spheres back to your area!

Gold spheres are worth three points!

Sphere Mongers is a four player minigame in Super Mario Party, and you can view how the game is actually played here. The game area has a lot of spheres on the ground. Each player flies in a UFO with a magnet, and the goal is to get as many spheres as possible. There are two types of spheres: the regular ones (silver ones) which are worth one point and gold ones which are worth three points. At any time, a player can lower their magnet to attract some spheres. In particular, all spheres within a certain radius r will be caught by this player.

At any time, a player may want to know, given the current status of the game (all the spheres and their position), what is the maximum points one can get in one catch. Your task is to write a program to answer this question. Note that the player can be at any position, not just integral coordinates.

Input Specification

The first line of the input contains two integers, n (0< n\le 1000), which is the number of spheres in the game, and r, which means that a magnet can attract all spheres within distance of r.

The next n lines each contain three integers x_i,y_i,g_i (0\le x_i,y_i\le 1000), which describes sphere i. (x_i,y_i) denotes the coordinate of sphere i. g_i is 0 or 1, where 0 means it is a silver sphere (1 point), and 1 means it is a gold sphere (3 points).

Output Specification

The output only contains 1 integer, which is the maximum number of points one can get by one catch.

Sample Input

5 2
1 1 0
1 5 1
3 3 0
3 7 0
10 10 1

Sample Output


Explanation for Sample Output

In the best solution, the player can stay at position (1,3), and catch spheres 1, 2 and 3. They are in total worth 5 points.


For 60% of the test cases, n\le 100.

There are 20 test cases, 6 points each.


There are no comments at the moment.