Cod sursa(job #686017)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 21 februarie 2012 12:47:56
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
struct miau{int x,poz;} rc;
deque <miau> c;
long long smn;

int main() {
	int n,i,k,x;
	ifstream f("deque.in");
	ofstream g("deque.out");
	f>>n>>k;
	for (i=1; i<=n; i++) {
		f>>x;
		rc.x=x;
		rc.poz=i;
		if (c.size())
		while (c.size()&&c[c.size()-1].x>x)
			if (c.size())
				c.pop_back();
		c.push_back(rc);
		if( c[0].poz+k-1<i)
			c.pop_front();
		if (i>=k) 
			smn+=c[0].x;
	}
	g<<smn<<'\n';
	g.close();
	return 0;
}