Submission #1237935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237935		muhammadali_2009	Bank (IZhO14_bank)	C++20	100 / 100	75 ms	16756 KiB

bank

//              +-- -- --++-- +-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
            //shunki hammasi bir xil reslut beradi (summa bir xil (b[j] sip qilingan dp lar -1 chunki))
        }
    }
    if(dp[i] == n){
        cout << "YES" << endl;
        return;
    }
   }
   cout << "NO" << endl;
}
 
 
signed main(){
    fast;
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29