Submission #1096566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096566		artem_svl	Bank (IZhO14_bank)	C++17	100 / 100	299 ms	60456 KiB

bank

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cassert>
#include <queue>
#include <cmath>

typedef long long ll;

using namespace std;

const int MAXN = 20;

int possible[MAXN+1][1<<MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    int N, M;
    while(test--) {
        cin >> N >> M;
        vector<int> a(N), b(M), pref_sum(N+1, 0);
        for(int i = 0; i < N; ++i) {
            cin >> a[i];
            pref_sum[i+1] = pref_sum[i] + a[i];
        }
        for(int i = 0; i < M; ++i) {
            cin >> b[i];
        }
        vector<vector<int>> sets(1000*M+1);
        sets[0].push_back(0);
        for(int i = 0; i < M; ++i) {
            for(int j = 1000*M; j >= b[i]; j--) {
                for(const int S: sets[j-b[i]]) {
                    sets[j].push_back(S+(1<<i));
                }
            }
        }

        possible[0][0] = 1;
        for(int u = 0; u < N; ++u) {
            for(const int prevS: sets[pref_sum[u]]) {
                if(possible[u][prevS]) {
                    for(const int addS: sets[a[u]]) {
                        if((prevS & addS) == 0) {
                            possible[u+1][prevS+addS] = 1;
                        }
                    }
                }
            }
        }
        // for(int i = 0; i < 10; ++i) {
        //     cout << i << ": ";
        //     for(const int S: sets[i]) {
        //         cout << S << ' ';
        //     }
        //     cout << '\n';
        // }

        for(int S = 0; S < (1<<M); ++S) {
            if(possible[N][S]) {
                cout << "YES\n";
                return 0;
            }
        }
        cout << "NO\n";
    }
}

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