제출 #71661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71661		istlemin	은행 (IZhO14_bank)	C++14	25 / 100	1082 ms	19168 KiB

bank

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

int main(){
	cin.sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
    vi a(n);
    vi b(m);
    rep(i,0,n) cin>>a[i];
    rep(i,0,m) cin>>b[i];

	a.push_back(0);
    vector<vector<vector<bool> > > dp(n+1,vector<vector<bool> >(1001,vector<bool>(1<<m,true)));//dp[index][left][mask];

    for(ll index = n-1;index>=0;index--){
		rep(mask,0,(1<<m))
			dp[index][0][mask] = dp[index+1][a[index+1]][mask];
        rep(left,0,1001){
            rep(mask,0,(1<<m)){
				dp[index][left][mask] = false;
				if(left==0)
					dp[index][left][mask] = dp[index+1][a[index+1]][mask];
                //cout<<index<<" "<<left<<" ";
                rep(i,0,m){
					//cout<<((mask&(1<<i))>0);
                    dp[index][left][mask] = dp[index][left][mask]||((mask&(1<<i))==0&&left>=b[i]&&dp[index][left-b[i]][mask|(1<<i)]);
                }
                //cout<<": "<<dp[index][left][mask]<<endl;
            }
        }
    }

    if(dp[0][a[0]][0]){
		cout<<"YES"<<endl;
    } else {
		cout<<"NO"<<endl;
    }
}

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