제출 #1222771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222771		toast12	은행 (IZhO14_bank)	C++20	100 / 100	194 ms	16972 KiB

bank

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1), b(m+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    vector<pair<int, int>> dp((1<<(m+1))+1, {-1, -1});
    // dp[mask].first stores the maximum prefix of salaries that the banknotes in the mask can pay
    // dp[mask].second stores the leftover sum of banknotes after the first dp[mask].first salaries have been paid
    dp[0] = {0, 0};
    bool poss = false;
    for (int mask = 0; mask < (1<<(m+1)); mask++) {
        for (int last = 1; last <= m; last++) {
            if (mask & (1<<last)) {
                int m2 = mask ^ (1<<last);
                if (dp[m2].first != -1) {
                    if (a[dp[m2].first+1] == dp[m2].second+b[last]) {
                        dp[mask].first = dp[m2].first+1;
                        dp[mask].second = 0;
                    }
                    else if (a[dp[m2].first+1] > dp[m2].second+b[last]) {
                        dp[mask].first = dp[m2].first;
                        dp[mask].second = dp[m2].second+b[last];
                    }
                }
            }
        }
        if (dp[mask].first == n) {
            poss = true;
            break;
        }
    }
    if (poss) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

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