Submission #1349381

#TimeUsernameProblemLanguageResultExecution timeMemory
1349381cpismayilmmdv985은행 (IZhO14_bank)C++20
100 / 100
66 ms16796 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, -1), rem(1 << M);
   dp[0] = 0;
   sort(A.rbegin(), A.rend()); // just for fun do not mind!
   for (int mask = 0; mask < (1 << M); mask++) {
      if (dp[mask] == -1)  continue;
      if (dp[mask] == N) {
         cout << "YES";
         return 0;
      }
      int curr = dp[mask];
      for (int i = 0; i < M; i++) {
         if (mask & (1 << i)) continue;
         int nxt = mask | (1 << i), total = rem[mask] + B[i];
         if (total == A[curr])      dp[nxt] = dp[mask] + 1, rem[nxt] = 0;
         else if (total < A[curr])  dp[nxt] = dp[mask], rem[nxt] = total;
         if (dp[nxt] == N) {
            cout << "YES";
            return 0;
         }
      }
   }
   cout << "NO";

   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...