Cod sursa(job #465036)

Utilizator IrnukIrina Grosu Irnuk Data 22 iunie 2010 23:07:15
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <deque>
#define NMAX 5000005
using namespace std;

long n,k;
long long sum;
struct elm
{
	long val;
	long poz;
};

int main()
{
	fstream fin,fout;
	fin.open("deque.in",ios::in);
	fout.open("deque.out",ios::out);

	deque<elm> coada;

	fin>>n>>k;
	for(long i=1;i<=n;i++)
	{
		//elm *e= new elm;
		elm e;
		fin>>e.val;
		e.poz=i;
		
		while(!coada.empty() && coada.back().val >= e.val)
		{
			elm c=coada.back();
			//delete c;
			coada.pop_back();
		}
		coada.push_back(e);

		if(i>=k)
		{
			elm c = coada.front();
			while(i-c.poz>=k)
			{
				c=coada.front();
				//delete c;
				coada.pop_front();
				c=coada.front();
			}

			sum+=c.val;
		}
		
	}
		

	fout<<sum<<'\n';

	fin.close();
	fout.close();
	return 0;
}