Cod sursa(job #628749)

Utilizator cristicecCristian Uricec cristicec Data 2 noiembrie 2011 00:26:25
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include<deque>

using namespace std;

deque<int>lista_smen;
deque<int>poz;
int n,k;
int main(){
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d", &n);
	scanf("%d", &k);
	int x;
	int s=0;
	for(int i=1;i<=n;i++){
		scanf("%d", &x);
		if(!lista_smen.empty()){
			if(i-poz.front()==k){
				poz.pop_front();
				lista_smen.pop_front();
			}
			while(x<=lista_smen.back()&&!lista_smen.empty()){
				poz.pop_back();
				lista_smen.pop_back();
			}
		}
			poz.push_back(i);
			lista_smen.push_back(x);
			if(i>=k)
				s=s+lista_smen.front();
				
			

		
	}
	
	printf("%d", s);
	return 0;
	
}