Cod sursa(job #206895)

Utilizator tamicTamas Iulia tamic Data 10 septembrie 2008 16:18:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#define NMAX 500000

FILE *fin,*fout;
long v[NMAX],a[NMAX];
char s[NMAX*10];
long i,j,n,k,max,semn,msa,start;

void add(long x){
	long i;
	for(i=j; (i>=msa) && (a[i]>x);i--);
   j=i+1;
   a[j]=x;
}

int main(){
	fin=fopen("secventa.in","r");
   fout=fopen("secventa.out","w");
   fscanf(fin,"%ld%ld\n",&n,&k);
   fgets(s,NMAX,fin); j=0;
   for(i=1;i<=n;i++){
      semn=1;
      if(s[j]=='-') semn=-1,j++;
      while((s[j] != '-') && !((s[j] >= '0') && (s[j] <= '9'))) ++j; 
      while((s[j]>='0') && (s[j]<='9')) v[i]=v[i]*10 + s[j]-'0',j++;
      v[i] *= semn;
   }

   msa=1; j=0;
   for(i=1;i<=k;i++) add(v[i]);
   for(i=k+1;i<=n;i++){
   	if(v[i-k]==a[msa]) msa++;
      add(v[i]);
      if(a[msa]>max) max=a[msa],start=i-k+1;
   }

   fprintf(fout,"%ld %ld %ld\n",start,start+k-1,max);
   fclose(fin); fclose(fout);
   return 0;
}