Submission #1231512

#TimeUsernameProblemLanguageResultExecution timeMemory
1231512Dreamy_lovesper은행 (IZhO14_bank)C++20
100 / 100
556 ms204736 KiB
#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first 
#define se second 
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 100'007
ll n, m;
ll a[27], b[27];

namespace LoveLast {

    ll  f[27][(1 << 20) + 7];
    vll c[mxn];

    void DreamyLove () {

        fu(msk, 1, (1 << m) - 1) {
            ll cr = 0;
            fu(j, 0, m - 1) if(Bitc(msk, j)) cr += b[j + 1];
            c[cr].pb(msk);
        }

        c[0].pb(0);
        f[0][0] = 1;
        ll prev = 0;
        fu(i, 1, n) {
            vll tmp;
            for(auto&j: c[prev]) {
                if(!f[i - 1][j]) continue;
                for(auto&msk: c[a[i]]) {
                    if(msk & j) continue;
                    f[i][msk | j] = 1;
                    tmp.pb(msk | j);
                }
            }
            prev += a[i];
        }

        ll o = 0;
        fu(msk, 1, (1 << m) - 1) o |= f[n][msk];

        if(!o) return void(cout << "NO");
        cout << "YES";

        //
    }
}

void lovesper(const ll &TestCase) {
    
    cin >> n >> m;

    fu(i, 1, n) cin >> a[i];
    fu(i, 1, m) cin >> b[i];

    LoveLast::DreamyLove();

}

signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    
    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    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...