Cod sursa(job #694376)

Utilizator Daniel30daniel Daniel30 Data 27 februarie 2012 20:32:23
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <cstdio>
#include <vector>
#include <deque>
using namespace std;
int n,k,x;
vector<int> a; deque<int> d;
long long Sum;
int main()
{freopen("deque.in", "rt", stdin);
 freopen("deque.out", "wt", stdout);
 scanf("%d %d ", &n, &k);
 for (register int i=0;i<n;++i)  scanf("%d ",&x),a.push_back(x);
 if(a[0]<a[1] && a[0]<a[2]) Sum=a[0];
 for (register int i=0;i<n;++i)
	{while (!d.empty() && a[i]<=a[d.back()]) d.pop_back();		
	 d.push_back(i);
	 if (d.front() == i-k) d.pop_front();
	 if (i >= k) Sum += a[d.front()]; 	
	}
 printf("%lld\n",Sum);
 return 0;
}