Cod sursa(job #23279)

Utilizator pocaituDavid si Goliat pocaitu Data 28 februarie 2007 16:08:49
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream.h>
#define infi 1000000
int long pos[500000],st[500000],sf,inc,d,max,i,n,k,x,j;
int main()
{ifstream f("secventa.in");
 f>>n>>k;
 f>>st[1];
 st[0]=-infi;
 inc=sf=1;
 pos[sf]=1;
 for(i=2;i<=k;i++)
   {f>>x;
   for(j=sf;st[j]>=x;j--);
	st[j+1]=x;
	sf=j+1;
   pos[sf]=i;
   }
 max=st[1];
 for(i=k+1;i<=n;i++)
  {f>>x;
   if(pos[inc]==i-k)
	 st[inc++]=-infi;
   for(j=sf;st[j]>=x;j--);
   st[j+1]=x;
   sf=j+1;
   pos[sf]=i;
   if(st[inc]>max)
	 {max=st[inc];
	  d=i;
	  }
   }

 ofstream g("secventa.out");
 g<<d-k+1<<" "<<d<<" "<<max;
 g.close();
 return 0;
 }