제출 #1363498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363498		mine255	Bank (IZhO14_bank)	C++20	71 / 100	1094 ms	8468 KiB

bank

#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
#define ii pair<int,int>
#define lii pair<ll,ll>
#define fi first
#define se second
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

int n,m;
int a[27];
int b[27];

namespace sub1 {
    bool check() {
        return n == 1;
    }

    bool _try(int i, int s) {
        if (s > a[1]) return 0;
        if (s == a[1]) return 1;
        if (i > m) return 0;

        bool res = _try(i+1,s);
        if (!res) res = _try(i+1,s+b[i]);

        return res;
    }

    void solve() {
        if (_try(1,0)) cout << "YES";
        else cout << "NO";
    }
}

namespace sub2 {
    bool check() {
        // return n <= 10 && m <= 10;
        return 1;
    }

    bool dp[27][MASK(20)+7];
    int sum[MASK(20)+7];

    void solve() {
        for (int i=0; i<MASK(m); i++) {
            int mask = i;
            int cur = 0;

            while (mask > 0) {
                int pos = __builtin_ctz(mask);
                cur += b[pos+1];
                mask -= mask & -mask;
            }

            sum[i] = cur;
        }

        dp[0][0] = 1;
        for (int i=0; i<n; i++) {
            for (int j=0; j<MASK(m); j++) {
                if (!dp[i][j]) continue;

                int mask = (MASK(m)-1) ^ j;
                for (int k=mask; k>0; k--) {
                    k &= mask;

                    if (sum[k] == a[i+1]) dp[i+1][j|k] = 1;
                }                
            }
        }

        bool res = 0;
        for (int i=0; i<MASK(m); i++) {
            if (dp[n][i] == 1) {
                res = 1;
                break;
            }
        }

        if (res) cout << "YES";
        else cout << "NO";
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    #ifdef EMERGENCY_DEBUG
    freopen(_FILE".inp","r",stdin);
    freopen(_FILE".out","w",stdout);
    #endif

    cin >> n >> m;

    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }

    for (int i=1; i<=m; i++) {
        cin >> b[i];
    }

    if (sub1::check()) return sub1::solve(),0;
    if (sub2::check()) return sub2::solve(),0; 

    return 0;
}

• 서브태스크 1: 19 / 19
• 서브태스크 2: 25 / 25
• 서브태스크 3: 27 / 27
• 서브태스크 4: 0 / 29