WA #3 #10

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6e5 + 100, L = 50;

string str;
int n, st[L][L], ans = 40, l;
int f[L][N];

int main ()
{
    cin >> str >> n;

    if (n == 0) {cout << 1 << endl; return 0;}

    l = str.length();
    for (int i = l; i >= 1; i -- ) str[i] = str[i - 1];

    for (int len = 1; len <= 6; len ++ )
        for (int i = 1; i <= l - len + 1; i ++ )
        {
            int num = 0;
            for (int j = 1; j <= len; j ++ )
                num = num * 10 + str[i + j - 1] - '0';
            st[i][i + len - 1] = num;
        }

    memset (f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= l; i ++ )
        for (int k = 0; k <= i - 1; k ++ )
            for (int j = st[k + 1][i]; j <= n; j ++ )
                    f[i][j] = min(f[k][j - st[k + 1][i]] + 1, f[i][j]);

    if (f[l][n] == 0x3f3f3f3f) cout << -1 << endl;
    else cout << f[l][n] - 1 << endl;

    return 0;
}