Cod sursa(job #316931)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 21 mai 2009 17:02:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <deque>
#define N 8192
using namespace std;
char b[N];
int bi;
deque<pair<int,int> > d;
int k,n;

int citeste()
{int nr=0,semn=0;
 while(!isdigit(b[bi])&&b[bi]!='-')
 {bi++;
  if(b[bi]==NULL)
  {fgets(b,N,stdin);
   bi=0;
  }
 }
 if(b[bi]=='-')
 {semn=1;
  if(b[++bi]==NULL)
  {fgets(b,N,stdin);
   bi=0;
  }
 }
 while(isdigit(b[bi]))
 {nr=nr*10+b[bi]-'0';
  if(b[++bi]==NULL)
  {fgets(b,N,stdin);
   bi=0;
  }
 }
 
 if(semn)return -nr;
 return nr;
}
int main ()
{int i,x,max=-40000,pmax;
 freopen("secventa.in","r",stdin);
 freopen("secventa.out","w",stdout);
 n=citeste();k=citeste();
 for (i=1;i<k;i++)
 {x=citeste();
  while(!d.empty() && x<d.front().first)
  {d.pop_front();
  }
  d.push_front(pair<int,int>(x,i));
 }
 for (;i<=n;i++)
 {x=citeste();
  if(!d.empty()&&i-d.back().second>=k)
  {d.pop_back();
  }
  while(!d.empty()&&x< d.front().first)
  {d.pop_front();
  }
  d.push_front(pair<int,int>(x,i));
  if(max<d.back().first)
  {max=d.back().first;
   pmax=i;
  }
 }
 printf("%d %d %d",pmax-k+1,pmax,max);
 return 0;
}