asif_iut's blog

a problem from a recent contest
By asif_iut, 14 years ago, In English
Given a list of advertisements for a building choose the ones which maximized the total income from the advertisements. Each advertisements spans the whole face of the building, so no two advertisements can occupy the same floor and no floors can be partially occupied.

Input starts with an integer N, denoting the total number of advertisements. Each advertisements is described using three integers, A ( 0 <= A <= 10 ^ 5 ) , B( 1 <= B <= 10 ^ 5 ) and C ( 1 <= C <= 1000 ) denoting the lowest floor of the advertisement, the number of floor the advertisement covers( including the lowest floor ) and the money earned from placing it, respectively.


Sample Input:
3
1 5 1
2 10 3
7 12 1

Ans : 3

how can this problem be solved ?
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Sort the ads by their lowest floors and then you can do a DP.
If you want to use an ad, think of what all the ads it'll block.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
the problem i faced during the contest is to keep the records of the advertisements states. which ads cannot be taken as a result of picking an ad.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In the contest We tried  binary search + dp . But could not  got AC.May be a bug in binary search . Binary search was to find  " if we take ad i which next ad we can take ".

→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
EDIT:

Ok I realised Sanzee's solution is the same XD
→ Reply