Cod sursa(job #150777)

Utilizator rethosPaicu Alexandru rethos Data 7 martie 2008 13:29:04
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <fstream.h>
#define NM 501
#define INF 0x7fff
int a[NM],ind[NM],vf,baza;
void popvf()
{ vf--;
}
void popbaza()
{ baza++;
}
void push(int x,int k)
{ a[++vf]=x;
  ind[vf]=k;
}
int main()
{ long n,k;
  FILE *f=fopen("secventa.in","rt");
  fscanf(f,"%ld %ld",&n,&k);
  int max=-INF,kmax=1;
  int x,i,sw;
  char c;
  fscanf(f,"%c",&c);
  fflush(f);
  vf=0;baza=1;
  for (i=1;i<k;i++)
	{ x=0;sw=1;
	  fscanf(f,"%c",&c);
	  while ((c<='9'&&c>='0'||c=='-')&&!feof(f))
		{ if (c=='-') sw=-1;
		  else x=x*10+c-'0';
		  fscanf(f,"%c",&c);
		}
	  x=x*sw;
	  while (a[vf]>x&&vf>=baza) popvf();
	  push(x,i);
	}
  for (i=k;i<=n;i++)
	{ x=0;sw=1;
	  fscanf(f,"%c",&c);
	  while ((c<='9'&&c>='0'||c=='-')&&!feof(f))
		{ if (c=='-') sw=-1;
		  else x=x*10+c-'0';
		  fscanf(f,"%c",&c);
		}
	  x=x*sw;
	  if (i-ind[baza]>=k) popbaza();
	  while (a[vf]>x&&vf>=baza) popvf();
	  push(x,i);
	  if (a[baza]>max)
		{ max=a[baza];
		  kmax=i-k+1;
		}
	}
  fclose(f);
  ofstream g("secventa.out");
  g<<kmax<<' '<<kmax+k-1<<' '<<max;
  g.close();
  return 0;
}