제출 #1232107

#제출 시각아이디문제언어결과실행 시간메모리
1232107samuelandrianoo_은행 (IZhO14_bank)C++20
100 / 100
110 ms16848 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define pb push_back

const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const ll modinv = 1e9 + 5;

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

//ll modinv(ll a, ll b){
//    return (a % mod * expo(b, mod - 2) % mod) % mod;
//}

int main(){
    fastio();
    ll n, m;
    cin >> n >> m;

    ll a[n + 5], b[m + 5];
    for (ll i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (ll i = 1; i <= m; i++) cin >> b[i];
    ll dp[ll(1 << m) + 10][2];
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    dp[0][1] = 0;

    bool ans = 0;   
    for (ll i = 0; i < (1 << m); i++){
        for (ll j = 0; j < m; j++){
            if (((1 << j) & i) == 0) continue;

            ll prev = ((1 << j) ^ i);

            ll duit = 0;
            duit = b[j + 1];

            if (dp[prev][0] == -1) continue;

            ll need = a[dp[prev][0] + 1];

            if (duit + dp[prev][1] < need){
                dp[i][0] = dp[prev][0];
                dp[i][1] = dp[prev][1] + duit;
            }

            else if (duit + dp[prev][1] == need){
                dp[i][0] = dp[prev][0] + 1;
                dp[i][1] = 0;
            }
        }

        if(dp[i][0] == n)ans = 1;
    } 

    if (ans) cout << "YES" << endl;
    else 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...