Submission #332234

#	Time	Username	Problem	Language	Result	Execution time	Memory
332234		topovik	Bank (IZhO14_bank)	C++14	100 / 100	900 ms	152172 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define f first
#define s second
#define pb push_back
#define INF 1000000000

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<
ll,
null_type,
greater<ll>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;

const ll N = 1 << 20;

set <short int> st[N];
set<short int> st1[N];

int gd[N];

int main()
{
//    freopen("bank.in", "r", stdin);
//    freopen("bank.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    int a[n], b[m];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    swap(n, m);
    for (int i = 0; i < (1 << n); i++)
    {
        int kol = 0;
        for (int j = 0; j < n; j++) kol += (i&(1 << j)) > 0;
        gd[i] = kol;
    }
    st1[0].insert(0);
    for (int j = 0; j < m; j++)
    {
        for (int i = 0; i < (1 << n); i++) st[i] = st1[i], st1[i].clear();
        for (int i = 0; i < (1 << n); i++)
          if ((n - gd[i]) >= (m - (j + 1)))
        {
            if (st[i].find(a[j]) != st[i].end())
            {
                st1[i].insert(0);
                continue;
            }
            for (auto g : st[i])
            {
                for (int c = 0; c < n; c++)
                    if (((1 << c)&i) == 0 && g + b[c] <= a[j] && (n - gd[i + (1 << c)]) >= (m - (j + 1))) st[i + (1 << c)].insert(g + b[c]);
            }
        }
    }
    for (int i = 0; i < (1 << n); i++)
        if (st1[i].size() > 0) {cout << "YES";return 0;}
    cout << "NO";
}

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