Submission #1156108

#TimeUsernameProblemLanguageResultExecution timeMemory
1156108vincentbucourt1Bank (IZhO14_bank)C++20
100 / 100
99 ms16868 KiB
#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

int numPeople, numNotes;
int people[21], notes[21];
int idxSS[1 << 21], valSS[1 << 21];
bool ans = false;

signed main() {
    fastIO();
    cin >> numPeople >> numNotes;
    for (int i = 0; i < numPeople; i++) {
        cin >> people[i];
    }
    for (int i = 0; i < numNotes; i++) {
        cin >> notes[i];
    }
    idxSS[0] = 0;
    for (int mask = 0; mask < (1 << numNotes); mask++) {
        for (int note = 0; note < numNotes; note++) {
            if (mask&(1 << note)) continue;
            int idx = idxSS[mask];
            if (idx < numPeople && people[idx] == valSS[mask] + notes[note] && idxSS[mask | (1 << note)] <= idxSS[mask] + 1) {
                idxSS[mask | (1 << note)] = idxSS[mask] + 1;
                valSS[mask | (1 << note)] = 0;
            }
            else if (idxSS[mask | (1 << note)] <= idxSS[mask]) {
                idxSS[mask | (1 << note)] = idxSS[mask];
                valSS[mask | (1 << note)] = valSS[mask] + notes[note];
            }
        }
    }
    for (int mask = 0; mask < (1 << numNotes); mask++) {
        if (idxSS[mask] == numPeople) {
            ans = true;
        }
    }
    cout << (ans ? "YES" : "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...