제출 #847292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847292		c2zi6	은행 (IZhO14_bank)	C++14	100 / 100	512 ms	136060 KiB

bank

    #include <bits/stdc++.h>
     
    using namespace std;
    using ll = long long;
     
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        int n, m;
        cin >> n >> m;
        vector<int> a(n), b(m);
        for (int& x : a) cin >> x;
        for (int& x : b) cin >> x;
     
        const int MAXA = 1001;
     
        int dpc[1<<m]{};
        bitset<MAXA> dpp[1<<m];
        dpp[0] = bitset<MAXA>(1);
        for (int s = 1; s < (1<<m); s++) {
            int bestc = -1;
            bitset<MAXA> bestp;
            for (int i = 0; i < m; i++) {
                if (!(s & (1<<i))) continue;
                int ps = (s ^ (1<<i));
                int curc = dpc[ps];
                bitset<MAXA> curp = (dpp[ps]<<b[i]);
                if (curp[a[curc]]) curc++, curp = bitset<MAXA>(1);
                if (curc > bestc) {
                    bestc = curc;
                    bestp = curp;
                } else if (curc == bestc) {
                    bestp |= curp;
                }
                //cout << curc << " " << curp << endl;
            }
            dpc[s] = bestc;
            dpp[s] = bestp;
        }
        bool ans = false;
        for (int i = 0; i < (1<<m); i++) {
            if (dpc[i] == n) ans = true;
        }
        if (ans) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
     
    int main() {
        int t = 1;
        //cin >> t;
        while (t--) solve();
    }

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