Cod sursa(job #21558)

Utilizator amadaeusLucian Boca amadaeus Data 23 februarie 2007 20:46:05
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <deque>

using namespace std;

typedef pair< int, int > p;

int main() {
	deque< p > d;
	p x;
	int best = -66666, poz, N, K;
	
	ifstream Fin( "secventa.in" );
	ofstream Fout( "secventa.out" );

	Fin >> N >> K;
	Fin >> x.second;
	x.first = 1;
	d.push_back( x );
	
	for( int i=2; i<=N; i++ ) {
		if( d.front().first <= i-K )
			d.pop_front();

		Fin >> x.second;
		x.first = i;

		int gata = 0;
		do {
			if( !d.empty() )
				if( d.back().second >= x.second )
					d.pop_back();
				else
					gata = 1;
			else
				gata = 1;
		}
		while( !gata );
		d.push_back( x );

		if( best < d.front().second ) {
			poz = i;
			best = d.front().second;
		}
	}
	Fout << poz - K + 1 << " " << poz << " " << best << endl;
	return 0;
}