Submission #36163889

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 998244353ll;
const long long INF = 2305843009213693951ll;

int main(void){
    
    int N,X;
    cin >> N >> X;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }

    //dp[i][j] = i番目まで行って所持金がjであるときの買える商品の最大値
    int dp[101][10000];
    for(int i=0;i<101;i++){
        for(int j=0;j<10000;j++){
            dp[i][j] = INT_MIN;
        }
    }

    //Xとその並び替えは最初から使える
    int x = X;
    vector<int> Y;
    while(x>0){
        Y.push_back(x%10);
        x/=10;
    }
    sort(Y.begin(),Y.end());
    do{
        int y = 0;
        for(int j=0;j<(int)Y.size();j++){
            y *= 10;
            y += Y[j];
        }
        dp[0][y] = 0;
    }while(next_permutation(Y.begin(),Y.end()));

    //最も大きくなるように並べ替えたときのもの
    ll S[10000];
    for(int i=0;i<10000;i++){
        vector<int> R;
        int k = i;
        while(k>0){
            R.push_back(k%10);
            k /= 10;
        }
        sort(R.begin(),R.end(),greater<>());
        
        int r = 0;
        for(int j=0;j<(int)R.size();j++){
            r *= 10;
            r += R[j];
        }
        S[i] = r;
    }

    //遷移
    for(int i=0;i<N;i++){

        for(int j=0;j<10000;j++){
            //買う
            if(j>=A[i]){
                dp[i+1][j-A[i]] = max(dp[i+1][j-A[i]],dp[i][j]+1);
            }
            //買わない
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }

        //魔法を使って遷移元を集めてくる
        for(int j=0;j<10000;j++){
            dp[i+1][S[j]] = max(dp[i+1][S[j]],dp[i+1][j]);
        }
        for(int j=0;j<10000;j++){
            int k = S[j];
            while(k!=0 && k<10000){
                dp[i+1][j] = max(dp[i+1][j],dp[i+1][k]);
                k *= 10;
            }
        }
    }

    int Ans = 0;
    for(int j=0;j<10000;j++){
        Ans = max(Ans,dp[N][j]);
    }

    cout << Ans << endl;

    return 0;
}

Submission Info

Judge Result