Cod sursa(job #97882)

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

const int MAX = 128*1024;
char sir[MAX];

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[MAX];
	x = ind = 0;

	bool neg = false;
	int i = 0;

	while(fgets(sir, MAX, fin) != NULL)
	{
		//int l = strlen(sir);
		
		for(; sir[ind] != '\0'; ++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;
				}
			}
		}
		ind = 0;
	}

/*	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;
}