Cod sursa(job #21604)

Utilizator amadaeusLucian Boca amadaeus Data 23 februarie 2007 21:39:57
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>

struct S {
	int index, val;
};

typedef struct S S;

S d[50001];
int front, back;
int N, K;

int main() {
	S x;
	int i, poz, best;
	
	freopen( "secventa.in", "r", stdin );
	scanf( "%d%d", &N, &K );

	front = back = 1;
	poz = 1; best = -66666;

	for( i=1; i<=N; i++) {
		x.index = i;
		scanf( "%d", &x.val );

		while( front - 1 != back && d[back].val >= x.val )
			back --;

		d[ ++back ] = x;

		if( d[front].index <= i-K )
			front++;
		if( i>=K && best < d[front].val ) {
			poz = i;
			best = d[front].val;
		}
	}

	freopen( "secventa.out", "w", stdout );
	printf( "%d %d %d\n", poz-K+1, poz, best );
	return 0;
}