제출 #1237788

#제출 시각아이디문제언어결과실행 시간메모리
1237788muhammadali_2009은행 (IZhO14_bank)C++20
100 / 100
74 ms16712 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];
   vector<int>dp(1ll << m, -1), l(1ll << m, -1);
   dp[0] = 0; l[0] = 0;
   for(int i = 0; i < (1ll << m); i ++){
    for(int j = 0; j < m; j ++){
        if((1ll << j) & i){
            int prev = dp[(1ll << j) ^ i];
            if(prev == -1)continue;
            int sum = b[j] + l[(1ll << j) ^ i];
            if(sum < a[dp[(1ll << j) ^ i]]){
                dp[i] = dp[(1ll << j) ^ i];
                l[i] = sum;
                break;
            }
            else if(sum == a[dp[(1ll << j) ^ i]]){
                dp[i] = dp[(1ll << j) ^ i] + 1;
                l[i] = 0;
                break;
            }

            // else why not pick b[j] ? chunki u xolat boshqa maskda koriladi
            //why update dp[i] in every suitable j
        }
    }
    if(dp[i] == n){
        cout << "YES" << endl;
        return;
    }
   }
   cout << "NO" << endl;
}
 
 
signed main(){
    fast;
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...