Cod sursa(job #59466)

Utilizator scapryConstantin Berzan scapry Data 9 mai 2007 12:32:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <assert.h>
#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(start != n - len + 1)
	{
		min = inf;
		for(i = start; i <= end; i++)
			if(p[i] < min)
			{
				min = p[i];
				minpos = i;
			}
		assert(min != inf);

		//printf("start %d end %d, min %d at pos %d\n", start, end, min, minpos);
		assert(end > start);
		assert(end - start == len - 1);
		assert(end < n);

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

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

	assert(best != -inf);

	//printf("final start %d end %d, best %d\n", best_start, best_end, best);
	while(best-start - 1 >= 0 && p[best_start - 1] >= best)
		best_start--;

	//printf("brought start down to %d\n", 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();
	//printf("best %d, start %d end %d\n", best, best_start, best_end);

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