Cod sursa(job #570958)

Utilizator yaxleyyaxley yaxley Data 3 aprilie 2011 20:00:21
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
#include<deque>
#include<algorithm>
using namespace std;

deque<long long> a;
deque<long long> p;
long n;
long long s;
long k;	
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d", &n);
	scanf("%d", &k);
	long x;

	a.push_front(0);
	p.push_front(0);
	for(long i=1;i<=n;i++)
	{
		scanf("%d", &x);
	
	while(x <= a.back()  && !a.empty())
			{ 	
				a.pop_back();
				p.pop_back();
				
			}
			
		
		a.push_back(x);
		p.push_back(i);
		
		if(p.front() <= i-k)
		{
			a.pop_front();
			p.pop_front();
		}
		
		if(i>=k)
			s=s+a.front();
		
	}
	
	printf("%d ", s);
return 0;
}