Cod sursa(job #372615)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 10 decembrie 2009 22:40:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <string.h>

#define Nmax 500010

int V[Nmax], D[Nmax];
int minp, minu, p, u, i, n, k, max = -Nmax, semn;
char s[Nmax * 7];

int main (){
	
	FILE * f = fopen ("secventa.in", "r");
	FILE * g = fopen ("secventa.out", "w");
	
	fscanf (f, "%d %d\n", &n, &k);
	
	//fscanf (f, "%s", s);
	fgets (s, sizeof(s), f);
	
	int N = strlen (s);
	semn = 1; n = 0;
	for (i = 0; i < N; i++) {
		if (s[i] == '-') semn = -1;
		if (s[i] >= '0' && s[i] <= '9') {
			n++;
			while (s[i] >= '0' && s[i] <= '9' && i < N) {
				V[n] = V[n] * 10 + s[i] - '0';
				i++;
			}
			
			V[n]*= semn;
			semn = 1;
		}
	}
	
	p = 1;
	u = 0;
	for (i = 1 ; i <= n ; i++){
		while ( p <= u && V[i]<=V[D[u]])
			u--;
		
		D[++u] = i;
		
		if (D[p] == i-k) p++;
		
		if (i>=k) 
			if (max < V[D[p]]) {
				max = V[D[p]];
				minp = i-k+1;
				minu = i;
			}
		
	}
	
	fprintf (g, "%d %d %d", minp, minu, max);
	
	fclose(f);
	fclose(g);
	
	return 0;
}