CFR 295 1C. Greg and Friends ( DP + Restoration )

Problem - C - Codeforces
dp[ i ][ j ][ k ] :
boat is on the original side, j people 50 pounds are on the goal, k people 100 pounds are on the goal
Then we will be able to perform PFS to find the shortest path, but since all the weights for transportation is equivalent, which is 1, we can use BFS instead that is faster as well. After finding the shortest path from the beginning state to all other states, now we can do some DP restoration, which I used memoization to implement. Note that the number of ways to transfer from some state to the current state will be
ways to choose 50 pounds people * ways to choose 100 pounds people * ways of the previous state
which we will precompute C() function. It is a 2D / 2D DP, so the overall time complexity is O( n ^ 4 ).
Be careful that there will be 3 very large numbers multiplying each others, so it will be necessary to perform mod twice.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 5;
const int MAXK = 5e3 + 3;
const int MOD = 1e9 + 7;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int n, k;
int wei[ MAXN ];
int fcnt, hcnt;

struct State{
    int boat, fifty, hundr;
    State( int _b = -1, int _f = -1, int _h = -1 ):
        boat( _b ), fifty( _f ), hundr( _h ){}
};

int dis[ 2 ][ MAXN ][ MAXN ];
int C[ MAXN ][ MAXN ];

void precompute_C(){
    C[ 0 ][ 0 ] = 1;
    for( int i = 0; i < MAXN - 1; ++i )
        for( int j = 0; j < MAXN - 1; ++j )
            ( C[ i + 1 ][ j ] += C[ i ][ j ] ) %= MOD,
            ( C[ i + 1 ][ j + 1 ] += C[ i ][ j ] ) %= MOD;
}

int dp_way[ 2 ][ MAXN ][ MAXN ];
int backtrackWays( int b, int f, int h ){
    if( b + f + h == 0 ) return 1;
    if( ~dp_way[ b ][ f ][ h ] ) return dp_way[ b ][ f ][ h ];
    ll res = 0;
    if( b == 0 ){
        for( int i = 0; i <= fcnt - f; ++i )
            for( int j = 0; j <= hcnt - h; ++j ) if( i + j > 0 && i * 50 + j * 100 <= k )
                if( dis[ 1 ][ f + i ][ h + j ] == dis[ 0 ][ f ][ h ] - 1 )
                    res += (ll)backtrackWays( 1, f + i, h + j ) * ( (ll)C[ fcnt - f ][ i ] * C[ hcnt - h ][ j ] % MOD ),
                    res %= MOD;

    } else{
        for( int i = 0; i <= f; ++i )
            for( int j = 0; j <= h; ++j ) if( i + j > 0 && i * 50 + j * 100 <= k )
                if( dis[ 0 ][ f - i ][ h - j ] == dis[ 1 ][ f ][ h ] - 1 )
                    res += (ll)backtrackWays( 0, f - i, h - j ) * ( (ll)C[ f ][ i ] * C[ h ][ j ] % MOD ),
                    res %= MOD;
    }
    return dp_way[ b ][ f ][ h ] = res;
}

void solve(){
    memset( dis, INF, sizeof(dis) );
    queue< State > que;
    que.push( State( 0, 0, 0 ) );
    dis[ 0 ][ 0 ][ 0 ] = 0;
    while( !que.empty() ){
        int b = que.front().boat;
        int f = que.front().fifty;
        int h = que.front().hundr;
        que.pop();
        if( b == 0 ){
            for( int i = 0; i <= fcnt - f; ++i )
                for( int j = 0; j <= hcnt - h; ++j ) if( i + j > 0 && i * 50 + j * 100 <= k )
                    if( dis[ 1 ][ f + i ][ h + j ] > dis[ 0 ][ f ][ h ] + 1 )
                        dis[ 1 ][ f + i ][ h + j ] = dis[ 0 ][ f ][ h ] + 1,
                        que.push( State( 1, f + i, h + j ) );
        } else{
            for( int i = 0; i <= f; ++i )
                for( int j = 0; j <= h; ++j ) if( i + j > 0 && i * 50 + j * 100 <= k )
                    if( dis[ 0 ][ f - i ][ h - j ] > dis[ 1 ][ f ][ h ] + 1 )
                        dis[ 0 ][ f - i ][ h - j ] = dis[ 1 ][ f ][ h ] + 1,
                        que.push( State( 0, f - i, h - j ) );
        }
    }
    if( dis[ 1 ][ fcnt ][ hcnt ] == INF ) cout << "-1\n0\n";
    else{
        cout << dis[ 1 ][ fcnt ][ hcnt ] << "\n";
        precompute_C();
        memset( dp_way, -1, sizeof(dp_way) );
        cout << backtrackWays( 1, fcnt, hcnt ) << "\n";
    }
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> k;
    for( int i = 0; i < n; ++i )
        cin >> wei[ i ];
    for( int i = 0; i < n; ++i ){
        if( wei[ i ] == 50 ) ++fcnt;
        else ++hcnt;
    }
    solve();
    return 0;
}