Pagini recente » Cod sursa (job #1793081) | Cod sursa (job #2475654) | Cod sursa (job #2871151) | Cod sursa (job #940565) | Cod sursa (job #2087827)
import java.io.*;
import java.util.*;
public class Main {
private static final String INPUT_FILE_PATH = "deque.in";
private static final String OUTPUT_FILE_PATH = "deque.out";
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader(INPUT_FILE_PATH));
PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
Deque<Integer> deQueue = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
if (i < k) {
while (!deQueue.isEmpty() && arr[deQueue.getLast()] >= arr[i]) {
deQueue.removeLast();
}
deQueue.addLast(i);
}
}
long sumMin = arr[deQueue.getFirst()];
for (int i = k; i < n; ++i) {
while (!deQueue.isEmpty() && (arr[deQueue.getLast()] >= arr[i])) {
deQueue.removeLast();
}
while (!deQueue.isEmpty() && (i - k >= deQueue.getFirst())) {
deQueue.removeFirst();
}
deQueue.addLast(i);
sumMin += arr[deQueue.getFirst()];
}
out.println(sumMin);
out.flush();
in.close();
out.close();
}
}