Cod sursa(job #98064)

Utilizator alle_forever13Alexandra Retegan alle_forever13 Data 9 noiembrie 2007 21:34:28
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>

#define dim 5001

#define input  "secventa.in"
#define output "secventa.out"

int  a[dim], q[dim];

long n, k, i, st, dr, rez, poz;

int main()
{

	FILE *in, *out;

	in = fopen (input, "r");
	out = fopen (output, "w");

	fscanf(in, "%ld%ld", &n, &k);

	for(i=1; i<=n; i++)

		fscanf(in, "%ld", &a[i]);


	rez = -30001;

	for ( i = 1; i <= k-1; i ++ )
	{
		while ( (dr>=st) && (a[i]<=a[q[dr]]) )

			dr --;

		q[++dr] = i;



	}

	for ( i = k; i <= n; i ++)
	{
		while ( (st <= dr) && (a[i]<=a[q[dr]]) )

			dr --;

		q[++dr] = i;

		while ( (st<=dr) && (q[st]<i-k+1) )

			st ++;

		if ( a[q[st]] > rez )
		{
			rez = a[q[st]];
			poz = i;
		}
	}

	fprintf(out, "%ld% ld% ld\n", poz-k+1,poz,rez);

	return 0;
}