제출 #598410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598410		jack715	은행 (IZhO14_bank)	C++14	52 / 100	1083 ms	20564 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
#define int long long

using namespace std;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<int> people(n), money(m), dp(1<<m, 0);
    for (int i = 0; i < n; i++)
        cin >> people[i];
    for (int i = 0; i < m; i++)
        cin >> money[i];

    vector<vector<int> > make(1005);
    for (int b = 0; b < (1<<m); b++) {
        int now = 0;
        for (int j = 0; j < m; j++)
            if (b&(1<<j)) now += money[j];
        if (now <= 1000)
            make[now].pb(b);
    }

    bool ans = 0;
    for (int b = 0; b < (1<<m); b++) {
        if (dp[b] == n) {
            ans = 1;
            continue;
        }

        for (int pos : make[people[dp[b]]])
            if (pos+b == (pos^b))
                dp[pos^b] = max(dp[pos^b], dp[b]+1);
    }

    if (ans)
        cout << "YES\n";
    else 
        cout << "NO\n";
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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