Submission #734113

#	Time	Username	Problem	Language	Result	Execution time	Memory
734113		benjaminkleyn	Bank (IZhO14_bank)	C++17	71 / 100	1085 ms	8628 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, a[20], b[20];
vector<int> masks[20001];

set<int> masks1, masks2;
void search1(int i, int cur_mask)
{
    if (i == n / 2)
    {
        masks1.insert(cur_mask);
        return;
    }
    for (const int &mask : masks[a[i]])
        if ((cur_mask & mask) == 0)
            search1(i + 1, cur_mask | mask);
}
void search2(int i, int cur_mask)
{
    if (i == n)
    {
        masks2.insert(cur_mask);
        return;
    }
    for (const int &mask : masks[a[i]])
        if ((cur_mask & mask) == 0)
            search2(i + 1, cur_mask | mask);
}

struct TrieNode
{
    bool is_end;
    int cnt;
    TrieNode *children[2];
    TrieNode()
    {
        is_end = false;
        children[0] = children[1] = nullptr;
    }
};

void insert(int x, TrieNode *root)
{
    TrieNode *p = root;
    for (int i = 0; i < m; i++)
    {
        if (p->children[x & 1] == nullptr)
            p->children[x & 1] = new TrieNode();
        p = p->children[x & 1];
        x >>= 1;
    }
    p->is_end = true;
}

bool find(int x, TrieNode *p, int i = 0)
{
    if (p == nullptr)
        return false;
    if (i == m)
        return p->is_end;

    if (x & 1)
        return find(x >> 1, p->children[0], i + 1);
    else
        return find(x >> 1, p->children[0], i + 1) || find(x >> 1, p->children[1], i + 1);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    for (int mask = 0; mask < (1 << m); mask++)
    {
        int sum = 0;
        for (int i = 0; i < m; i++)
            if (mask & (1 << i))
                sum += b[i];
        masks[sum].push_back(mask);
    }
    search1(0, 0);
    search2(n / 2, 0);

    TrieNode *root = new TrieNode;
    for (int mask1 : masks1)
        insert(mask1, root);
    for (int mask2 : masks2)
        if (find(mask2, root))
            return cout << "YES\n", 0;
    cout << "NO\n";

    return 0;
}

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