Cod sursă (job #547248)

#include <fstream>

#include <fstream>

#include <iomanip>

using namespace std;

ifstream fin("sam.in");
ofstream fout("sam.out");
int n, a[100010], x[100010], nr;
struct uc {
  int v[2];
};
uc b[100010];
int main() {
  int i, s, t, j, k, p;
  // 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] = 0;
  x[1] = 1;
  k = 1;
  s = 0;
  if (a[0] < a[1])
    s = 1;
  for (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 (i = x[0] + 1; i <= x[2] - 1; i++) {
    b[i].v[s] = 1;
  }
  for (p = 1; p <= k - 2; p++) {
    s = 1 - s;
    for (i = x[p] + 1; i <= x[p + 2] - 1; i++) {
      for (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[i].v[s] += b[j].v[1 - s];
          b[i].v[s] = b[i].v[s] % 1000003;
        }
      }
    }
  }
  nr = 0;
  for (i = x[k - 2] + 1; i <= x[k] - 1; i++) {
    nr += b[i].v[s];
    nr = nr % 1000003;
  }
  fout << nr << "\n";

  return 0;
}