Can anyone pls tell the approach to this problem…?? I tried sliding window approach but only few subtasks passed.
You could have used Binary Search using prefix sum array. It could be done like this:
For each index starting from 1 (1-indexed), find a lower bound of K (binary search) of range sum starting from this index. Just find the maximum range sum not exceeding K this way. It is an O(N\log_{2}{N}) solution.
Hope it helps!
Will those problems not be moved to practice section?? Bcoz I can’t see any submit option yet
Sliding window does work in it. Are you sure you used long long and not int for your datatypes ? Or can you share your WA approach ?
Here’s my wrong submission
https://www.codechef.com/viewsolution/28589974
But I think I found my mistake instead of pushing (sm-a[I]) into vector I just pushed sm in it but I can’t test it now since submit option is unavailable
U may use kadane’s algorithm for O(n) solution
Actually I had already emailed CodeChef Admin to move the problems to practice section. It’s just that there’s no reply yet. It’s taking unexpectedly long, I know. Because they should’ve been moved to practice latest by today morning itself. And now it’s been quite a few hours.
Please be patient, they might move to practice in some time today.
Cheers!