제출 #469963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469963		dooompy	은행 (IZhO14_bank)	C++17	100 / 100	144 ms	8516 KiB

bank

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

pair<int, int> dp[1 << 21];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;
    vector<int> people(n);
    for (int i = 0; i < n; i++) {
        cin >> people[i];
    }
    vector<int> note(m);
    for (int i = 0; i < m; i++) {
        cin >> note[i];
    }

    dp[0] = {0, 0};

    for (int i = 1; i < (1 << m); i++) {
        dp[i] = {-1, -1};

        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                int subset = i - (1 << j);

                auto prev = dp[subset];

                prev.second += note[j];

                if (prev.second == people[prev.first]) {
                    prev.first++;
                    prev.second = 0;
                }

                if (prev.first == n) {
                    cout << "YES";
                    return 0;
                }

                dp[i] = max(dp[i], prev);
            }
        }

    }

    cout << "NO";
}

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