Any hints for this one? It can be done in O(n) with dynamic programming, but even that is way too slow for K = 1e9...
I’m in the same boat. I have an O(n) solution, but it’s too slow for 1e9 input as well even written in go.
Googling turns up this from the problem author, but he loses me right where he says “it’s easy to see…”