Submission #984729

#TimeUsernameProblemLanguageResultExecution timeMemory
984729TroySerBank (IZhO14_bank)C++17
19 / 100
1060 ms440 KiB
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> salaries;
vector<int> bankNotes;

vector<int> params;

int LSOne(int a) {
    return a & (-a);
}

bool canDo = false;

void bitmask(int ind, vector<int> &params) {
    if (ind == M) {
        // checker
        for (int i = 0; i < N; i++) {
            // cout << i << ": ";
            int iBitmask = params[i];
            int currSum = 0;
            while (iBitmask) {
                int currInd = __builtin_ctz(LSOne(iBitmask));
                // cout << currInd << ", ";
                currSum += bankNotes[currInd];
                iBitmask -= LSOne(iBitmask);
            }
            // cout << "\n";
            if (currSum != salaries[i]) return;
        }
        cout << "YES\n";
        exit(0);
    } else {
        for (int i = 0; i < N; i++) {
            params[i] |= (1 << ind);
            bitmask(ind+1, params);
            params[i] ^= (1 << ind);
        }
        bitmask(ind+1, params);
    }
}

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];
    }
    bitmask(0, params);
    cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...