Cod sursa(job #728325)

Utilizator OwnedCheciches Marius Owned Data 28 martie 2012 17:26:09
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;

int main(){
	long long n,i,k,s=0,x;
	vector <long long> a;
	deque <long long> d;
	ifstream f("deque.in");
	ofstream g("deque.out");
	f>>n>>k;
	k--;
	for(i=1;i<=n;i++){
		f>>x;
		a.push_back(x);}
	d.push_front(0);
	for(i=1;i<n;i++){
		while(a[i]<a[d.back()])
			d.pop_back();
		d.push_back(i);
		if(d.front()==i-k-1)
			d.pop_front();
		if(i>=k)
			s=s+a[d.front()];}
	g<<s;
	f.close();
	g.close();
	return 0;}