Cod sursa(job #688811)

Utilizator an_drey_curentandreycurent an_drey_curent Data 23 februarie 2012 21:09:21
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
#include<deque>
#define MAX 5000005
using namespace std;
long long int N,K,v[MAX],S=0;
deque<int>COADA;
void deschidere()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
}
void citire()
{
	scanf("%lld%lld",&N,&K);
	for(int i=0;i<N;i++)
		scanf("%lld",&v[i]);
}
void rezolvare()
{
	int i;
	for(i=0;i<N;i++)
	{
		while( COADA.size() && v[i]<v[COADA.back()] )
			COADA.pop_back();
		COADA.push_back(i);
		if(COADA.front() == i-K)
			COADA.pop_front();
		if(i>=K-1)
			S+=v[COADA.front()];
	}
	printf("%lld",S);
}
int main()
{
	deschidere();
	citire();
	rezolvare();
	return 0;
}