제출 #479057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479057		fliptheswitch	은행 (IZhO14_bank)	C++14	0 / 100	1096 ms	460 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std; 
 
typedef long long ll;
 
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef tuple<int,int,int> ti;
typedef tuple<ll,ll,ll> tl;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<ti> vti;
typedef vector<tl> vtl;
 
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int>> pqg;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound


int main() {
ios::sync_with_stdio(0);
cin.tie(0);
	

    //dp[i][j] is can we give the people denoted
    //by the bit rep. of i their exact salary
    //using the bank notes denoted by the bit rep.
    //of j
    
    int n,m;
    cin>>n>>m;
    vi a(n), b(m);
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<m; i++) cin>>b[i];
    
    vector<vector<bool>> dp((1<<n), vector<bool>(1<<m, false));
    for(int i=0; i<(1<<m); i++) dp[0][i]=true;
    
    //1 bit in people
    for(int person=0; person<n; person++){
		for(int notes=1; notes<(1<<m); notes++){
			int sum=0;
			for(int mask=0; mask<m; mask++){
				if(notes & (1<<mask)) {
					sum+=b[mask];
				}
			}
			if(sum==a[person]) {
				dp[(1<<person)][notes]=true;
				//cout<<person<<" ";
				//for(int mask2=m-1; mask2>=0; mask2--){
				//	if(notes&(1<<mask2)) cout<<1;
				//	else cout<<0;
				//}
				//cout<<" "<<sum<<endl;
			}
		}
	}
	
    
    for(int people=1; people<(1<<n); people++){
        for(int notes=1; notes<(1<<m); notes++){
            int ctz = __builtin_ctz(people);
            int subPeople=(people^(1<<ctz));
            for(int subNotes=0; subNotes<=notes; subNotes++){
				bool bo=false;
				for(int mask=0; mask<m; mask++){
					if((subNotes & (1<<mask)) && !(notes & (1<<mask))) bo=true;
				}
				if(!bo) {
					if(dp[(1<<ctz)][subNotes] && dp[subPeople][(notes^subNotes)]) dp[people][notes]=true;
				}
            }
        }
    }
    

    if(dp[(1<<n)-1][(1<<m)-1]) cout<<"YES";
    else cout<<"NO";
    cout<<"\n";
    
    return 0;
}

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