Cod sursa(job #702076)

Utilizator fhandreiAndrei Hareza fhandrei Data 1 martie 2012 19:25:50
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
//Ce stil am ;x
//Include
#include <stdio.h>
#include <deque>
using namespace std;

//Constante
const int MAX_SIZE=5000010;

//Variabile
FILE *in,*out;

int n,k;
int v[MAX_SIZE];
long long int suma;

deque<int> d;

//Main
int main()
{
	in=fopen("deque.in","rt");
	out=fopen("deque.out","wt");
	fscanf(in, "%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		fscanf(in, "%d",&v[i]);

	for(int i=1;i<k;++i)
	{
		while(!d.empty() &&v[i]<=v[d.back()])
			d.pop_back();
		d.push_back(i);
		if(d.front()==i-k)
			d.pop_front();
	}

	for(int i=k;i<=n;++i)
	{
		while(!d.empty() &&v[i]<=v[d.back()])
			d.pop_back();
		d.push_back(i);
		if(d.front()==i-k)
			d.pop_front();
			suma+=(long long int)v[d.front()];

	}

	fprintf(out, "%lld",suma);
	fclose(in);
	fclose(out);
	return 0;
}

//Ce stil am ;x