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

#3881 upload - done - how_to_reg -

The Lazy Cow timer 1s memory 128MB

#3881

The Lazy Cow 1s 128MB