Cod sursa(job #579104)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 11 aprilie 2011 20:55:27
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<cstdio>
#include<queue>
#define Nmax 5000001

using namespace std;

int N,K,v[Nmax];

deque <int> a;

long long sol;

int main(){
	
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	
	scanf("%d%d",&N,&K);
	
	for(int i=1;i<=N;++i){
		
		scanf("%d",&v[i]);
		
		while(!a.empty() && v[i] < v[a.back()])
			a.pop_back();
		a.push_back(i);
		
		if(i-a.front() >=K )
			a.pop_front();
		
		if(i>=K)
		   sol+=v[a.front()];

	}
	
	printf("%lld\n",sol);
	
return 0;
}