Submission #1118930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118930		kirakosyan	Bank (IZhO14_bank)	C++17	44 / 100	85 ms	12448 KiB

bank

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<random>
#include<cmath>
#include<stack>
#include<map>
#include <iomanip> 
#include <queue>
#include <set>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll mod = 1e9 + 7;
ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return (((res * res) % mod) * (a % mod)) % mod;
    }
    else {
        return (res * res) % mod;
    }
}
vector<ll>a,b;
vector<vector<ll>>gp;
ll f=0;
void recursia(ll mask,ll i){
    if(i==-1){
        f = 1;
        return;
    }
    for(ll x:gp[a[i]]){
        // cout<<x<<" "<<a[i]<<endl;
        if((x&mask)==x){
            recursia((x^mask),i-1);
        }
    }
    
}
void solve() {
    ll n,m,sum=0; cin >> n >> m;
    a=vector<ll>(n);
    b=vector<ll>(m);
    for(ll i=0;i<n;i++)cin >> a[i];
    for(ll i=0;i<m;i++){
        cin >> b[i];
        sum+=b[i];
    }
    gp=vector<vector<ll>>((sum+5));
    for(ll i=1;i<(1<<m);i++){
        ll ap=0;
        for(ll j=0;j<m;j++){
            if(i&(1<<j)){
                ap+=b[j];
            }
        }
        gp[ap].push_back(i); 
    }
    for(ll i=0;i<n;i++){
        if(gp[a[i]].size()==0){
            cout<<"NO"<<endl;
            return;
        }
    }
    recursia((1<<m)-1,n-1);
    if(f==1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cin.tie(nullptr);

    ll _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}

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