Submission #1132906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132906		DangKhoizzzz	Bank (IZhO14_bank)	C++20	0 / 100	1096 ms	824 KiB

bank

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;

int bit(int x , int b) {return ((x >> b)&1);}
int flip(int x , int b) {return (x ^ (1 << b));}

int n , m , a[40] , b[40];
pii dp[(1 << 21)];

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    a[n+1] = INF;

    dp[0] = {0 , 0};

    for(int mask = 1; mask < (1 << m); mask++)
    {
        for(int i = 0; i < mask; i++)
        {
            if(bit(mask , i) == 0) continue;

            pii prev = dp[flip(mask , i)];

            if((prev.se + b[i]) == a[prev.fi + 1])
            {
                dp[mask] = max(dp[mask] , {prev.fi + 1 , 0});
            }
            else 
            {
                dp[mask] = max(dp[mask] , {prev.fi , prev.se + b[i]});
            }
        }
    }

    for(int i = 0; i < (1 << m); i++)
    {
        if(dp[i].fi == n)
        {
            cout << "YES" << '\n'; return;
        }
    }
    cout << "NO" << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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