Cod sursa(job #277106)

Utilizator robbyRobertino robert robby Data 11 martie 2009 15:11:23
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#define nmax 500005
int a[nmax],c[nmax];
int in,sf,bz;
char s[nmax*2+2];

FILE *f,*g;
int main()
{
	long n,k,i,st,semn,j;
	f=fopen("secventa.in","rt");
	g=fopen("secventa.out","wt");
	fscanf(f,"%ld %ld\n",&n,&k);
	for (i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	fgets(s,nmax*2+2,f);
	i=0;
	semn=1;
	j=0;
	while (s[i])
		{
			if (s[i]=='-')
				semn=-1;
			 else
			if (s[i]>='0'&&s[i]<='9')
				{a[++j]=(s[i]-'0')*semn;semn=1;}
			i++;
		}
	bz=-30009;
  in=1;sf=0;
	for (i=1;i<=n;i++)
	{
	  while (a[c[sf]]>a[i]&&sf>=in)sf--;
		c[++sf]=i;
	  while (c[in]<i-k+1) in++;

		if ( a[c[in]]> bz  && i-k+1 > 0)
		{
			bz = a[c[in]];
			st = i-k;
		}
	}
  fprintf(g, "%ld %ld %d\n", st+1, st+k, bz);
  fcloseall();
  return 0;
}