Submission #405112

#TimeUsernameProblemLanguageResultExecution timeMemory
405112FalconBank (IZhO14_bank)C++17
71 / 100
1044 ms8164 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n), b(m); rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; sort(all(b)); vector<vector<bool>> dp(n + 1, vector<bool>(1 << m)); rep(i, 1 << m) dp[0][i] = true; vector<vector<int>> sums(1001); rep(c, 1 << m) { int s{}; rep(i, m) if(c & (1 << i)) s += b[i]; if(s <= 1000) sums[s].push_back(c); } rep1(i, n) { for(int y: sums[a[i - 1]]) { dp[i][y] = dp[i][y] || dp[i - 1][0]; int t = (1 << m) - 1 - y; for(int x{t}; x > 0; x = (x - 1) & t) dp[i][x | y] = dp[i][x | y] || dp[i - 1][x]; } } cout << (dp[n].back() ? "YES" : "NO") << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif 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...