Submission #535854

#	Time	Username	Problem	Language	Result	Execution time	Memory
535854		ctd6969	Bank (IZhO14_bank)	C++17	46 / 100	72 ms	1376 KiB

bank

#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const ll mod = 1e9 + 7; // 500057 , 1000037 ,10000931 , 90903649 , 998244353, 109000057 , 1090000039
const ll inf = 1e18;

using pl = pair<ll,ll>;
using pi = pair<int,int>;
using vi = vector<int>; 
using vl = vector<ll>; 
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;


#define mp make_pair
#define f first
#define s second

#define foru(i,a,b) for(int i = a ; i <= b;i++)
#define ford(i,a,b) for(int i = a ; i >= b;i--)

#define psh push
#define em emplace
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << x <<" ";



// #define LOCAL 1
vl suitable[20];
bool dp[20][1<<20];
void sol(){
	int n , m;
	cin >> n >> m;
	ll a[n] , b[m];
	foru(i,0,n-1) cin >> a[i];
	foru(i,0,m-1) cin >> b[i];
	foru(i,1,(1<<m) - 1){
		int total = 0;
		foru(j,0,m-1){
			if ( (i>>j)&1 ) total += b[j];
		}
		foru(k,0,n-1){
			if(total == a[k]) suitable[k].eb(i);
		}
	}
	bool ans = 0;
	for(int mask : suitable[0]){
		dp[0][mask] = 1;
	}
	if(n == 1){
		if(suitable[0].size() > 0) ans = 1;
	}
	foru(i,1,n-1){
		foru(j,0,(1<<m)-1){
			for(int mask : suitable[i]){
				if(__builtin_popcount(j) <= __builtin_popcount(mask) ) continue;
				dp[i][j]|=dp[i-1][j^mask];
			}
			if(i == n - 1) ans|=dp[i][j];
		}
	}
	if(ans) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}


int main(void){

	#ifdef LOCAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		auto start_time = chrono::high_resolution_clock::now();
	#endif 

	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	sol();



	#ifdef LOCAL
		auto end_time = chrono::high_resolution_clock::now();
		double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
		cout << "\n[ " << duration << " ms ]\n";
	#endif

}

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