제출 #980384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980384		54skyxenon	은행 (IZhO14_bank)	C++17	100 / 100	99 ms	8784 KiB

bank

// https://oj.uz/problem/view/IZhO14_bank 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> A(n);
    for (int& a : A) {
        cin >> a;
    }

    vector<int> B(m);
    for (int& b : B) {
        cin >> b;
    }

    vector<int> dp_prefix(1 << m);
    vector<int> dp_remaining(1 << m);

    for (int bitmask = 1; bitmask < (1 << m); bitmask++) {
        for (int last = 0; last < m; last++) {
            if (!(bitmask & (1 << last))) {
                continue;
            }

            int previous = bitmask ^ (1 << last);
            int sum = dp_remaining[previous] + B[last];

            if (sum == A[dp_prefix[previous]]) {
                if (dp_prefix[previous] + 1 > dp_prefix[bitmask]) {
                    dp_prefix[bitmask] = dp_prefix[previous] + 1;
                    dp_remaining[bitmask] = 0;
                }
            }
            else {
                if (dp_prefix[previous] >= dp_prefix[bitmask]) {
                    dp_prefix[bitmask] = dp_prefix[previous];
                    dp_remaining[bitmask] = sum;
                }
            }
        }

        if (dp_prefix[bitmask] == n) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29