Cod sursa(job #334460)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 26 iulie 2009 20:40:47
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main()
{
	int coada[500001],i,n,k,x[500000],tail,head,max=-30001,pozmax=0,j=0,sign;
	char s[3500000];  
	FILE *f=fopen("secventa.in","r");


	fscanf(f,"%i %i\n",&n,&k);
	fgets(s,3500000,f);
	memset(x,0,500000*sizeof(int));
	for(i=0;i<n;i++) 
	{  
		if(s[j]!='-') 
			sign=1;       
		else 
		{ 
			sign=-1; 
			j++; 
		}  
		while((s[j]>='0')&&(s[j]<='9')) 
		{ 
			x[i]=x[i]*10+s[j]-'0'; 
			j++; 
		}  
		j++;  
		x[i]*=sign;  
   }  
	fclose(f);

	tail=1;
	head=0;
	
	for(i=0;i<n;i++)
	{
		while(tail<=head && x[i]<=x[coada[head]])
			head--;
		coada[++head]=i;

		if(i-k==coada[tail])
			tail++;
		if(i+1>=k)
		{
			if(x[coada[tail]]>max)
			{
				max=x[coada[tail]];
				pozmax=i;
			}
		}
	}
	f=fopen("secventa.out","w");
	fprintf(f,"%i %i %i\n",pozmax+2-k,pozmax+1,max);
	fclose(f);
	return 0;
}