제출 #1117643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117643		NguyenPhucThang	은행 (IZhO14_bank)	C++14	71 / 100	1076 ms	18000 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vii;
typedef pair<int, pair<int, int>> piii;

#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int base = 31;
const ll mod = 1e9 + 7; // 998244353;
const ll oo = (ll) 1e16;
const int N = 2e5 + 5;

vi mask_list[N];
bool dp[25][(1 << 20)];
int a[N], b[N], m, n; 

namespace sub1 {
    bool res = false;
    int sum = 0;
    void backtrack(int i) {
        forr(j, 0, 1) {
            sum += b[i] * j;
            if (i == m) {
                if (sum == a[1]) res = true;
            }
            else backtrack(i + 1);
            sum -= b[i] * j;
        }
    }
    void solve() {
        backtrack(1);
        cout << (res ? "YES" : "NO");
    }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

    cin >> n >> m;
    forr(i, 1, n) cin >> a[i];
    forr(i, 1, m) cin >> b[i];

    if (n == 1) {
        sub1::solve();
        return 0;
    }

    forr(mask, 0, (1 << m) - 1) {
        int sum = 0;
        forr(i, 1, m) if (bit(mask, i - 1)) sum += b[i];
        mask_list[sum].pb(mask);
    }

    dp[0][0] = true;

    forr(i, 1, n) {
        forr(mask, 0, (1 << m) - 1) {
            for(int mask2 : mask_list[a[i]]) {
                if ((mask | mask2) == mask)
                    dp[i][mask] |= dp[i - 1][mask ^ mask2];
            }
        }
    }

    bool res = false;
    forr(mask, 0, (1 << m) - 1) res |= dp[n][mask];
    cout << (res ? "YES" : "NO");

    return 0;
}

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