Triway Cup '18 Summer E - Eyes of Void

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

In his second flashback, Bai Yuechu recalls Tushan's greatest enemy: the Queen of the Black Foxen. In one of their legendary fights with her, his ancestor, Dongfang Yuechu uses the "Tear void" ability.

The Queen of the Black Foxen can be modelled as a 2D plane (see picture), with the point that the tear void hits being (0, 0). The tear void then expands in a circle.

Her body has N "magical points", represented as coordinates on the 2D plane. The i-th point, if hit by the tear void, deals d_i damage to her. However, expanding the tear void also causes Dongfang Yuechu to expend energy. Specifically, a tear void with radius r costs Cr^2 energy, where C is a constant in the input. Dongfang wants to measure his effectiveness, which is defined as the (\sum_i d_i)-Cr^2, for all i which are inside the circle. Help him calculate the maximum effectiveness he can have.

Input Specification

Line 1: N, C (1 \le N \le 200\,000, 1 \le C \le 1000)

Next N lines: 3 integers d_i, x_i, y_i, representing a point with damage d_i at (x_i, y_i). (-1000 \le x_i, y_i \le 1000, 0 \le d_i \le 1000).

Sample Input

10 3
36 5 0
30 -8 -2
61 -5 -4
74 -2 3
19 -7 -4
21 -5 -4
75 9 -5
29 10 -8
81 8 2
99 3 -7

Sample Output

217

Comments

There are no comments at the moment.