Cod sursa(job #355746)

Utilizator iulia609fara nume iulia609 Data 12 octombrie 2009 00:13:41
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#define dim 500001
using namespace std;

int A[dim], deque[dim], N,K,i,min,in,sf,capat;

void functie()
{
	min = capat = -30001;
	in = sf = 1;
	
	for(i = 1; i <= N; i++)
		{
			while(in <= sf && A[deque[sf]] >= A[i]) sf--;
			deque[++sf] = i;
			if (i - deque[in] == K) in++; 
			
			if (A[deque[in]] > min && i >= K) 
					{
						min = A[deque[in]];
						capat = i;
					}
		}
}

int main()
{ 

	FILE *f = fopen("secventa.in", "r");
	FILE *g = fopen("secventa.out", "w");
	
	fscanf(f, "%d%d", &N, &K);
	
	for(i = 1; i <= N; i++)
		fscanf(f, "%d", &A[i]);

	functie();
	
	fprintf(g, "%d %d %d\n", capat-K+1, capat, min);
	
	fclose(f);
	fclose(g);
	return 0;
}