Cod sursa(job #277133)

Utilizator robbyRobertino robert robby Data 11 martie 2009 15:22:10
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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);
	fgets(s,nmax*8+2,f);
	i=0;
	semn=1;
	j=0;
	while (s[i])
		{
			if (s[i]=='-')
				semn=-1;
			 else
			if (s[i]>='0'&&s[i]<='9')
			{j++;
			while (s[i]>='0'&&s[i]<='9')
				{a[j]=a[j]*10+(s[i]-'0');i++;}
			a[j]*=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;
}