Cod sursa(job #333162)

Utilizator dodgerblueBogdan P. dodgerblue Data 21 iulie 2009 16:43:59
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

int main()
{
	FILE *f,*g;
	int n,k,i,*a;
	int start,end,*Q,poz=0,max=-9999999;
	char *s,*p;
	
	f=fopen("secventa.in","r");
	g=fopen("secventa.out","w");
	
	fscanf(f,"%d %d\n",&n,&k);
	a=(int*)malloc((n+1)*sizeof(int));
	Q=(int*)malloc((n+1)*sizeof(int));
	s=(char*)malloc(7*n*sizeof(char));
	
	fscanf(s,7*n,f);
	i=1;
	p=strtok(s," ");
	while(p)
	{
		a[i++]=atoi(p);
		p=strtok(NULL," ");
	}
	
	start=1;
	end=0;
	
	for(i=1;i<=n;i++)
	{
		if(start<=end && Q[start]<=i-k) start++;
		while(start<=end && a[Q[end]]>a[i]) end--;
		Q[++end]=i;
		if(a[Q[start]]>max && i>=k)
		{
			max=a[Q[start]];
			poz=i;
		}
	}
	
	fprintf(g,"%d %d %d\n",poz-k+1,poz,max);
	
	fclose(f);
	fclose(g);
	return 0;
}