제출 #847906

#제출 시각아이디문제언어결과실행 시간메모리
847906orcslop은행 (IZhO14_bank)C++17
19 / 100
81 ms8528 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(dp[i].first >= n && dp[i].second < 1e8){ 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...