For those who solved this in Java with a lots of tricks. Thumbs up!

Take a look at P1148. It's really similar. E.g. simple DP problem, which becomes stick in ass with Time + Memory limits :)

I just don't get why this task has kindof 'small' difficulty, and P11048 has 'large' difficulty.

I'd say this was much more harder than P1148 for me to get AC in Java.