제출 #1351796

#제출 시각아이디문제언어결과실행 시간메모리
1351796waygonz은행 (IZhO14_bank)C++20
19 / 100
127 ms16708 KiB
#include <bits/stdc++.h>
#define int long long
#define float long double
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define f first
#define s second
#define ve vector
#define emb emplace_back
#define em emplace

using namespace std;

const int inf = 1e18;
const int mod = 1e9 + 7;

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    ve<int> a(n), b(m);
    for (auto &e : a) cin >> e;
    for (auto &e : b) cin >> e;
    ve<pii> dp((1 << m), {-1, -1});
    dp[0] = {0, 0};
    bool ok = false;
    function<pii(int)> solve = [&](int mask) {
        if (ok) return make_pair(0LL, 0LL);
        if (dp[mask].f != -1) return dp[mask];
        pii ans = {0, 0};
        for (int i = 0; i < m; i++) {
            if (!(mask & (1 << i))) continue;
            pii prev = solve(mask & ~(1 << i));
            if (ok) return make_pair(0LL, 0LL);
            if (prev.s + b[i] == a[prev.f]) ans = {prev.f+1, 0};
            else ans = {prev.f, prev.s + b[i]};
            if (ans.f == n) { ok = true; return make_pair(0LL, 0LL); }
        }
        return dp[mask] = ans;
    };
    solve((1 << m) - 1);
    cout << (ok ? "YES" : "NO");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...