제출 #930356

#제출 시각아이디문제언어결과실행 시간메모리
930356uped은행 (IZhO14_bank)C++14
52 / 100
1046 ms31148 KiB
#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

set<tuple<int, int, int>> visited;

const int MAX = 20;
int a[MAX + 1];
int b[MAX];
int n, m;

void solve(int idx, int val, int mask) {
    if (visited.count({idx, val, mask})) return;
    visited.emplace(idx, val, mask);
    if (idx == n) return;
    for (int i = 0; i < m; ++i) {
        if (mask & (1 << i)) continue;
        if (val - b[i] == 0) {
            solve(idx + 1, a[idx + 1], mask | (1 << i));
        } else if (val - b[i] > 0) {
            solve(idx, val - b[i], mask | (1 << i));
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    solve(0, a[0], 0);
    bool ans = false;
    for (int i = 0; i < (1 << m); ++i) {
        if (visited.count({n, 0, i})) {
            ans = true;
            break;
        }
    }
    cout << (ans ? "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...