Cod sursa(job #586859)

Utilizator david95szabo david emanuel david95 Data 3 mai 2011 08:57:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int main()
{
	int n, k, st, dr, rez, poz, a[5000], q[5000], i;
	fin >> n >> k;
	for ( i = 1; i <= n; i++ )
		fin >> a[i];
	rez = 99999;
	st = 1;
	dr = 0;
	for ( i = 1; i <= k - 1; i++ )
	{
		while ( dr >= st && a[i] <= a[q[dr]]  )
			dr = dr -1;
			dr = dr + 1;
			q[dr] = i;
	}
	for ( i = k; i < n; i++ )
	{
		while ( st <= dr && a[i] <= a[q[dr]])
			dr = dr - 1;
		dr = dr + 1;
		q[dr] = i;
		while ( st <= dr && q[st] < i - k + 1 ) 
			st = st + 1;
		if ( a[q[st]] > rez )
		{
			rez = a[q[st]];
			poz = i;
		}
	}
	fout << poz - k +1 << " " << poz << " " << rez << endl;
	fin.close();
	fout.close();
}