Submission #826158

#	Time	Username	Problem	Language	Result	Execution time	Memory
826158		NhanBeoo	Bank (IZhO14_bank)	C++17	100 / 100	202 ms	22772 KiB

bank

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

#define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

const int N = 25;
int n, m, a[N], b[N], sum[1 << N];
bool vis[N][1 << N];
vi avai[N];

void dfs(int i, int state){
	if(i == n){
		cout << "YES";
		exit(0);
	}
	if(vis[i][state]) return;
	vis[i][state] = true;
	for(auto tmp: avai[i]){
		if(state & tmp) continue;
		dfs(i+1, state|tmp);
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> a[i];
	for(int i=0; i<m; i++) cin >> b[i];
	for(int state=0; state<(1<<m); state++){
		for(int i=0; i<m; i++){
			if((state & (1<<i)) == 0){
				sum[state | (1<<i)] = sum[state] + b[i];
			}
		}
		for(int i=0; i<n; i++){
			if(sum[state] == a[i]){
				avai[i].emplace_back(state);
			}
		}
		// int sum = 0;
		// for(int i=0; (1<<i)<=state; i++){
			// if(state & (1<<i)) sum += b[i];
		// }
		// for(int i=0; i<n; i++){
			// if(sum == a[i]) avai[i].emplace_back(state);
		// }
	}
	dfs(0, 0);
	cout << "NO";
} 

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