제출 #1368621

#제출 시각아이디문제언어결과실행 시간메모리
1368621bnijaamaa은행 (IZhO14_bank)C++20
19 / 100
63 ms16856 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define nn endl
#define pb push_back

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    vector<int> dp((1LL << m), -1), memo((1LL << m),  -1);
    dp[0] = 0;
    memo[0] = 0;
    for (int mask = 0; mask < (1LL << m); mask++) {
        if (dp[mask] == -1) continue;
        int id = memo[mask];
        if (id >= n) continue;
        if (dp[mask] == a[id]) {
            if (memo[mask] < id + 1) {
                memo[mask] = id + 1;
                dp[mask] = 0;
            }
            continue;
        }
        for (int i = 0; i < m; i++) {
            if (mask & (1LL << i)) continue;
            int ns = dp[mask] + b[i];
            if (ns <= a[id]) {
                int j = mask | (1LL << i);
                if (memo[j] < id || (memo[j] == id && dp[j] < ns)) {
                    memo[j] = id;
                    dp[j] = ns;
                }
            }
        }
    }
    bool ok = false;
    for (int i = 0; i < (1LL << m); i++) {
        if (memo[i] == n) {
            ok = true;
            break;
        }
    }
    cout << (ok ? "YES" : "NO") << nn;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…