UVA 12105 - Bigger is Better ( DP )

UVa Online Judge
maxl[ i ][ j ] = maximal number of digits of a possible number x, where x is constructible with not more than i sticks and remains j for % M
maxd[ i ][ j ] = having maxl[ i ][ j ], the maximal digit that could be used
maxl[ i ][ j ] =
max( 0, max{ 1 + maxl[ i - cost[ d ] ][ ( j * 10 + d ) % M ] | for all i ≥ cost[ d ] } ), if j == 0
max( -1, max{ 1 + maxl[ i - cost[ d ] ][ ( j * 10 + d ) % M ] | for all i ≥ cost[ d ] and maxl[ i - cost[ d ] ][ ( j * 10 + d ) % M ] != -1 } ), otherwise

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

const int MAXN = 100 + 2;
const int MAXM = 3e3 + 3;
const int c[ 10 ] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

int kase;

int N, M;
int maxl[ MAXN ][ MAXM ];
int maxd[ MAXN ][ MAXM ];
int vis[ MAXN ][ MAXM ];

bool upmax( int &x, int v ){
    if( x < v ) return ( x = v ) or true;
    return false;
}

void dfs( int n, int rem ){
    if( vis[ n ][ rem ] == kase ) return;
    vis[ n ][ rem ] = kase;
    if( rem == 0 ) maxl[ n ][ rem ] = 0;
    else maxl[ n ][ rem ] = -1;
    for( int i = 9; i >= 0; --i )
        if( n >= c[ i ] ){
            int nn = n - c[ i ], nr = ( rem * 10 + i ) % M;
            dfs( nn, nr );
            if( maxl[ nn ][ nr ] == -1 ) continue;
            if( upmax( maxl[ n ][ rem ], maxl[ nn ][ nr ] + 1 ) )
                maxd[ n ][ rem ] = i;
        }
}

bool solve(){
    cin >> N; if( N == 0 ) return false;
    cin >> M;

    cout << "Case " << ++kase << ": ";

    dfs( N, 0 );

    if( maxl[ N ][ 0 ] == 0 ){
        cout << -1 << "\n";
        return true;
    }

    for( int n = N, r = 0; maxd[ n ][ r ] != -1 and n >= c[ maxd[ n ][ r ] ]; ){
        int d = maxd[ n ][ r ];
        cout << d;
        n -= c[ d ];
        r = ( r * 10 + d ) % M;
    }
    cout << "\n";

    return true;
}

int main(){
    ios::sync_with_stdio( false );
    while( solve() );
    return 0;
}