We will loop from 1 to N and at each step dp[i][j] will be the number of increasing subsequences of length i ending at element with value j. Let's say that the current element is a[i]. Obviously, this is a new subsequence of length 1 ending at a[i]. So we will do ++dp[1][a[i]]. Then for j from 2 to K we will do dp[j][a[i]]+=(dp[j-1][1]+dp[j-1][2]+dp[j][3]+...+dp[j-1][a[i]-1]) since we can extend every subsequence of length j-1 which ends in an element which is less that the current one :)

Here is my submission — http://mirror.codeforces.com/contest/597/submission/14321058 :)

bad

yeeeeee