Mod is involved in this problem so u can’t compare two values directly.The approach in the editorial is really good, u can’t store product of values ,but we can store log of it and us it for comparison of different options.
log(a * b * c * d) = log( a ) + log( b ) + log( c ) + log( d )
So we can make a priority queue of pairs and store the log value as the first entry and its index as the second entry.
So using priority queue we can get the optimal position from [i-k , i-1] to reach ith index . Each time pop until the top value of queue is less than i-k and hence we can notice, each value is inserted and poped only once, so Time complexity is O(N) and to get the answer
we can make another array side by side and when we get the best position from prev k steps , we can update its value in the array.
For Reference u can have a look at my code : https://www.codechef.com/viewsolution/36173158