<p>Given an array of integers <code>cost</code> and an integer <code>target</code>, return <em>the <strong>maximum</strong> integer you can paint under the following rules</em>:</p>

<ul>
	<li>The cost of painting a digit <code>(i + 1)</code> is given by <code>cost[i]</code> (<strong>0-indexed</strong>).</li>
	<li>The total cost used must be equal to <code>target</code>.</li>
	<li>The integer does not have <code>0</code> digits.</li>
</ul>

<p>Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return <code>&quot;0&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cost = [4,3,2,5,6,7,2,5,5], target = 9
<strong>Output:</strong> &quot;7772&quot;
<strong>Explanation:</strong> The cost to paint the digit &#39;7&#39; is 2, and the digit &#39;2&#39; is 3. Then cost(&quot;7772&quot;) = 2*3+ 3*1 = 9. You could also paint &quot;977&quot;, but &quot;7772&quot; is the largest number.
<strong>Digit    cost</strong>
  1  -&gt;   4
  2  -&gt;   3
  3  -&gt;   2
  4  -&gt;   5
  5  -&gt;   6
  6  -&gt;   7
  7  -&gt;   2
  8  -&gt;   5
  9  -&gt;   5
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cost = [7,6,5,5,5,6,8,7,8], target = 12
<strong>Output:</strong> &quot;85&quot;
<strong>Explanation:</strong> The cost to paint the digit &#39;8&#39; is 7, and the digit &#39;5&#39; is 5. Then cost(&quot;85&quot;) = 7 + 5 = 12.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cost = [2,4,6,2,4,6,4,4,4], target = 5
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong> It is impossible to paint any integer with total cost equal to target.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>cost.length == 9</code></li>
	<li><code>1 &lt;= cost[i], target &lt;= 5000</code></li>
</ul>

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast", "inline", "unroll-loops", "no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native", "f16c")
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
static void fast_read()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

class Solution
{
private:
    /*
Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules:

    The cost of painting a digit (i + 1) is given by cost[i] (0-indexed).
    The total cost used must be equal to target.
    The integer does not have 0 digits.

Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return "0".



Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation: The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It is impossible to paint any integer with total cost equal to target.

     */
public:
    const int MOD = 1e9 + 7;
    Solution()
    {
        fast_read();
    }
    unordered_map<int, unordered_map<int, string, custom_hash>, custom_hash> dp;
    string recur(int idx, int target, vector<pair<int, int>> &digitCost)
    {
        if (target == 0)
        {
            return "";
        }
        if (idx == 0)
        {
            if (target % digitCost[idx].second == 0)
            {
                int num = target / digitCost[idx].second;
                return string(num, digitCost[idx].first + '0');
            }
            else
            {
                return "0";
            }
        }

        if (dp.count(idx) && dp[idx].count(target))
        {
            return dp[idx][target];
        }

        string notTake = "" + recur(idx - 1, target, digitCost);
        string take = "";
        if (target >= digitCost[idx].second)
        {
            take = to_string(digitCost[idx].first) + recur(idx, target - digitCost[idx].second, digitCost);
        }
        if (take.empty() || take.back() == '0')
        {
            return dp[idx][target] = notTake;
        }
        else if (notTake.empty() || notTake.back() == '0')
        {
            return dp[idx][target] = take;
        }
        else
        {
            if (take.length() > notTake.length())
            {
                return dp[idx][target] = take;
            }
            else if (take.length() < notTake.length())
            {
                return dp[idx][target] = notTake;
            }
            else
            {
                return dp[idx][target] = max(take, notTake);
            }
        }
    }

    string largestNumber(vector<int> &cost, int target)
    {
        vector<pair<int, int>> digitCost;
        unordered_map<int, int, custom_hash> mp;
        for (int i = 1; i <= cost.size(); i++)
        {
            mp[cost[i - 1]] = i;
        }
        for (auto &[k, v] : mp)
        {
            digitCost.push_back({v, k});
        }
        sort(digitCost.begin(), digitCost.end());
        string ans = recur(digitCost.size() - 1, target, digitCost);
        if (ans.empty() || ans.back() == '0')
        {
            return "0";
        }
        return ans;
    }
};

50296