REVAMP THE CITY
All submissions for this problem are available.
There is a city, that has a straight road of length L meters and width 0. Coordinate x
on the road denotes point that is at x meters from the start of the road. That is coordinate 0
denotes beginning of the road and coordinate L denotes end of the road. The road has to be
painted with color. There are K proposals, Each proposal is of the form a, b, c which means that the road can be painted from coordinate a to coordinate b for the cost c. Note that some part of road can be painted multiple times and it is still considered to be painted.
The mayor wants to know if the whole road can be painted and if possible, also wants to know the minimum cost that is required to paint the entire road.
First line of the input is the number of test cases T. It is followed by T test cases.In each test
case first line has two space separated integers, the length of the road L and the number of
proposals K. It is followed by K lines, which are K proposals, each proposal is 3 space separated
integers a b and c.
For each test case output a single integer, that is minimum cost required to paint the entire road. If it is impossible to paint the entire road, print -1.
- 1 <= T <= 10
- 1 <= L <= 256
- 1 <= K <= 512
- 0 <= a < b <= L
- 1 <= c <= 1000
Input: 3 9 6 2 7 10 7 8 3 3 4 8 0 8 2 5 6 4 3 7 1 9 6 7 8 6 6 9 6 2 5 8 3 6 10 0 7 6 2 9 1 3 4 0 3 8 0 2 4 0 1 10 2 3 8 Output: -1 7 8
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.