제출 #815797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815797		phi	은행 (IZhO14_bank)	C++17	100 / 100	191 ms	3156 KiB

bank

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];

    vector<vector<bool>> dp(n + 1, vector<bool>(1 << m));
    dp[0][0] = true;

    for (int mask = 0; mask < (1 << m); mask++) {
        for (int i = 0; i < n; i++) {
            if (!dp[i][mask]) continue;

            int left = 0;
            for (int j = 0; j <= i; j++)
                left += a[j];

            for (int j = 0; j < m; j++)
                if (mask & (1 << j))
                    left -= b[j];

            for (int j = 0; j < m; j++) {
                if (mask & (1 << j)) continue;
                if (left < b[j]) continue;
                if (left == b[j])
                    dp[i + 1][mask | (1 << j)] = true;
                else
                    dp[i][mask | (1 << j)] = true;
            }
        }
    }

    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[n][mask]) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";

    return 0;
}

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