Cod sursa(job #465031)

Utilizator IrnukIrina Grosu Irnuk Data 22 iunie 2010 22:53:50
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <deque>
#define NMAX 5000005
using namespace std;

long n,k,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;
		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;
}