Submission #414584

#	Time	Username	Problem	Language	Result	Execution time	Memory
414584		nkato	Bank (IZhO14_bank)	C++17	100 / 100	172 ms	1376 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int N = 20;
bool dp[1<<N];

int main() {


	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> a = {0}, b(m);
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        a.push_back(a.back()+x);
    }
    for(int i = 0; i < m; i++) cin >> b[i];

    dp[0] = 1;
    for(int msk = 0; msk < (1<<m); msk++) {
        if (!dp[msk]) continue;
        int sum = 0;
        for(int j = 0; j < m; j++) {
            if (msk & (1<<j)) sum += b[j];
        }
        int idx = 0;
        while(idx+1 < (int)size(a) && sum >= a[idx+1]) idx++;

        if (idx == int(size(a))-1) {
            cout << "YES" << endl;
            return 0;
        }

        for(int j = 0; j < m; j++) {
            if (msk & (1<<j)) continue;
            if (sum+b[j] <= a[idx+1]) {
                dp[msk|(1<<j)] = 1;
            }
        }
    }

    cout << "NO" << endl;

    return 0;
}

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