Cod sursa(job #2087827)

Utilizator abitlazyabitlazy abitlazy Data 14 decembrie 2017 12:37:50
Problema Deque Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 1.11 kb
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();
	}

}