Cod sursa(job #628756)

Utilizator cristicecCristian Uricec cristicec Data 2 noiembrie 2011 00:49:06
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 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);
	
	long long s=0;
	int x;
	for(int i=1;i<=n;i++){
		
		scanf("%d", &x);
		if(!lista_smen.empty()){
			
			while(x<=lista_smen.back()){
				poz.pop_back();
				lista_smen.pop_back();
				if(lista_smen.empty())
					break;
			}
			}
			
		
			poz.push_back(i);
			lista_smen.push_back(x);
			
			if(i-poz.front()==k){
				poz.pop_front();
				lista_smen.pop_front();
			}
			if(i>=k){
				
				s=s+lista_smen.front();
			}	
			

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