Submission #847905

#TimeUsernameProblemLanguageResultExecution timeMemory
847905orcslopBank (IZhO14_bank)C++17
0 / 100
80 ms8828 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 20; 

int n, m; 
bool invalid[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); 
    for(int i = 0; i < (1 << m); i++){
        for(int j = 0; j < m; j++){
            if(i & (1 << j)){
                // if(invalid[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; 
                }
                else if(curr.first < n && curr.second + notes[j] == sal[curr.first]){
                    curr.first++; 
                    curr.second = 0; 
                    dp[i] = curr; 
                }
                else{
                    if(curr.first < 1e9) continue; 
                    curr = make_pair(1e9, 1e9); 
                }
            }
        }
        if(!invalid[i] && dp[i].first >= n){
            cout << "YES\n"; 
            return 0; 
        }
    }
    cout << "NO\n"; 
    return 0; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...