luogu#P4876. [USACO14MAR] The Lazy Cow G
[USACO14MAR] The Lazy Cow G
题目描述
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 patches of grass in Bessie's field. The such patch contains units of grass and is located at a distinct point in the field . 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 steps from this location .
When Bessie takes a step, she moves 1 unit north, south, east, or west of her current position. For example, to move from to , 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.
输入格式
-
Line 1: The integers and .
-
Lines 2..1+N: Line describes the patch of grass using 3 integers:
输出格式
- Line 1: The maximum amount of grass Bessie can reach within steps, if she locates herself at the best possible initial position.
题目大意
Bessie的田里有N(1<=N<=100,000)块草地,每块草地的坐标是 (xi, yi) (0<=xi,yi<=1,000,000),上面长着gi(1<=gi<=10,000)个单位的牧草。
Bessie可以向东南西北方向走,一次走一步(一个单位长度)。如她从(0,0)走到(3,2)需要5步。她最多可以一次走k (1<=k<=2,000,000) 步。
现在她想找一个位置,使她从该位置出发可以得到最多单位的牧草(她可以走多次,但每次都从该位置出发)。
输入格式:
第1行:两个整数N和K
第2~N+1行:三个整数gi,xi,yi
输出格式:
第1行:Bessie所能获得的最多单位牧草数
4 3
7 8 6
3 0 0
4 6 0
1 4 2
8
提示
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 , and so on.
OUTPUT DETAILS:
By locating herself at , the grass at positions , , and is all within units of distance.