During the OpenCup I've accepted the problem with complexity O(N*K^2), but here, on timus, only optimizations helped me to beat timelimit with this algo. At the same time, some people have AC-times 0.015 or something like that. Is it possible to solve the problem with more efficient algo?

O(N*K)
my implementation is not so fast because of recursion

O(N*K). Are you sure it's still O(N*K) with recursion?

I could adopt only O(N*K*10) in DP

I got confused.
My program is very short and the complexity is O(N*K). I didn't find anything hard when solving this.
I think you must have made it harder in thought.

BTW, not O(N*K*M), but O(N*K). M is the modulo(10 here).

Edited by author 21.10.2010 23:19

Edited by author 21.10.2010 23:19