Cod sursă (job #543035)

#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];

 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()
{
    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;
}