제출 #984974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984974		TroySer	은행 (IZhO14_bank)	C++17	71 / 100	1074 ms	7040 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M;
vector<int> salaries;
vector<int> bankNotes;

vector<vector<int> > possibleSums;
 
vector<int> params;
 
int LSOne(int a) {
    return a & (-a);
}

void bm(int bills, int ind) {
    if (ind == N) {
        cout << "YES\n";
        exit(0);
        return;
    } else if (bills == 0) {
        return;
    } else {
        for (auto bitmasks: possibleSums[salaries[ind]]) {
            if ((bills & bitmasks) == bitmasks)
                bm(bills ^ bitmasks, ind+1);
        }
    }
}

int main() {
    cin >> N >> M;
    salaries.resize(N);
    params.resize(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> salaries[i];
    }
    bankNotes.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> bankNotes[i];
    }

    possibleSums.resize(1000 + 1);
    for (int i = 0; i < (1 << M); i++) {
        int currSum = 0;
        for (int j = 0; j < M; j++) {
            if (i & (1 << j)) {
                currSum += bankNotes[j];
            }
        }
        if (currSum <= 1000) {
            possibleSums[currSum].push_back(i);
        }
    }

    bm((1 << M) - 1, 0);

    cout << "NO\n";
}

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