Cod sursa(job #21880)

Utilizator amadaeusLucian Boca amadaeus Data 24 februarie 2007 21:05:27
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>

typedef struct S {
	int poz, val;
} S;

int main() {
	const int NMAX = 1024;
	int x, i, fl, N, K, best = -66666, poz = 0, first, last;
	S d[50001];
	char input[1030];
	char *p;
	register char ch;

	freopen( "secventa.in", "r", stdin );
	freopen( "secventa.out", "w", stdout );

	scanf( "%d %d\n", &N, &K );
	first = last = 1;
	fgets( input, NMAX, stdin );

	p = input;
	for( i=1; i<=N; i++ ) {
		fl = 1; x = 0;
		for( ; *p != ' ' && *p != '\n'; ) {
			ch = *p;

			if( ch >= '0' && ch <= '9' )
				x = x*10 + ch - '0';
			else
				if( ch == '-' )
					fl = -1;

			p++;
			if( p - input >= NMAX - 1 ) {
				fgets( input, NMAX, stdin );
				p = input;
			}

		}
		p++; x *= fl;

		//printf( "%d\n", x );
		//elimina elementele vechi din fata
		while( first <= last && d[first].poz <= i-K )
			first++;
		//elimina elementele prea mari din spate
		while( first <= last && d[last].val >= x )
			last--;
		//adauga x in spate
		last++;
		d[last].poz = i;
		d[last].val = x;

		//actualizeaza maxim
		if( i >= K )
			if( best < d[first].val ) {
				best = d[first].val;
				poz = i;
			}
	}
	printf( "%d %d %d\n", poz - K + 1, poz, best );
	return 0;
}