Antu is analyzing peak passenger counts across sliding time windows on his route and wants the SUM of the maximum passenger count in every window of a fixed size. Given N integers and window size K, for every contiguous window of size K compute its maximum, and print the SUM of all these window-maximums. Use a monotonic deque for O(N), not a heap or O(N*K) brute force.
Input
Line1: N K. Line2: N integers.
Output
Sum of all window maximums.
Constraints
1 ≤ K ≤ N ≤ 10^5
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
36
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.