Cod sursă (job #547254)

#include <fstream>

#include <fstream>
using namespace std;

ifstream fin("sam.in");
ofstream fout("sam.out");
int n, i, j, k, p, a[100009], x[100009], dir, v;
int b[2][100009];

int main() {
  fin >> n;
  for (i = 1; i <= n; i++) {
    fin >> 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] = -1;
  x[1] = 0;
  p = 1;
  for (i = 1; i <= n; i++) {
    if ((a[i - 1] < a[i] && a[i] > a[i + 1]) ||
        (a[i - 1] > a[i] && a[i] < a[i + 1])) {
      p++;
      x[p] = i;
    }
  }
  x[p + 1] = n + 1;
  x[p + 2] = n + 2;

  if (a[1] < a[2])
    dir = 0;
  else
    dir = 1;

  b[dir][0] = 1;
  for (k = 1; k <= p; k++) {
    dir = 1 - dir;
    for (i = 1 + x[k - 1]; i < x[k + 1]; i++) {
      v = (x[k] > i) ? x[k] : i;
      for (j = 1 + v; j < x[k + 2]; j++) {
        if ((a[j] > a[i] && dir == 0) || (a[j] < a[i] && dir == 1)) {
          b[dir][j] = (b[dir][j] + b[1 - dir][i]) % 1000003;
        }
      }
    }
  }
  fout << b[dir][n + 1] << "\n";

  return 0;
}