제출 #1279732

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

bank

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll A = 1000;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);


int main() {
    Algerian OI

    ll n, m;

    cin >> n >> m;
    vector<ll> a(n), b(m);

    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < m; i++) cin >> b[i];

    vector<ll> dp(1 << m), left(1 << m);

    for (ll mask = 1; mask < (1 << m); mask++) {
        for (ll i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                ll new_mask = mask ^ (1 << i);
                ll val = dp[new_mask];
                
                if (dp[new_mask] < n && left[new_mask] + b[i] == a[dp[new_mask]]) {
                    val++;

                    if (val > dp[mask]) {
                        dp[mask] = val;
                        left[mask] = 0;
                    }
                } else {
                    if (dp[new_mask] >= dp[mask]) {
                        dp[mask] = dp[new_mask];
                        left[mask] = left[new_mask] + b[i];
                    }
                }
            }
        }
    }

    // dbg(left[4]);

    cout << (dp[(1 << m) - 1] == n ? "YES\n" : "NO\n");

    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29