Cod sursa(job #1109647)

Utilizator fhandreiAndrei Hareza fhandrei Data 17 februarie 2014 14:12:06
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
// Include
#include <fstream>
#include <deque>
#include <utility>
using namespace std;

// Definitii
#define pii pair<int, int>
#define val first
#define pos second

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

#define ll long long

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

int num, dif;
int readVal;
ll sum;

deque<pii> deck;

// Main
int main()
{
	in >> num >> dif;
	
	for(int i=1 ; i<dif ; ++i)
	{
		in >> readVal;
		while(!deck.empty() && readVal < deck.back().val)
			deck.popb();
		deck.pb(mp(readVal, i));
	}
	
	for(int i=dif ; i<=num ; ++i)
	{
		if(i - deck.front().pos == dif)
			deck.popf();
		
		in >> readVal;
		while(!deck.empty() && readVal < deck.back().val)
			deck.popb();
		deck.pb(mp(readVal, i));
		
		sum += deck.front().val;
	}
	
	out << sum << '\n';
	
	in.close();
	out.close();
	return 0;
}