Submission #36163891

---

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()));

    //シャッフルのリストを作る
    vector<int> S[10000];
    for(int i=0;i<10000;i++){
        
        vector<int> s;
        int k = i;
        while(k>0){
            s.push_back(k%10);
            k/=10;
        }

        sort(s.begin(),s.end());
        do{
            int y=0;
            for(int j=0;j<(int)s.size();j++){
                y *= 10;
                y += s[j];
            }
            S[i].push_back(y);
        }while(next_permutation(s.begin(),s.end()));
    }

    //遷移
    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++){
            for(int k=0;k<(int)S[j].size();k++){
                dp[i+1][S[j][k]] = max(dp[i+1][S[j][k]],dp[i+1][j]);
            }
        }
    }

    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