Cod sursa(job #332185)

Utilizator szabotamasSzabo Tamas szabotamas Data 16 iulie 2009 22:34:29
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <iostream>
#include <fstream>

long v[15],dq[15],i,n,k,beg,end;
long long sum;

using namespace std;

int main(){
	ifstream fin ("deque.in");
		fin >> n >> k;
		for (i=1; i<=n; i++){
			fin >> v[i];
		}
	fin.close();
		beg=1;
		end=0;
		for (i=1; i<=n; i++){
			while (beg<=end && v[dq[end]]>=v[i]){
				--end;
			}
			end++;
			dq[end]=i;
			if (dq[beg]==i-k) beg++;
			if (i>=k){
				sum+=v[dq[beg]];
			}
		}
	ofstream fout ("deque.out");
		fout << sum;
	fout.close();
	return 0;
}