Submission #948701

#	Time	Username	Problem	Language	Result	Execution time	Memory
948701		BF001	Bank (IZhO14_bank)	C++17	100 / 100	110 ms	17192 KiB

bank

#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;
}     

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