Hello everyone!
Since, I've found out that I'm weak at DP tagged problems, I decided to fix it, now I'm struggling at one really cool problem.
The problem is 588D - Duff in Beach. I found a solution but after reading the editorial I realized that it solves different problem. Perhaps I misunderstood the problem. So, please explain the following case where I think answer should be 48 but it's 30:
3 12 2
5 9 1
Author's output: 30, but there are 48 non-decreasing subsequences, e.g.
5 9 1 5 9 1 5 9 1 5 9 1 --> b
1 2 3 4 5 6 7 8 9 10 11 12 --> positions
length 1 subsequence 12
length 2:
1-4,1-5,1-7,1-8,1-10,1-11,2-5,2-8,2-11,3-4,3-5,3-6,3-7,3-8,3-9,3-10,3-11,3-12,
4-7,4-8,4-10,4-11,5-8,5-11,6-7,6-8,6-9,6-10,6-11,6-12
7-10,7-11,8-11,9-10,9-11,9-12
total 36+12 = 48
Thanks in advance!
Any help'll be appreciated!
