Cod sursa(job #34512)

Utilizator robbyRobertino robert robby Data 20 martie 2007 20:45:54
Problema Secventa Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#define nmax 500001
int a[nmax],b[800];
FILE *f,*g;
int main()
{
  long n,k,i,j,min,l,max,imax,nr,x,y,z,w,p;
  f=fopen("secventa.in","rt");
  g=fopen("secventa.out","wt");
  fscanf(f,"%ld %ld\n",&n,&k);
  l=0;
  while (l*l<=n)
    l++;
  l--;
  min=30001;
  nr=0;
  for (i=1;i<=n;i++)
    {
      fscanf(f,"%d",&a[i]);
      if (a[i]<min)
	min=a[i];
      if (i%l==0)
	{
	  b[++nr]=min;
	  min=30001;
	}
    }
  b[++nr]=min;
  max=-30001;
  imax=0;
  p=n-k+1;
  for (i=1;i<=p;i++)
    {
      j=i;
      min=30001;
      w=i+k-1;
      while (j<=w)
	{
	  if ((j%l==1)&&(j+l-1<=k))
	    {
	      if (b[j/l+1]<min)
		min=b[j/l+1];
	      j+=l;
	    }
	   else
	  if (j%l!=1)
	    {
	      if (j%l!=0)
		z=(j/l)*l+l;
	       else
		z=((j-1)/l)*l+l;
	      for (y=j;y<=z;y++)
		if (a[y]<min)
		  min=a[y];
	      j=z+1;
	    }
	   else
	    {
	      x=i+k-1;
	      for (y=j;y<=x;y++)
		if (a[y]<min)
		  min=a[y];
	      j=x+1;
	    }

	}
      if (min>max)
	{
	  max=min;
	  imax=i;
	}
    }
  fprintf(g,"%ld %ld %ld\n",imax,imax+k-1,max);
  fcloseall();
  return 0;
}