Submission #71666

#	Time	Username	Problem	Language	Result	Execution time	Memory
71666		istlemin	Bank (IZhO14_bank)	C++14	44 / 100	391 ms	2264 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];

    if(m<=10&&n<=10){
		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;
		}
	} else if(n==1&&m<=20){
        rep(mask,0,(1<<m)){
			ll sum = 0;
			rep(i,0,m){
                if((1<<i)&mask) sum += b[i];
			}
			if(sum==a[0]){
				cout<<"YES"<<endl;
				return 0;
			}
        }
		cout<<"NO"<<endl;

	}
}

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