Submission #852634

#	Time	Username	Problem	Language	Result	Execution time	Memory
852634		t6twotwo	Bank (IZhO14_bank)	C++17	71 / 100	1046 ms	1116 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	vector<int> b(M);
	for (int i = 0; i < M; i++) {
        cin >> b[i];
    }
    vector dp(N + 1, vector<bool>(1 << M));
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << M); j++) {
            if (!dp[i][j]) {
                continue;
            }
            vector<int> v;
            for (int k = 0; k < M; k++) {
                if (!(j >> k & 1)) {
                    v.push_back(k);
                }
            }
            int K = v.size();
            for (int k = 0; k < (1 << K); k++) {
                int s = 0, t = 0;
                for (int p = 0; p < K; p++) {
                    if (k >> p & 1) {
                        s += b[v[p]];
                        t += 1 << v[p];
                    }
                }
                if (s == a[i]) {
                    dp[i + 1][j + t] = 1;
                }
            }
        }
    }
    for (int i = 0; i < (1 << M); i++) {
        if (dp[N][i]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
	return 6/22;
}

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