Submission #1128162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128162		asdfghjk	Bank (IZhO14_bank)	C++20	44 / 100	1094 ms	448 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define all(x) x.begin(), x.end()
#define con continue
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;


const ll N = 1e5 + 5;
const ll NN =   1e6 + 1e5;
const ll INF = 1e18;
const ll inf = 1e9;
const ll MOD = 1e9 + 7;
int a[N],b[N];
int n,m;
int get(int x,int y){
    if(x == 0)return 1;
    if(y == ((1 << m) - 1))return 0;
    vector <pair<int,int> > d;
    d.clear();
    ll amo = 0;
    for(int i = 0;i < m;i++){
        if(((y >> i) & 1) == 0){
            d.pb({b[i + 1],i});
            amo += b[i+ 1];
        }
    }
    for(int i = 0;i < n;i++){
        if((x >> i) & 1){
            amo -= a[i + 1];
        }
    }
    if(amo < 0)return 0;
    int res =0;
    for(int i = 0;i < n;i++){
        if((x >> i) & 1){
            for(int mask = 1;mask < (1 << int(d.size()));mask++){
                int nw = y,sum = 0;
                for(int j = 0;j < d.size();j++){
                    if((mask >> j) & 1){
                        sum += d[j].F;
                        nw = (nw | (1 << d[j].S));
                    }
                }
                if(sum == a[i + 1]){
                    res = max(res,get((x ^ (1 << i)) , nw));
                }
            }
        }
    }
    return res;
}
void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= m;i++){
        cin >> b[i];
    }
    if(n == 1){
        for(int mask = 1;mask < (1 << m);mask++){
            int sum=  0;
            for(int i = 0;i < m;i++){
                if((mask >> i) & 1){
                    sum += b[i + 1];
                }
            }
            if(sum == a[1]){
                cout << "YES\n";
                return;
            }
        }
    }
    if( get( ( (1 << n) - 1) ,0) )cout << "YES\n";
    else cout << "NO\n";
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    cout.tie(0);
    ll abd = 1;
//    cin >>abd;
//    freopen("promote.in","r",stdin);
//    freopen("promote.out","w",stdout);
    for(ll i = 1;i <= abd;i++){

        solve();
    }
}

Compilation message (stderr)

bank.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

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