제출 #1132908

#제출 시각아이디문제언어결과실행 시간메모리
1132908DangKhoizzzz은행 (IZhO14_bank)C++20
100 / 100
100 ms8560 KiB
#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 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 < m; i++)
        {
            if(((mask >> i)&1) == 0) continue;

            pii prev = dp[mask ^ (1 << 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...