Cod sursa(job #74852)

Utilizator dzsDonca Zsolt dzs Data 28 iulie 2007 21:18:37
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
// secventa.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

#pragma warning(disable : 4996) // ms visual c++ stuff

const int max = 500001;
const int minlimit = -30000;
const int maxlimit = +30000;
const int limit = maxlimit - minlimit + 1;

int a[max] = {0}, b[limit] = {0};

int main(int argc, char* argv[])
{
	FILE *f = fopen("secventa.in", "r");

	int n, k;
	fscanf(f, "%d %d", &n, &k);

	int minb;
	for(int i=0;i<k;i++)
	{
		int h;
		fscanf(f, "%d", &h);

		static int min = h;

		a[i] = h;
		b[h - minlimit]++;

		if (min > h)
		{
			min = h;
		}

		if (i == k-1)
		{
			minb = min;
		}
	}

	int minii = 0, absmin = minb, absmini = 0;
	
	for(int i=k;i<n;i++)
	{
		int h;
		fscanf(f, "%d", &h);
		
		a[i] = h;
		b[a[i]-minlimit]++;
		b[a[i-k]-minlimit]--;

		if (a[i-k] == minb)
		{
			int j;
			for(j=minb+1; j < limit && b[j-minlimit] == 0 ; j++) {}
			
			minb = j;
			minii = i;
		}

		if (minb > h)
		{
			minb = h;
			minii = i;
		}

		if (absmin < minb)
		{
			absmin = minb;
			absmini = minii;
		}
	}
	fclose(f);

	f = fopen("secventa.out", "w");
	fprintf(f, "%d %d %d", absmini-k+2, absmini+1, absmin);
	fclose(f);

	return 0;
}