Submission #1217263

#TimeUsernameProblemLanguageResultExecution timeMemory
1217263amaninnightBank (IZhO14_bank)C++20
19 / 100
12 ms18760 KiB
        #include<bits/stdc++.h>
        #define pb push_back
        #define all(x) x.begin(),x.end()
        #define F first
        #define S second 
        
        using namespace std;
        typedef long long ll;
        typedef pair<int, int> pii;
        typedef pair<ll, int> pli;
        typedef pair<ll, ll> pll;
        typedef vector<int> VI;
        typedef vector<ll> VLL;

        const int maxn = 21;

        int a[maxn], b[maxn];
        int money[1<<maxn], dp[maxn][1<<maxn];
        VI bag[1000 * maxn];

        void MAIN(){
            int n, m;   cin >> n >> m;
            for(int i = 1; i <= n; i++) cin >> a[i];
            for(int i = 0; i < m; i++)  cin >> b[i];
            for(int mask = 1; mask < (1<<m); mask++){
                money[mask] = money[mask - (1<<(__builtin_ctz(mask)))] + b[__builtin_ctz(mask)];
                bag[money[mask]].pb(mask);
            }
            for(int mask = 0; mask < (1<<m); mask++)    dp[0][mask] = 1;
            for(int i = 1; i <= n; i++){
                for(int mask = 1; mask < (1<<m); mask++){
                    if(money[mask] == a[i]){
                        dp[i][mask] = dp[i-1][0];
                        int nmask = mask;
                        for(int ptr = 0; ptr < m; ptr++){
                            if((mask & (1<<ptr)) == 0)  nmask += (1<<ptr);
                            dp[i][nmask] |= dp[i-1][nmask - mask];
                        }
                    }
                }
            }
            if(dp[n][(1<<m)-1]) cout << "YES" << endl;
            else    cout << "NO" << endl;
        }

        int main(){
            cin.tie(0) -> sync_with_stdio(0), cout.tie(0);   
            
            int _ = 1;
            //cin >> _;
            while(_--)
                MAIN();
        }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...