oj.uz

Submission #479057

# Submission time Handle Problem Language Result Execution time Memory
479057 2021-10-09T18:00:46 Z fliptheswitch Bank (IZhO14_bank) C++14
0 / 100
 1000 ms 460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 18 ms 312 KB Output is correct
4 Execution timed out 1087 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 296 KB Output is correct
2 Correct 123 ms 204 KB Output is correct
3 Correct 52 ms 204 KB Output is correct
4 Correct 263 ms 300 KB Output is correct
5 Execution timed out 1096 ms 332 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 18 ms 312 KB Output is correct
4 Execution timed out 1087 ms 204 KB Time limit exceeded
5 Halted 0 ms 0 KB -