Cod sursa(job #21847)

Utilizator amadaeusLucian Boca amadaeus Data 24 februarie 2007 18:13:38
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>

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

int main() {
	int x, i, N, K, best = -66666, poz = 0, first, last;
	S d[50001];

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

	scanf( "%d%d", &N, &K );
	first = last = 1;
	for( i=1; i<=N; i++ ) {
		scanf( "%d", &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;
}