제출 #535735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535735		nhquan	은행 (IZhO14_bank)	C++17	52 / 100	1091 ms	8404 KiB

bank

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define ii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define sz(a) (int)a.size()

#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)

#define ll long long

#define oo 1000000007
#define maxN 21
#define maxM 21

using namespace std;

int n, m, a[maxN], b[maxM];
int f[maxN][(1 << maxN)];

int getBit(int i, int x) {
    return (x >> i) & 1;
}

int dp(int i, int S) {
    if (!i) return 1;
    if (f[i][S] != -1) return f[i][S];
    for (int T = S; T; T = (T-1)&S) {
        int tmp = 0;
        fto(j, 0, m-1) {
            if (getBit(j, T)) tmp += b[j+1];
        }
        if (tmp == a[i] && dp(i-1, S^T)) return f[i][S] = 1;
    }
    return f[i][S] = 0;
}

int main() {

    cin >> n >> m;
    fto(i, 1, n) {
        cin >> a[i];
    }

    fto(i, 1, m) {
        cin >> b[i];
    }

    fto(i, 0, n) {
        fto(S, 0, (1 << m)-1) {
            f[i][S] = -1;
        }
    }

    fto(S, 0, (1 << m)-1) {
        if (dp(n, S)) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";

    return 0;
}

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