Building Profit Plan
Time limit2sMemory limit128 MB
Given points with profits, select a subset maximizing total profit such that every chosen point sees other chosen points only in diagonal quadrant pairs (1,3) or (2,4) relative to itself.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Sorting, Divide and conquer
- Solved
- No attempts yet
Problem
There are several candidate buildings in a city. Each candidate has a distinct x-coordinate and y-coordinate, and building it gives a fixed profit. Choose some of the buildings so that the total profit is as large as possible.
For any chosen building, divide the plane into four regions around it. Region 1 contains points with both larger x and larger y. Region 2 contains points with smaller x and larger y. Region 3 contains points with both smaller x and smaller y. Region 4 contains points with larger x and smaller y.
For the city to look good, every chosen building must satisfy this condition. From that building's point of view, other chosen buildings must not appear in any adjacent pair of regions: 1 and 2, 1 and 4, 2 and 3, or 3 and 4. In other words, the other chosen buildings must lie only in the diagonal regions 1 and 3, or only in the diagonal regions 2 and 4. Having buildings in only one region is also allowed.
Find the maximum total profit obtainable while satisfying this condition.
Input
The first line contains the number of candidate buildings N. (1 <= N <= 1,000)
Each of the next N lines contains three integers x, y, and c: the coordinates of a candidate building and the profit gained by building it. (1 <= x, y <= 1,000,000,000, 1 <= c <= 50,000)
No two different buildings have the same x-coordinate, and no two different buildings have the same y-coordinate.
Output
Output the maximum profit obtainable by choosing buildings that satisfy the condition.