제출 #765605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765605		HD1	은행 (IZhO14_bank)	C++14	71 / 100	208 ms	173076 KiB

bank

//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const ll MAX=1e5+10;
const ll mod=1e9+7;
const ll inf=1e18+7;
vector<ll>s;
ll A[1010],B[1010];
map<ll,vector<ll>> masks;
map<ll,vector<ll>> c;
ll dp[21][(1<<20)+1000];
ll n, m;
void prin(ll x){
    for(ll i=m-1; i>=0; i--){
        cout<<((x>>i)&1);
    }
    cout<<endl;
    return;
}
bool DP(ll i, ll mask){
    if(i<0)return 1;
    if(dp[i][mask]!=-1)return dp[i][mask];
    dp[i][mask]=0;
    for(ll x: masks[s[i]]){
        if((mask&x)==x){
            if(i==0)dp[i][mask]=1;
            dp[i][mask]=dp[i][mask] or DP(i-1,mask^x);
        }
    }
    return dp[i][mask];
}
void solve(){
    cin>>n>>m;
    memset(dp, -1, sizeof dp);
    for(ll i=0; i<n; i++){
        ll a;
        cin>>a;
        s.push_back(a);
        c[a].push_back(i);
    }
    for(ll i=0; i<m; i++){
        cin>>B[i];
    }
    sort(s.begin(),s.end());
    for(ll mask=0; mask<(1<<m); mask++){
        ll sum=0;
        for(ll j=0; j<m; j++){
            if((mask>>j)&1){
                sum+=B[j];
            }
        }
        ll pos=lower_bound(s.begin(),s.end(),sum)-s.begin();
        if(pos<n and s[pos]==sum){
            masks[s[pos]].push_back(mask);
            for(ll it : c[s[pos]]) dp[it][mask]=1;
        }
    }
    if(DP(n-1,(1<<m)-1)){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;

}
int main(){
    fastio;
    solve();
    return 0;
}

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