Submission #1349374

#TimeUsernameProblemLanguageResultExecution timeMemory
1349374cpismayilmmdv985Bank (IZhO14_bank)C++20
19 / 100
65 ms16708 KiB
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif

   int N, M;   cin >> N >> M;
   vector<int> A(N), B(M);
   for (auto &a : A) cin >> a;
   for (auto &b : B) cin >> b;
   vector<int64_t> dp(1 << M), rem(1 << M);
   int j = 0;
   for (int mask = 0; mask < (1 << M); mask++) {
      if (dp[mask] == N) {
         cout << "YES";
         return 0;
      }
      for (int i = 0; i < M; i++) {
         if (mask & (1 << i)) continue;
         if (rem[mask] + B[i] == A[j]) {
            debug(i);
            debug(mask);
            debug(rem[mask]); debug(B[i]);   debug(A[j]);
            dp[mask | (1 << i)] = max(dp[mask | (1 << i)], dp[mask] + 1), rem[mask | (1 << i)] = 0, j++;
            debug(mask | (1 << i));
            debug(dp[mask | (1 << i)]);
         }
         else                          rem[mask | (1 << i)] += B[i], dp[mask | (1 << i)] = max(dp[mask | (1 << i)], dp[mask]);
      }
   }
   cout << "NO";
   // for (int mask = 0; mask < (1 << M); mask++) {
   //    bitset<5> bt(mask);
   //    debug(bt);
   //    debug(dp[mask]);
   //    debug(rem[mask]);
   //    cerr << '\n';
   // }
   // cout << (dp[(1 << M) - 1] == N ? "YES" : "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...