제출 #1344899

#제출 시각아이디문제언어결과실행 시간메모리
1344899x_a은행 (IZhO14_bank)C++20
19 / 100
62 ms16832 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main(){
    ll n, m, k; cin >> n >> m;
    vector<ll> a(n + 1), b(m + 1);
    for(ll i = 1; i <= n; i ++) cin >> a[i];
    for(ll i = 1; i <= m; i ++) cin >> b[i];
    vector<ll> dp(1LL << m, -1), left(1LL << m, -1);
    dp[0] = 0;
    left[0] = 0;

    ll x = 1LL << m;
    for(ll mask = 0; mask < x; mask ++){
        if(dp[mask] == -1) continue;
        ll cnt = dp[mask];

        if(cnt == n){
            cout << "YES" << endl;
            return 0;
        }

        for(ll i = 0; i < m; i ++){
            if((mask & 1LL << i)) continue;
            ll new_mask = mask | 1LL << i;
            k = a[cnt + 1];
            ll curr = left[mask] + b[i];
            if(curr < k){
                dp[new_mask] = dp[mask];
                left[new_mask] = curr;
            }
            else if(curr == k){
                dp[new_mask] = dp[mask] + 1;
                left[new_mask] = 0;
            }
        }
    }
    
    cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...