Cod sursa(job #84177)

Utilizator vladcoderVlad Ion vladcoder Data 13 septembrie 2007 20:02:37
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define FIN "secventa.in"
#define FOUT "secventa.out"

vector<int> A, DEQ;
FILE * fin, * fout;
int N, K, x, MIN, right, i, v;

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d %d\n", &N, &K );
	for( i = 0; i < N; i++ )
	{
		fscanf( fin, "%d", &v );
		A.push_back(v);
	}
for( i = 0; i < K; i++ )
{
	while ( !DEQ.empty() && A[ DEQ.back() ] > A[i] ) DEQ.pop_back();
	DEQ.push_back( i );
}
   MIN = A[ DEQ.front() ]; right = K - 1;

	for( i = K; i < N; i++ )
	{
		while( !DEQ.empty() && A[ DEQ.back() ] > A[i] ) DEQ.pop_back();
		DEQ.push_back(i);
		while ( !DEQ.empty() && i - DEQ.front() >= K ) DEQ.erase( DEQ.begin() );
		if ( A[ DEQ.front() ] > MIN )
		{
			MIN = A[ DEQ.front() ];
			right = i;
		}
	}
	fprintf( fout, "%d %d %d\n", right - K + 2, right + 1, MIN );
	fclose( fin );
	fclose( fout );
	return 0;
}