Cod sursă (job #543062)

#include <fstream>
using namespace std;
ifstream in("sam.in");
ofstream out("sam.out");
int n,a[100001],x[100001],b[2][100001],r,k;
bool s,t;
int main()
{ in>>n;
  for(int i=1;i<=n;i++)
    in>>a[i];
  if(a[1]<a[2])
     a[0]=n+1;
  else
     a[0]=0;
  if(a[n-1]<a[n])
     a[n+1]=-1;
  else
     a[n+1]=n+2;
  x[0]=0;
  x[1]=1;
  k=1;
  if(a[0]<a[1])
     s=1;
  for(int i=2;i<=n+1;i++)
  { t=0;
    if(a[i-1]<a[i])
       t=1;
    if(s==t)
    { k++;
      x[k]=i-1;
      s=1-s;
    }
  }
  k++;
  x[k]=n+1;
  s=0;
  if(a[0]<a[1])
     s=1;
  for(int i=x[0]+1;i<=x[2]-1;i++)
    b[s][i]=1;
  for(int p=1;p<=k-2;p++)
  { s=1-s;
    for(int i=x[p]+1;i<=x[p+2]-1;i++)
    { for(int j=x[p-1];j<=x[p+1]-1 && j<=i-1;j++)
      { t=0;
        if(a[j]<a[i])
           t=1;
        if(s==t)
           b[s][i]+=b[1-s][j];
      }
    }
  }
  r=0;
  for(int i=x[k-2]+1;i<=x[k]-1;i++)
    r+=b[s][i],r%=1000003;
  out<<r;
  in.close();
  out.close();
  return 0;
}