제출 #1127405

#제출 시각아이디문제언어결과실행 시간메모리
1127405FucKanh은행 (IZhO14_bank)C++20
0 / 100
8 ms328 KiB
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

int n,m;
int f[1<<20];
int a[30], b[30], c[30];

void solve() {
    cin >> n >> m;
    if (n > m) {
        cout << "NO";
        return;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= min(7ll,m); i++) {
        cin >> b[i];
    }

    for (int i = 8; i <= m; i++) {
        cin >> c[i - 7];
    }
    vector<int> v1,v2;
    for (int i = 1; i <= min(7ll,m); i++) v1.push_back(i);
    for (int i = 8; i <= m; i++) v2.push_back(i-7);
    f[0] = 1;
    for (int state = 1; state < (1<<n); state++) {
        if (__builtin_popcount(state) > 7) continue;
        vector<int> t,q;
        t = v1;
        int s= 0;
        for (int i = 1; i <= n; i++) {
            if (state & (1<<i-1)) {
                s += a[i];
                q.push_back(s);
            }
        }
        int ok = 0;
        do {
            int pos = 0;
            int sum = 0;
            for (int val : t) {
                sum += b[val];
                if (sum > q[pos]) break;
                if (sum == q[pos])pos++;
                if (pos == q.size()) {
                    ok = 1;
                    break;
                }
            }
        } while (next_permutation(t.begin(), t.end()));
        f[state] = ok;
//        cerr << bitset<14>(state) << ": " << ok << endl;
//        for (int val : q) cerr << val << " "; cerr << endl;
//        system("pause");
    }

    if (f[(1<<n)-1]) {
        cout << "YES";
        return;
    }

    for (int state = 1; state < (1<<n); state++) {
         if (__builtin_popcount(state) > 7) continue;
        vector<int> t,q;
        t = v2;
        int s= 0;
        for (int i = 1; i <= n; i++) {
            if (state & (1<<i-1)) {
                s += a[i];
                q.push_back(s);
            }
        }
        int ok = 0;
        do {
            int pos = 0;
            int sum = 0;
            for (int val : t) {
                sum += c[val];
                if (sum > q[pos]) break;
                if (sum == q[pos])pos++;
                if (pos == q.size()) {
                    ok = 1;
                    break;
                }
            }
        } while (next_permutation(t.begin(), t.end()));
        if (ok && f[((1<<n)-1) ^ state]) {
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...