Cod sursa(job #494647)

Utilizator ChallengeMurtaza Alexandru Challenge Data 22 octombrie 2010 14:43:58
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <deque>

using namespace std;

const char InFile[]="deque.in";
const char OutFile[]="deque.out";

ifstream fin(InFile);
ofstream fout(OutFile);

struct s
{
	s(int x2=0, int pos2=0):x(x2),pos(pos2){}
	int x,pos;
};

long long sol;
int n,k,x;
deque<s> d;

int main()
{
	fin>>n>>k;
	for(register int i=1;i<=k;++i)
	{
		fin>>x;
		while(!d.empty())
		{
			if(d.back().x<x)
			{
				break;
			}
			d.pop_back();
		}
		d.push_back(s(x,i));
	}
	sol+=(long long)d.front().x;
	for(register int i=k+1;i<=n;++i)
	{
		fin>>x;
		while(!d.empty())
		{
			if(d.back().x<x)
			{
				break;
			}
			d.pop_back();
		}
		d.push_back(s(x,i));
		while(d.front().pos<=i-k)
		{
			d.pop_front();
		}
		sol+=(long long)d.front().x;
	}
	fin.close();
	
	fout<<sol;
	fout.close();
	return 0;
}