Cod sursa(job #570955)

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

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

	a.push_front(0);
	p.push_front(0);
	for(int 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);
		int l= p.front();
		if(l <= i-k)
		{
			a.pop_front();
			p.pop_front();
		}
		
		if(i>=k)
			s=s+a.front();
		
	}
	
	printf("%d", s);
return 0;
}