Submission #1217263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217263		amaninnight	Bank (IZhO14_bank)	C++20	19 / 100	12 ms	18760 KiB

bank

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

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29