Submission #644891

#TimeUsernameProblemLanguageResultExecution timeMemory
644891vovamrBank (IZhO14_bank)C++17
19 / 100
22 ms18896 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } inline void solve() { int n, m; cin >> n >> m; ve<int> a(n), b(m); for (auto &i : a) cin >> i; for (auto &i : b) cin >> i; ve<ve<int>> dp(n + 1, ve<int> (1 << m)); dp[0][0] = 1; ve<int> sm(1 << m); ve<ve<int>> sums(1001); for (int ma = 1; ma < (1 << m); ++ma) { sm[ma] = sm[ma - (ma & -ma)] + b[__builtin_ctz(ma)]; if (sm[ma] > 1000) continue; sums[sm[ma]].pb(sm[ma]); } for (int i = 0; i < n; ++i) { for (int ma = 0; ma < (1 << m); ++ma) { if (!dp[i][ma]) continue; for (int &f : sums[a[i]]) { if ((ma & f) == 0) { dp[i + 1][ma | f] = 1; } } } } bool ok = 0; for (int i = 0; i < (1 << m); ++i) { ok |= dp[n][i]; } cout << (ok ? "YES" : "NO"); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...