Cod sursa(job #59469)

Utilizator scapryConstantin Berzan scapry Data 9 mai 2007 12:38:13
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>

enum { maxn = 500001, inf = 0x3F3F3F3F };

int n, len;
int p[maxn];
int best, best_start, best_end;
int start, end, min, minpos;

void go()
{
	int i;

	best = -inf;

	start = 0;
	end = len - 1;

	while(true)
	{
		min = inf;
		for(i = start; i <= end; i++)
			if(p[i] < min)
			{
				min = p[i];
				minpos = i;
			}

		if(min > best)
		{
			best = min;
			best_start = start;
			best_end = end;
		}

		start = minpos + 1;
		end = start + len - 1;

		if(end >= n) break;
	}

	while(best-start - 1 >= 0 && p[best_start - 1] >= best)
		best_start--;
}

int main()
{
	int i;
	FILE *f = fopen("secventa.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &n, &len);
	for(i = 0; i < n; i++)
		fscanf(f, "%d", &p[i]);

	fclose(f);
	f = fopen("secventa.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
	fclose(f);
	return 0;
}