제출 #1344904

#제출 시각아이디문제언어결과실행 시간메모리
1344904x_a은행 (IZhO14_bank)C++20
100 / 100
64 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;
            if(dp[new_mask] == -1){
                k = a[cnt + 1];
                ll curr = left[mask] + b[i + 1];
                if(curr < k){
                    dp[new_mask] = cnt;
                    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...