Cod sursa(job #167035)

Utilizator pandaemonAndrei Popescu pandaemon Data 28 martie 2008 21:17:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<fstream.h>
#include<iostream.h>
#include<stdlib.h>

#define NMAX 500001

fstream fin("secventa.in",ios::in),fout("secventa.out",ios::out);

long n,k,v[NMAX],m[NMAX],i=0; char s[10];

main()
{
  fin>>n>>k; fin.get();

  while( fin.get(s,6,' ') )  { fin.get(); v[++i]=atof(s); }

  long beg=1,end=0,max=-66666,poz=0;

  for(i=1;i<=n;i++)
    {
      if(beg<=end && m[beg]<=i-k) beg++;

      while(beg<=end && v[ m[end] ] > v[i] ) end--;

      m[++end]=i;

      if(i>=k && v[ m[beg] ] > max ) {poz=i; max = v[ m[beg] ];}

    }

    fout<<poz-k+1<<" "<<poz<<" "<<max;

    fout<<endl;  return 0;

}