Cod sursa(job #97869)

Utilizator piroslPiros Lucian pirosl Data 9 noiembrie 2007 02:08:35
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int stack[5001];
int poz[5001];
int begin, end;

void add(int& v, int& pozitie)
{
	while(stack[end] >= v && begin < end)
	{
		--end;
	}
	
	if(stack[end] >= v) 
	{
		stack[end] = v;
	}
	else
	{
		stack[++end] = v;
	}
	poz[end] = pozitie;
}

void print()
{
	for(int i=begin;i<=end;++i)
		printf("(%d / %d) ", stack[i], poz[i]);
	printf("\n");
}


int main(void)
{
	FILE* fin;
	FILE* fout;
	fin = fopen("secventa.in", "r");
	fout = fopen("secventa.out", "w");
	int n, k;
	fscanf(fin, "%d %d\n", &n, &k);

	int max = -30001;
	int start = -1;
	begin = 0;
	end = 0;
	stack[0] = 300001;
	
	int ind, x;
	char sir[1024];
	fgets(sir, 1024, fin), x = ind = 0;
	int l = strlen(sir);
	bool neg = false;
	int i = 0;
	for(; ind < l; ++ind) 
	{
		if(sir[ind] >= '0' && sir[ind] <= '9')
			x = x*10+(sir[ind]-'0');
		else
		{
			if(sir[ind] == '-')
				neg = true;
			else
			{
				if(neg)
					x *= -1;
				//printf("%d\n", x);
				add(x, i);
	
				if(i>=k-1)
				{
					while(i-poz[begin] > k-1)
						++begin;
					if(stack[begin] > max)
					{
						max = stack[begin];
						start = i-(k-1);
					}
				}
				x = 0;
				neg = false;
				++i;
			}
		}
	}

/*	for(int i=0;i<n;++i)
	{
		int v;
		fscanf(fin, "%d ", &v);
		
		add(v, i);
	
		if(i>=k-1)
		{
			while(i-poz[begin] > k-1)
				++begin;
			if(stack[begin] > max)
			{
				max = stack[begin];
				start = i-(k-1);
			}
		}
	}
*/	fclose(fin);
	fprintf(fout, "%d %d %d\n", start+1, start+1+k-1, max);
	fclose(fout);
	return 0;
}