제출 #1118978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118978		kirakosyan	은행 (IZhO14_bank)	C++17	71 / 100	1068 ms	20808 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,dp;
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(dp[mask]){
            // cout<<"STE"<<endl;
            f=1;
            continue;
        }
        if((x&mask)==x){
            recursia((x^mask),i-1);
            // dp[(x^mask)]=1;
            
        }
    }
    
}
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));
    dp=vector<ll>(max(sum,(1ll<<m))+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"<<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: 27 / 27
• Subtask 4: 0 / 29