Artifact 55b5f1c30cb956ae0ebe0bd6bcc403c0570002f3
#include <vector>
using namespace std;
struct HillHike
{
long long numPaths(int distance, int maxHeight, vector<int> landmarks)
{
// reached-maxHeight?, #reached-landmarks, current-height
long long buf1[2][51][51]={0}, buf2[2][51][51], (*dp)[51][51]=buf1;
dp[0][0][0] = 1;
for(int d=1; d<=distance; ++d)
{
long long (*dp2)[51][51] = (dp==buf1 ? buf2 : buf1);
memset(dp2, 0, sizeof(long long)*2*51*51);
for(int rm=0; rm<=1; ++rm)
for(int rl=0; rl<=landmarks.size(); ++rl)
for(int ch=0; ch<=maxHeight; ++ch)
{
if(ch>1 || d==distance && ch>0)
{
dp2[rm]
[rl<landmarks.size() && landmarks[rl]==ch-1 ? rl+1 : rl]
[ch-1] += dp[rm][rl][ch];
}
if(ch>0 || d==distance)
{
dp2[rm]
[rl<landmarks.size() && landmarks[rl]==ch ? rl+1 : rl]
[ch] += dp[rm][rl][ch];
}
if( ch<maxHeight )
{
dp2[ch+1==maxHeight ? 1 : rm]
[rl<landmarks.size() && landmarks[rl]==ch+1 ? rl+1 : rl]
[ch+1] += dp[rm][rl][ch];
}
}
dp = dp2;
}
return dp[1][landmarks.size()][0];
}
};