Submission #937933

#TimeUsernameProblemLanguageResultExecution timeMemory
937933ibroshBank (IZhO14_bank)C++17
100 / 100
94 ms8796 KiB
// #pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long

using namespace std;
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}

#define du long double
#define m_p make_pair
#define pb push_back
#define pii pair<int,int>
#define piii pair<pii,int>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<pair<int,pii> >
#define si set<int>
#define sii multiset<pii>
#define siii set<pair<int,pii> >
#define F first
#define S second
#define pre precision
#define sz size()
#define all(x) x.begin(),x.end()
#ifndef ONLINE_JUDGE
#define OK  cout << __LINE__ << "| "<< "---------------------------OK-----------------------" << endl;
#define deb(x) cout << __LINE__ << "| "<< #x  << " = " << x << endl;
#else
#define OK  
#define deb(x) 
#endif
#define nl cout<<'\n'
#define OPEN  freopen ("exam.in","r" , stdin), freopen ("exam.out","w",stdout)
const ll mod=1e9+7;
const ll inf=1e18;
const du PI=3.14;
const int N=21;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int a[23],b[23];
int ans[N];
pair <int,int> dp[(1<<21)+9];
void Teemka_abi(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int j=1;j<=m;j++){
		cin>>b[j];
	}
	for(int mask=0;mask<(1<<m);mask++){
		for(int j=0;j<m;j++){
			if(mask & (1 << j)){
				int k=dp[mask^(1<<j)].F;
				int smn=dp[mask^(1<<j)].S+b[j+1];
				if(smn==a[k+1]){
					smn=0;
					k++;
				}
				if(dp[mask].F<k){
					dp[mask]={k,smn};
				}
				else if(dp[mask].F==k){
					dp[mask] = {k,smn};
				}
			}
		}
		if(dp[mask].F==n){
			cout<<"YES";
			return;
		}
	}
	cout<<"NO";
	
}
signed main(){
	ios_base::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0); 
	// OPEN;	
	int tt=1;
	// cin>>tt;
	while(tt--){
		Teemka_abi();
		cout<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...