I am trying to solve http://www.spoj.com/problems/AIRLINES/ using DP , for which i wrote a solution using 3-D dp, but its too slow , if anyone could suggest me improvements and appropriate logic it would be very helpful , here is the ideone link http://ideone.com/QKspPN

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll m , n ,  k ;
int dp[32800][51][51];

ll rec(int vtx , vector<vector<int> > &g,ll sum ,ll idx,vector<int>&ct)
 {
   ll tp = 0;

      if(sum > k || idx > n)
        return 0 ;

     if( idx == n && sum == k )
          tp = 1 ;

      if(dp[vtx][sum][idx]!=-1)
         return dp[vtx][sum][idx];

     for( size_t i = 0 ; i<g[vtx].size() ; i ++ )
        {
             int vt = g[vtx][i] ;
             tp += rec( vt , g , sum + ct[ vt ] , idx + 1 ,ct);
        }

     dp[vtx][sum][idx]  = tp;
          return tp;
 }

int main()

{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin>>m>>n>>k;

  vector<int>vst; // To store valid states
  vector<vector<int> > g(32800); // to store paths form one valid state to another
  vector<int>ct(32800); // to store number of 1s in ach valid state  

  //vector<int>idx(32800);

// finding the valid states 
  for( int i =  0 ; i < exp(2,m) ; i ++ )
    for( int j = 1; j <32 ; j ++ )
      {
           if( (1<<j)&i  && (1<<(j-1))&i )
               break;

           if(j==31)
             vst.push_back(i);
      }


// finding the paths 
   for( size_t i =0 ; i < vst.size() ; i ++ )
     for( size_t j = 0 ; j <  vst.size() ; j ++ )
         for( size_t  k = 0 ; k < 32 ; k ++  )
              {
                if( 1<<k & vst[i]  &&  1<<k & vst[j])
                       break;

                  if(k==31)g[vst[i]].push_back(vst[j]);
               }


// finding the number of 1s in  a valid state 

       for( size_t i = 0 ; i < vst.size() ; i++ )
            { int tp = 0 ;
               for( int j = 0 ; j < 32 ; j++ )
                   if(1<<j & vst[i])
                       tp++;

               ct[vst[i]] = tp ;
            }


       ll sum = 0 ;

      memset(dp,-1,sizeof(dp));
       for( size_t i = 0 ; i < vst.size() ; i ++ )
           sum+= rec(vst[i],g, ct[vst[i]] ,1,ct);

      cout<< sum<<endl;
}