Cod sursa(job #628754)

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

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