제출 #948701

#제출 시각아이디문제언어결과실행 시간메모리
948701BF001은행 (IZhO14_bank)C++17
100 / 100
110 ms17192 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 25
#define fi first
#define se second

typedef pair<int, int> ii;

int n, m, a[N], b[N];
ii dp[(1 << 20) + 5];

int getbit(int msk, int pos){
	return (msk >> pos) & 1;
}

int onbit(int msk, int pos){
	return (msk | (1 << pos));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
   	cin >> n >> m;
   	for (int i = 1; i <= n; i++){
   		cin >> a[i];
   	}

   	for (int i = 0; i < m; i++) cin >> b[i];

   	for (int msk = 0; msk < 1 << m; msk++){
   		int cnt = dp[msk].fi, w = dp[msk].se;
   		for (int pos = 0; pos < m; pos++){
   			if (getbit(msk, pos)) continue;
   			int nwmsk = onbit(msk, pos);
   			ii nw = {cnt, w + b[pos]};
   			if (b[pos] + w == a[cnt + 1]) nw = {cnt + 1, 0};
   			dp[nwmsk] = max(dp[nwmsk], nw);
   		}
   	}

   	int res = 0;
   	for (int msk = 0; msk < 1 << m; msk++) res = max(res, dp[msk].fi);

   	if (res == n) cout << "YES\n";
   	else cout << "NO\n";

    return 0;
}     
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...