Wangnuni the Frog
Time limit1sMemory limit128 MB
Find the path from leaf 1 to leaf N using only rightward or upward axis-aligned jumps costing K power each, that maximizes leftover power after eating flies along the way.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Sorting, Segment tree
- Solved
- No attempts yet
Problem
Wangnuni the frog lives in a pond with N lotus leaves, numbered 1 to N. Seen from above, each leaf's position is a point on the 2D plane. The frog can only jump along axis-parallel directions and only in the positive direction. That is, to jump from (x1, y1) to (x2, y2), one of the following must hold.
- x2 > x1 and y2 = y1
- y2 > y1 and x2 = x1
Each jump costs K power. If the frog's power is less than K, it cannot jump anymore. The frog starts on leaf 1 and wants to reach leaf N, and its initial power is 0.
Each leaf has flies. The frog can eat the flies on the leaf it is standing on, and each fly eaten restores 1 power. Since the initial power is 0, note that the frog must first eat the flies on leaf 1 to gain power before it can make its first jump.
When the frog moves according to the rules and arrives at leaf N, find the maximum power it can have upon arrival.
Input
The first line contains the number of leaves N and the power K needed for one jump. (2 ≤ N ≤ 300000, 1 ≤ K ≤ 1000)
Each of the next N lines gives a leaf's coordinates X, Y and its number of flies F, in that order. The information on the (i+1)-th line describes leaf i. All leaf coordinates are distinct. (0 ≤ X, Y ≤ 100000, 0 ≤ F ≤ 1000)
The input is always given so that a way to reach leaf N exists.
Output
Print, on one line, the maximum power the frog can have after arriving at leaf N.