Cod sursă (job #543031)

#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];
 void SOLVE (int i, int j)
 {  int q,viz[10],k1,ma[10][10];
 	if (!q && !viz[i]) 
	{
		fout << i << " "; 
		k1++;
	}
 	q = 1; 
	viz[i] = true;
    if (!viz[j])
	fout << j << " ";
    viz[j] = true; 
    ma[i][j] = 0; 
	ma[j][i] = 0;

    for (int h = 1; h <= n; h++)
	{
        if (ma[j][h]) 
		    SOLVE(j, h);
    }
}
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;
}