Submission #922732

#	Time	Username	Problem	Language	Result	Execution time	Memory
922732		eysbutno	Bank (IZhO14_bank)	C++11	52 / 100	1028 ms	9060 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define pb push_back
#define ins insert
#define f first 
#define s second 

template<class T> bool smin(T& a, T b) {
    return b < a ? a = b, 1 : 0;
}
template<class T> bool smax(T& a, T b) {
    return b > a ? a = b, 1 : 0;
}
bool dp[2][1 << 20];
vector<int> msks[1001];
int main() {
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    for (int& i : a) cin >> i;
    for (int& i : b) cin >> i;
    for (int i = 0; i < (1 << m); i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) sum += b[j];
        }
        if (sum <= 1000) msks[sum].pb(i);
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << m); j++) {
            for (int k : msks[a[i]]) {
                if ((j & k) == k) {
                    dp[1][j] |= dp[0][j ^ k];
                }
            }
        }
        for (int j = 0; j < (1 << m); j++) {
            swap(dp[0][j], dp[1][j]);
            dp[1][j] = false;
        }
    }
    for (int i = 0; i < (1 << m); i++) {
        if (dp[0][i]) {
            cout << "YES" << '\n';
            return 0;
        }
    }
    cout << "NO" << '\n';
}

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