What in this test?
I use AVL trees and calculate result with binomial coefficient's. Where i mistaken?

Interval tree is enough.
I wrote solution based on binomial coefficient's, but it's almost wrong(WA 9).
My new program, DP O(n * k * logn ) gets AC.

Edited by author 20.02.2007 21:23

Edited by author 20.02.2007 21:23

I used direct calculation of bin cofficents from factorials.

Answer := SUM[ C(k - 1)(n) ]   for each ai
where n is the number elements greater tha ai in subsequance from 0 till ai.

However also WA4... Why?

Try this test:

Input:
6 3
6 2 3 1 5 4

Output:
3

Also test
5 3
5 2 1 4 3
breaks this approach