Cod sursa(job #513155)

Utilizator redls_95Nechita Laura redls_95 Data 15 decembrie 2010 11:09:27
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
const int N=5000005;
int v[N];
int dq[N];
int n,k,i,j,min,max,s=0,st,dr;
inline void dreapta(int i)
{
	while(st<=dr &&v[dq[dr]]>=v[i])
	{
		--dr;
	}
}
inline void stanga(int i)
{
	if (i-dq[st]==k) ++st;
}
inline void adauga(int i)
{
	dq[++dr]=i;
}
int main()
{
	in>>n>>k;
	for(i=1;i<=n;i++)
		in>>v[i];
	//st=1;
	dr=-1;
	for(i=1;i<=k;++i)
	{
		dreapta(i);
		adauga(i);
		//dq[++dr]=i;
	}
	s=v[dq[st]];
	for(;i<=n;++i)
	{
		stanga(i);
		dreapta(i);
		adauga(i);
		s=s+v[dq[st]];
	}
	out<<s;
	return 0;
}