Cod sursa(job #427482)

Utilizator miticaMitica mitica Data 27 martie 2010 21:38:14
Problema Deque Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.46 kb
# include <algorithm>
# include <deque>
# define nmax 5000005

using namespace std;

int n,k,a[nmax];
long long s;
deque <int> Q;

int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d %d", &n, &k);
	for (int i=1;i<=n;i++)
		scanf("%d", &a[i]);
	for (int i=1;i<=n;i++)
	{
		while (!Q.empty() && a[i]<=a[Q.back()]) Q.pop_back();
		Q.push_back(i);
		if (i>=k) s+=a[Q.front()];
	}
	printf("%lld", s);
	return 0;
}