Cod sursa(job #343716)

Utilizator aladinaladin aladinn aladin Data 26 august 2009 22:42:51
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
//la ce te uiti....
using namespace std;
#include <cstdio>
#include <deque>
deque <int> D;
int n, k, i, v[5000010];
long long sol;


int main(){

	freopen("deque.in", "r",stdin);
	freopen("deque.out", "w",stdout);

	scanf("%d %d %d", &n, &k,&v[1]);
	D.push_back(1);
	for (i = 2; i <= n; i++)
	{scanf("%d", &v[i]);
	 while( !D.empty() && D.front() <= i - k )	D.pop_front();
	 while( !D.empty() && v[i] <= v[ D.back() ] ) D.pop_back();
	 D.push_back(i);
	if(i >= k)
			sol+= (long long)v[ D.front() ];
	 }
	
	printf("%lld", sol);
	
return 0;
}