USACO 2014 March Contest, Gold
Problem 1. The Lazy Cow
Contest has ended.
Log in to allow submissions in analysis mode
Problem 1: The Lazy Cow [gold] [Brian Dean, 2014]
It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants
to locate herself at a position in her field so that she can reach as much
delicious grass as possible within only a short distance.
There are N patches of grass (1 <= N <= 100,000) in Bessie's field.
The ith such patch contains g_i units of grass (1 <= g_i <= 10,000)
and is located at a distinct point (x_i, y_i) in the field (0 <= x_i,
y_i <= 1,000,000). Bessie would like to choose a point in the field
as her initial location (possibly the same point as a patch of grass,
and possibly even a point with non-integer coordinates) so that a
maximum amount of grass is within a distance of K steps from this
location (1 <= K <= 2,000,000).
When Bessie takes a step, she moves 1 unit north, south, east, or west of
her current position. For example, to move from (0,0) to (3,2), this
requires 5 total steps. Bessie does not need to take integer-sized
steps -- for example, 1 total step could be divided up as half a unit
north and half a unit east.
Please help Bessie determine the maximum amount of grass she can reach, if
she chooses the best possible initial location.
PROBLEM NAME: lazy
INPUT FORMAT:
* Line 1: The integers N and K.
* Lines 2..1+N: Line i+1 describes the ith patch of grass using 3
integers: g_i, x_i, y_i.
SAMPLE INPUT (file lazy.in):
4 3
7 8 6
3 0 0
4 6 0
1 4 2
INPUT DETAILS:
Bessie is willing to take at most 3 steps from her initial position. There
are 4 patches of grass. The first contains 7 units of grass and is located
at position (8,6), and so on.
OUTPUT FORMAT:
* Line 1: The maximum amount of grass Bessie can reach within K steps,
if she locates herself at the best possible initial position.
SAMPLE OUTPUT (file lazy.out):
8
OUTPUT DETAILS:
By locating herself at (3,0), the grass at positions (0,0), (6,0), and
(4,2) is all within K units of distance.
Contest has ended. No further submissions allowed.