Submission #1237733

#TimeUsernameProblemLanguageResultExecution timeMemory
1237733muhammadali_2009Bank (IZhO14_bank)C++20
0 / 100
7 ms16708 KiB
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+     //          

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define ll long long
#define int long long
#define all(x) x.begin(), x.end()
#define all1(x) x.rbegin(), x.rend()
#define seea(x) for(int i = 0; i < x; i++)
#define pb push_back
#define ff first
#define vc vector
#define ss second

using namespace std;  
const int mod = 1e9 + 7;

void solve() {
   int n, m; cin >> n >> m;
   vector<int>a(n), b(m);
   seea(n) cin >> a[i];
   seea(m) cin >> b[i];

   int full = 1LL << m;
   vector<int> dp(full, -1), l(full, -1);
   dp[0] = 0; l[0] = 0;

   for (int mask = 0; mask < full; ++mask) {
       int bestCov  = dp[mask];
       int bestLeft = l[mask];

       for (int j = 0; j < m; ++j) {
           if (!(mask & (1LL << j))) continue;
           int prevMask = mask ^ (1LL << j);
           int prevCov  = dp[prevMask];
           if (prevCov < 0) continue;

           int sum = l[prevMask] + b[j];
           int nc, nl;
           if (sum < a[prevCov]) {
               nc = prevCov;
               nl = sum;
           } else {
               nc = prevCov + 1;
               nl = sum - a[prevCov];
           }

           if (nc > bestCov || (nc == bestCov && nl > bestLeft)) {
               bestCov  = nc;
               bestLeft = nl;
           }
       }

       dp[mask] = bestCov;
       l[mask]  = bestLeft;

       if (dp[mask] == n) {
           cout << "YES" << endl;
           return;
       }
   }

   cout << "NO" << endl;
}

signed main(){
    fast;
    int t = 1;
    while (t--) solve();
    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...