Submission #928027

#	Time	Username	Problem	Language	Result	Execution time	Memory
928027		mariamp1	Bank (IZhO14_bank)	C++14	100 / 100	151 ms	4684 KiB

bank

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int mod = 1e9 + 7;
int dp[(1<<21)];
int main(){
    int n, m; cin >> n >> m;
    int mas[n];
    int pref[n];
    for(int i = 0; i < n; i++){
        cin >> mas[i];
    }
    pref[0] = mas[0];
    for(int i = 1; i < n; i++){
        pref[i] = pref[i-1] + mas[i];
    }
    int kup[m];
    for(int i = 0; i < m; i++){
        cin >> kup[i];
    }
    for(int i = 0; i < (1 << m); i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            if((1 << j) & i) {
                sum += kup[j];
            }   
        }

        for(int j = 0; j < m; j++){
            if((1 << j) & i) {
                if(sum == pref[dp[i - (1 << j)]])
                    dp[i] = max(dp[i], dp[i - (1 << j)] + 1);
                else dp[i] = max(dp[i], dp[i - (1 << j)]);
            }   
        }
    }
    if(dp[(1 << m) - 1] == n) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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