제출 #332226

#제출 시각아이디문제언어결과실행 시간메모리
332226topovik은행 (IZhO14_bank)C++14
0 / 100
200 ms200172 KiB
#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;
const int M = 20;

short int dp[N][M];
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 += (a[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))
        {
            if (st[i].find(a[j]) != st[i].end()) dp[i][j] = 1;
            if (dp[i][j] > 0)
            {
                st1[i].insert(0);
                continue;
            }
            for (auto g : st[i])
            {
                for (int c = 0; c < n; c++)
                    if (!((1 << c)&i) && g + b[c] <= a[j] && (n - gd[i + (1 << c)]) >= (m - j)) st[i + (1 << c)].insert(g + b[c]);
            }
        }
    }
    for (int i = 0; i <= (1 << n); i++)
        if (st1[i].find(0) != st1[i].end()) {cout << "YES";return 0;}
    cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...