Cod sursa(job #31253)

Utilizator CezarMocanCezar Mocan CezarMocan Data 15 martie 2007 18:33:59
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream.h>
#include <iomanip.h>

fstream f("secventa.in",ios::in);
fstream g("secventa.out",ios::out);

long n,k,i,j,start,stop,max,min,posmax,v[501000],ct[60000];

int main(){
  f>>n>>k;
  for (i=1;i<=n;i++) f>>v[i];
/*
  - determin minimul pe prima secventa de lungime k
  - apoi ma deplasez cat timp am elemente mai mici decat minimul
  - atunci cand gasesc un element mai mare,determin baza pe secventa
  de la el pana la el+k-1 (si pozitia ei)
  - daca gasesc o baza mai buna actualizez maximul si pozitia secventei
  - daca nu gasesc o baza mai buna, continuu de dupa minimul gasit.
  */
  posmax=1;start=1;stop=k;
  for(i=2;i<=k;i++){
   posmax=(v[i]<v[posmax])*i;
   ct[v[i]]++;
  i=k;max=v[posmax];
  }
  while (i<n-k+1){
   ct[i-k+1+30000]--;
   if (!(ct[posmax+30000])){
    posmax=i+1;
    for(j=i+1;j<=k;j++)posmax=(v[j]<v[posmax])*j; 
    if (v[posmax]>max){start=i+1;stop=i+k;max=v[posmax];}      
   } 
  //g<<max<<" "<<i<<endl;
   i++;ct[v[i]]++;
  }           
  g<<max<<" "<<start<<" "<<stop;
  f.close();g.close();
return 0;
}