Cod sursa(job #36024)

Utilizator diac_paulPaul Diac diac_paul Data 22 martie 2007 20:54:08
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define nmax 500005

FILE *fin, *fout;

long n, k, a[nmax];

void read_data()
{
	long i;

	fin = fopen("secventa.in", "rt");
	fout =  fopen("secventa.out", "wt");

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

	for (i = 0; i < n; i++)
	{
		fscanf(fin, "%ld", &a[i]);

	}
}

long in, sf, c[nmax];

void solve()
{
	long i;
	long sm, fm, vm = -30005;

	in = 0;  sf = 0;  c[0] = 0;

	for (i = 1; i < n; i++)
	{
		//introduc a[i] in coada

		while ( a[ c[sf] ]> a[i] && sf>=in ) sf--;

		sf++;
		c[sf] = i;

		//scot din coada elementele care nu sunt din [i-k+1, i] => am toate minimile din [i-k+1, i] in coada, sortate

		while ( c[in] < i-k+1 ) in++;

		//retin noua solutie, daca e mai buna

		if ( a[ c[in] ] > vm  && i-k+1 >= 0)
		{
			vm = a[ c[in] ];
			sm = i-k+1;
			fm = i;
		}
	}
	
	fprintf(fout, "%ld %ld %ld\n", sm + 1, fm + 1, vm);
}

int main()
{
	read_data();

	solve();

	fclose(fin);
	fclose(fout);

	return 0;
}