Submission #984984

#	Time	Username	Problem	Language	Result	Execution time	Memory
984984		TroySer	Bank (IZhO14_bank)	C++17	100 / 100	587 ms	128064 KiB

bank

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

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

bool bm(int bills, int ind) {
    if (ind == N) {
        cout << "YES\n";
        exit(0);
        return true;
    } else if (bills == 0) {
        return false;
    } else if (dp[bills][ind] != -1) {
        return dp[bills][ind];  
    } else {
        bool anyTrue = false;
        for (auto bitmasks: possibleSums[salaries[ind]]) {
            if ((bills & bitmasks) == bitmasks)
                anyTrue = anyTrue || bm(bills ^ bitmasks, ind+1);
        }
        dp[bills][ind] = anyTrue;
        return anyTrue;
    }
}

int main() {
    cin >> N >> M;
    salaries.resize(N);
    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);
        }
    }

    dp.resize((1 << M), vector<int>(N, -1));
    bm((1 << M) - 1, 0);

    cout << "NO\n";
}

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