I can't get past WA #5.  I know it's an n=500 case, but my solution works for n=500 with various k and passenger data as far as I can tell.   Any other boundary conditions known to be in test 5?

Try data:
3 2
9 2 1
6 3
8

Edited by author 15.10.2012 17:43

I have problems with this test too. My answer is
23
1 3
Is the correct?

But your example is ill-formed because you've included data correct for n=4 but you specify n=3

Assuming you meant "4 2" instead of "3 2",
yes my solution also produces:
23
1 3
which a visual check shows is the correct answer (based on my understanding!   If you have AC and get a different result than "23/1 3", please respond!)

Edited by author 16.10.2012 02:47

I'm beginning to wonder if the test 5 answer set includes all possible correct answers, since in many problems there will be quite a lot of legal answers when there are ties for each maximum span.    Of course everyone thinks their problem is  right and the tests are wrong :).    What is it I'm missing, I must be brainwashed not to see it!   What's wrong with my thinking?

+ add the passenger groups into the corresponding spans
+ greedy approach, take max, then 2nd max, etc., k times
+ make sure to count a particular passenger group only once if it participates in finding one of the k max spans
+ total up each max span,  and output the spans in ascending order

What else is there?   Must be a silly mistake or misunderstanding....!

Yes, I meant "4 2".

I got WA #5 too and my programm correctly work on my example, but I understand that my programm may not work properly in the examples, like the one that I brought.

My example is simple, but it shows that in the first selection, each railroad crossing gives us 12 happy people, but the end result depends on the first choice. If first choice is 2nd, than result — 21 / 1 2

Try it:
5 2
9 11 4 2
4 9 2
8 7
9

48 / 2 4 is wrong answer.

52 / 1 3 is correct.

@samplex: Thank you!   This shows my "choose the first max" greedy approach is wrong.   I suspected this was the problem but didn't work hard enough to come up with a counter-example.    So my code matches my solution approach, but my solution approach was wrong.   Back to the drawing board...  always be skeptical of the greedy approach!

> My example is simple, but it shows that in the first selection, each railroad crossing
> gives us 12 happy people, but the end result depends on the first choice. If first
> choice is 2nd, than result — 21 / 1 2

Yes I missed this point, thanks again.

I am getting correct answer for all the test cases listed here but still I have WA5, any idea why?

If you have WA 5 you may try this test:
4 2
6 9 1
2 20
10
ans:
46
1 3