제출 #1299854

#제출 시각아이디문제언어결과실행 시간메모리
1299854goppamach은행 (IZhO14_bank)C++20
100 / 100
301 ms12468 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 20;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

#define bit(i, mask) ((mask >> i) & 1)

int dp[1 << N];
map<int, vi> memo;
int a[N], b[N];
int n, m;

void solve() {
    cin >> n >> m;

    FOR(i, 0, n - 1) {
        cin >> a[i];
    }

    FOR(i, 0, m - 1) {
        cin >> b[i];
    }

    int salary_sum = accumulate(a, a + n, 0);
    int banknote_sum = accumulate(b, b + m, 0);
    if (salary_sum > banknote_sum) {
        cout << "NO" << el;
        return;
    }

    const int full_mask = (1 << m) - 1;

    FOR(mask, 0, full_mask) {
        int sum = 0;
        FOR(i, 0, m - 1) {
            if (bit(i, mask)) {
                sum += b[i];
            }
        }
        memo[sum].push_back(mask);
    }

    fill(all(dp), -1);
    dp[0] = 0;

    FOR(mask, 0, full_mask) {
        int satisfied = dp[mask];
        if (satisfied == -1 || satisfied == n) continue;
        for (int &sub : memo[a[satisfied]]) {
            if ((mask & sub) == 0) {
                chmax(dp[mask | sub], satisfied + 1);
            }
        }
    }

    cout << (*max_element(all(dp)) == n ? "YES" : "NO") << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM "bank"
    freopen(PROBLEM ".in", "r", stdin);
    freopen(PROBLEM ".out", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...