Submission #847907

#	Time	Username	Problem	Language	Result	Execution time	Memory
847907		orcslop	Bank (IZhO14_bank)	C++17	100 / 100	95 ms	9660 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 20; 

int n, m; 
bool valid[1 << MAXN]; 
int notes[MAXN], sal[MAXN]; 
pair<int, int> dp[1 << MAXN]; 

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m; 
    for(int i = 0; i < n; i++) cin >> sal[i]; 
    for(int i = 0; i < m; i++) cin >> notes[i]; 
    // fill(dp, dp + (1 << n), make_pair(1e9, 1e9)); 
    dp[0] = make_pair(0, 0); 
    valid[0] = true; 
    for(int i = 0; i < (1 << m); i++){
        for(int j = 0; j < m; j++){
            if(i & (1 << j)){
                if(!valid[i ^ (1 << j)]) continue; 
                pair<int, int> curr = dp[i ^ (1 << j)]; 
                if(curr.first < n && curr.second + notes[j] < sal[curr.first]){
                    curr.second += notes[j]; 
                    dp[i] = curr; 
                    valid[i] = true; 
                }
                else if(curr.first < n && curr.second + notes[j] == sal[curr.first]){
                    curr.first++; 
                    curr.second = 0; 
                    dp[i] = curr; 
                    valid[i] = true; 
                }
            }
        }
        if(valid[i] && dp[i].first >= n){
            cout << "YES\n"; 
            return 0; 
        }
    }
    cout << "NO\n"; 
    return 0; 
}

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