제출 #1282547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282547		kreukpg	Bank (IZhO14_bank)	C++20	100 / 100	793 ms	16864 KiB

bank

// code by phongln
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define fo(i, a, b, k) for(ll i=a; i<=b; i+=k)
#define fod(i, a, b, k) for(ll i=a; i>=b; i-=k)
#define lop(x, s) for(auto x : s)
#define sz(s) s.size()
#define all(s) s.begin(), s.end()
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define sq(a) (a)*(a)
#define cb(a) (a)*(a)*(a)
#define NAME "TEST"
const ll inf=1e18;
const ll mod=1e9+7;
const ll maxn=1e6+5;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void init(){
}

void solve(){
    ll n, m;
    cin >> n >> m;
    vll a(n), b(m);
    fo(i, 0, n-1, 1) cin >> a[i];
    fo(i, 0, m-1, 1) cin >> b[i];
    sort(all(a));
    ll num_masks = 1 << m;
    vll sum(num_masks, 0);
    fo(i, 0, m-1, 1) sum[1 << i] = b[i];
    fo(mask, 1, num_masks-1, 1){
        ll lsb = mask & (-mask);
        if(mask != lsb) sum[mask] = sum[mask ^ lsb] + sum[lsb];
    }
    vector<ll> dp(num_masks, -1);
    dp[0] = 0;
    bool ok = 0;
    fo(mask, 0, num_masks-1, 1){
        if(dp[mask] == -1) continue;
        ll k = dp[mask];
        if(k == n){
            ok = 1;
            break;
        }
        ll need = a[k];
        ll cmask = (num_masks - 1) ^ mask;
        for(ll s = cmask; s > 0; s = (s - 1) & cmask){
            if(sum[s] == need){
                ll newmask = mask | s;
                dp[newmask] = max(dp[newmask], k + 1);
            }
        }
    }
    if(!ok){
        fo(mask, 0, num_masks-1, 1){
            if(dp[mask] == n){
                ok = 1;
                break;
            }
        }
    }
    cout << (ok ? "YES" : "NO");
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen(NAME".INP", "r", stdin);
    // freopen(NAME".OUT", "w", stdout);
    init();
    ll t = 1;
    while(t--){
        solve();
    }
    return 0;
}

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