Submission #485422

#	Time	Username	Problem	Language	Result	Execution time	Memory
485422		danielliu04	Bank (IZhO14_bank)	C++17	100 / 100	119 ms	8516 KiB

bank

// Link: https://cses.fi/problemset/task/2181

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define lc (node<<1)+1
#define rc (node<<1)+2
#define endl '\n'
#define INF 1e9

const int max_n = 20;

int n, m;

int ppl[max_n];
int notes[max_n];

pair<int, int> dp[(1 << max_n)];

int main() {
	
	cin.tie(0);
    ios::sync_with_stdio(0);    
	
    cin >> n >> m;

    for(int i = 0; i < n; i ++){
        cin >> ppl[i];
    }

    for(int i = 0; i < m; i ++){
        cin >> notes[i];
    }

    // maximum possible value is {n, 0};
    for(int i = 0; i < (1 << m); i ++){
        dp[i] = {0, 0};
    }

    for(int i = 0; i < (1 << m) - 1; i ++){

        int current = dp[i].first;
        int curr_w = dp[i].second;

        for(int j = 0; j < m; j ++){

            if((1 << j) & i) continue;

            if(current == n) dp[i | (1 << j)] = {n, 0};
            else{
                if(curr_w + notes[j] == ppl[current]){
                    dp[i | (1 << j)] = max(dp[i | (1 << j)], {current + 1, 0});
                }
                else if(curr_w + notes[j] < ppl[current]){
                    dp[i | (1 << j)] = max(dp[i | (1 << j)], {current, curr_w + notes[j]});
                }   
                else{
                    dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i]);
                }
            }
        }
    }

    if(dp[(1 << m) - 1].first == n) cout << "YES" << endl;
    else cout << "NO" << endl;

}

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