Cod sursa(job #749733)

Utilizator fhandreiAndrei Hareza fhandrei Data 18 mai 2012 14:57:12
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
//Include
#include <fstream>
#include <deque>
#include <utility>
using namespace std;

//Definitii
#define value first
#define id second 
#define frontValue d.front().value
#define frontId d.front().id
#define backValue d.back().value
#define backId d.back().id
#define ll long long

#define popb pop_back
#define pb push_back
#define popf pop_front
#define pf push_front
#define mp make_pair

//Variabile
ifstream in("deque.in");
ofstream out("deque.out");

int elements, limit;
int newValue;
ll sum;

deque<pair<int, int> > d;

//Main
int main()
{
	in >> elements >> limit;
	
	for(int i=1 ; i<limit ; ++i)
	{
		in >> newValue;
		while(!d.empty() && newValue <= backValue)
			d.popb();
		d.pb(mp(newValue, i));
	}
	
	for(int i=limit ; i<=elements ; ++i)
	{
		in >> newValue;
		while(!d.empty() && newValue <= backValue)
			d.popb();
		d.pb(mp(newValue, i));
		
		if(frontId == i - limit)
			d.popf();
		
		sum += (ll)frontValue;
	}
	
	out << sum;
	
	in.close();
	out.close();
	return 0;
}