Submission #699803

#TimeUsernameProblemLanguageResultExecution timeMemory
699803hazzle은행 (IZhO14_bank)C++17
100 / 100
106 ms8652 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

int solve(){
        int n, m;
        cin >> n >> m;
        vec <int> a(n), b(m);
        for (auto &i: a) cin >> i;
        for (auto &i: b) cin >> i;
        vec <int> dp(1 << m, -1), le(1 << m, -1);
        dp[0] = le[0] = 0;
        for (int msk = 1; msk < (1 << m); ++msk){
                for (int i = 0; i < m; ++i){
                        if (~msk >> i & 1) continue;
                        int prv = msk ^ (1 << i);
                        if (dp[prv] == -1) continue;
                        int cur = le[prv] + b[i];
                        if (cur == a[dp[prv]]){
                                if (umax(dp[msk], dp[prv] + 1)) le[msk] = 0;
                        }
                        if (cur < a[dp[prv]]){
                                if (umax(dp[msk], dp[prv])) le[msk] = cur;
                        }
                }
        }
        for (int msk = 0; msk < (1 << m); ++msk){
                if (dp[msk] == n){
                        cout << "YES\n";
                        return 0;
                }
        }
        cout << "NO\n";
        return 0;
}

signed main(){
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int tst = 1; //cin >> tst;
        while(tst--) solve();
        return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...