제출 #827352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827352		SoulKnight	은행 (IZhO14_bank)	C++17	100 / 100	101 ms	8532 KiB

bank

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

#define ll long long
#define ln '\n'

const int N = 20;
const int LG = 21;
const ll INF = 5e18;
const int MOD = 998244353;

int a[N], b[N], cover[(1<<N)+5], leftover[(1<<N)+5];
bool solve(){
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    memset(cover, -1, sizeof(cover));
    memset(leftover, -1, sizeof(leftover));
    cover[0] = leftover[0] = 0;

    for (int i = 0; i < (1 << m); i++){
        // cout << i << ln;
        for (int j = 0; j < m; j++){
            if (((1 << j) & i) == 0) continue;

            // let j be the last banknote in subset i
            int prev = i & ~(1 << j);
            if (cover[prev] == -1) continue;

            int cur = leftover[prev] + b[j];
            int target = a[cover[prev]];

            if (cur < target) {
                // cout << prev << ' ' << cover[prev] << ' ' << cur << ln;
                cover[i] = cover[prev];
                leftover[i] = cur;
            } else if (cur == target){
                // cout << prev << ' ' << cover[prev] + 1 << ' ' << 0 << ln;
                cover[i] = cover[prev] + 1;
                leftover[i] = 0;
            }
        }

        // cout << ln;

        if (cover[i] == n) return true;
    }
    return false;
}



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

    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);


    // ll T; cin >> T;
    // while (T--){
    //     solve();
    // }

    // init();
    // solve();
    cout << (solve()? "YES": "NO") << ln;

    return 0;
}

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