CFR 580 D. Kefa and Dishes ( bit DP )

Problem - D - Codeforces
I thought this resembled quite a lot with this problem.
What we really have to do is to perform dynamic programming on:
dp[ S ][ i ] : the value of having each element in set S eaten and i'th as the last

int bit_count( int x ){
    return x ? bit_count( x >> 1 ) + ( x & 1 ) : 0;
}

void solve(){
    int N, M, K; cin >> N >> M >> K;
    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    map< pii, int > rule;
    for( int i = 0; i < K; ++i ){
        int x, y, c; cin >> x >> y >> c;
        --x, --y;
        rule[ pii( x, y ) ] = c;
    }
    vvl dp( 1 << N, vl( N, -( 1LL << 60 ) ) );
    for( int i = 0; i < N; ++i )
        dp[ 1 << i ][ i ] = A[ i ];
    for( int i = 1; i < 1 << N; ++i )
        for( int j = 0; j < N; ++j ) if( i >> j & 1 )
            for( int k = 0; k < N; ++k ) if( not ( i >> k & 1 ) ){
                ll nv = dp[ i ][ j ] + A[ k ];
                if( rule.count( pii( j, k ) ) ) nv += rule[ pii( j, k ) ];
                upmax( dp[ i | 1 << k ][ k ], nv );
            }
    ll ans = 0;
    for( int i = 1; i < 1 << N; ++i )
        for( int j = 0; j < N; ++j ) if( i >> j & 1 )
            if( bit_count( i ) == M )
                upmax( ans, dp[ i ][ j ] );
    cout << ans << endl;
}