Cod sursa(job #424126)

Utilizator darrenRares Buhai darren Data 24 martie 2010 16:51:30
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<deque>
using namespace std;

void read();
void write();

deque<pair<int, int> > d;
long long s;
int n, k;

int main() {
	read();
	write();
	return 0;
}

void read() {
	ifstream fin("deque.in");
	fin >> n >> k;
	int i, aux;
	for (i = 0; i < k; ++i) {
		fin >> aux;
		while (!d.empty() && aux < d.front().first)
			d.pop_front();
		d.push_front(make_pair(aux, i));
	}
	s += d.back().first;
	for (i = k; i < n; ++i) {	
		if (i - d.back().second >= k)
			d.pop_back();
			
		fin >> aux;
		while (!d.empty() && aux < d.front().first)
			d.pop_front();
		
		d.push_front(make_pair(aux, i));
		
		s += d.back().first;
	}
	fin.close();
}

void write() {
	ofstream fout("deque.out");
	fout << s;
	fout.close();
}