Cod sursa(job #2502282)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 30 noiembrie 2019 17:12:37
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <deque>
using namespace std;
long long n,k,nr,suma;
deque < pair <int,long long> > chestie;
int main () {
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%lld%lld", &n, &k);
	for(int i=1;i<k;++i) {
		scanf("%lld", &nr);
		if(chestie.empty())
			chestie.push_back(make_pair(i,nr));
		else {
			while(!chestie.empty() && chestie.back().second>=nr)
				chestie.pop_back();
			chestie.push_back(make_pair(i,nr));
		}
	}
	//suma+=chestie.front().second;
	for(int i=k;i<=n;++i) {
		scanf("%lld", &nr);
		if(chestie.empty())
			chestie.push_back(make_pair(i,nr));
		else {
			while(!chestie.empty() && chestie.back().second>=nr)
				chestie.pop_back();
			chestie.push_back(make_pair(i,nr));
		}
		if(i-chestie.front().first>=k)
			chestie.pop_front();
		suma=suma+chestie.front().second;
	}
	printf("%lld", suma);
	return 0;
}