제출 #479995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479995		Dima_Borchuk	은행 (IZhO14_bank)	C++17	71 / 100	1090 ms	332 KiB

bank

#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) int32_t(x.size())
#define pii pair < int, int >
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define _ << ' ' <<
#define se second
#define fi first
//#define int ll

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = (int)1e9 + 9;
const int N = (int)1e6 + 5;
const int INF = (int)1e16 + 5;

vector < int > a, b;

vector < bool > used;

bool ans = true;

void solve(int l) {
    vector < pii > v;
    for (int i = 0; i < sz(b); i++) {
        if (!used[i]) {
            v.push_back({ b[i], i });
        }
    }

    int n = sz(v);
    for (int i = 1; i < (1 << n); i++) {
        int s = 0;
        for (int j = 0; j < n; j++) {
            if ((1 << j) & i) {
                s += v[j].first;
            }
        }
        if (s == a[l]) {
            if (l == sz(a) - 1) {
                cout << "YES\n";
                exit(0);
            }
            for (int j = 0; j < n; j++) {
                if ((1 << j) & i) {
                    used[v[j].second] = true;
                }
            }
            solve(l + 1);
            for (int j = 0; j < n; j++) {
                if ((1 << j) & i) {
                    used[v[j].second] = false;
                }
            }
        }
    }
}

int32_t main() {
    #ifdef LOCAL
//        freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    a.resize(n); b.resize(m); used.resize(m, false);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    solve(0);

    cout << "NO\n";
    return 0;
}

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