제출 #1360695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360695		domi	은행 (IZhO14_bank)	C++20	100 / 100	78 ms	16848 KiB

bank

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 20;
const int MSK = (1LL << NMAX);

using namespace std;

pair<int, int> dp[MSK + 5]; /// (mx_pref, leftover)
int a[NMAX + 5], b[NMAX + 5], n, m;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= m; ++i)
        cin >> b[i];

    fill(dp + 1, dp + MSK + 2, make_pair(-1, -1));
    dp[0] = {0, 0};
    for (int msk = 0; msk < (1LL << m); ++msk) {
        for (int nxt = 1; nxt <= m; ++nxt) {
            if ((msk & (1LL << (nxt - 1)))) continue;
            if (dp[msk].fi == -1) continue;

            int new_msk = (msk | (1LL << (nxt - 1)));
            int cur_money = dp[msk].se + b[nxt];
            int target = a[dp[msk].fi + 1];

            if (cur_money < target) {
                dp[new_msk].fi = dp[msk].fi;
                dp[new_msk].se = cur_money;
            }
            else if (cur_money == target) {
                dp[new_msk].fi = dp[msk].fi + 1;
                dp[new_msk].se = 0;
            }
        }
    }

    auto [best_pref, leftover] = *max_element(dp, dp + MSK);
    cout << (best_pref == n ? "YES\n" : "NO\n");
    return 0;
}

• 서브태스크 1: 19 / 19
• 서브태스크 2: 25 / 25
• 서브태스크 3: 27 / 27
• 서브태스크 4: 29 / 29