Cod sursa(job #2184184)

Utilizator DimaTCDima Trubca DimaTC Data 23 martie 2018 20:06:24
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.39 kb
#include<bits/stdc++.h>

using namespace std;

deque<int>Q;
int a[5000010],s,n,k;

int main() {
	ifstream cin("deque.in");
	ofstream cout("deque.out");
	cin>>n>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		while (Q.size() && a[i]<a[Q.back()]) Q.pop_back();
		while (Q.size() && i-Q.front()>=k) Q.pop_front();
		Q.push_back(i);
		if (i>=k) s+=a[Q.front()];
	}
	cout<<s;
	return 0;
}