SRM459 div1 medium

一番下の列を決めたら全部決まる。
一番下の列の要素は{1,5,10,10,5,1}倍された和がtopに等しくなる。
これは二項係数。
じゃあナップサックできるじゃん。
ここでオーダーを下げきれずにTLE。
どの要素も正なのでbaseLengthがある程度大きくなったら弾いちゃってOK。

#include <vector>

typedef long long LL;
using namespace std;

LL DP[1000000+10][2];

class NumberPyramids 
{
	public:
		int count(int baseLength, int top) 
		{
			int C[21][21];
			int bottom[20];

			if(20<baseLength)
				return 0;

			for(int i=0;i<21;i++)
				for(int j=0;j<21;j++)
					C[i][j]=(i==0 || j==0)?1:C[i-1][j]+C[i][j-1];
			for(int i=0;i<baseLength;i++)
				bottom[i]=C[baseLength-1-i][i],top-=bottom[i]

			if(top<0)
				return 0;

			for(int i=baseLength;0<=i;i--)
				for(int j=0;j<=top;j++)
					if(i==baseLength)
						DP[j][i%2]=(j==0)?1:0;
					else
					{
						DP[j][i%2]=DP[j][(i+1)%2];
						if(0<=j-bottom[i])
							DP[j][i%2]=(DP[j][i%2]+DP[j-bottom[i]][i%2])%1000000009;
					}

			return DP[top][0];
		}
};