Submission #1123278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123278		kirakosyan	Bank (IZhO14_bank)	C++17	100 / 100	142 ms	20028 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;
const ll N=1e7+5;
    // dp=vector<ll>(max(sum,(1ll<<m))+5);
long long dp[N];
void recursia(ll mask,ll i){
    if(i==-1){
        f = 1;
        return;
    }
    for(ll x:gp[a[i]]){
        
        if((x&mask)==x&&dp[x^mask]==0){
            dp[x^mask]=1;
            recursia((x^mask),i-1);
            // dp[mask]=max(dp[(x^mask)],dp[mask]);
            
        }
    }
    
}
void solve() {
    ll n,m,sum=0; cin >> n >> m;
    a=vector<ll>(n+5);
    b=vector<ll>(m+5);
    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&(1ll<<j)){
                ap+=b[j];
            }
        }
        gp[ap].push_back(i); 
    }
    for(ll i=0;i<n;i++){
        if(a[i]>sum){
            cout<<"NO"<<endl;
            return;
        }
        if(gp[a[i]].size()==0ll){
            cout<<"NO"<<endl;
            return;
        }
    }
    recursia((1ll<<m)-1,n-1);
    if(f==1)cout<<"YES";
    else cout<<"NO";
 
}
 
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: 27 / 27
• Subtask 4: 29 / 29