제출 #93024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93024		Nodir_Bobiev	은행 (IZhO14_bank)	C++14	100 / 100	121 ms	13632 KiB

bank

# include <iostream>
# include <vector>

# define fi first
# define se second

using namespace std;

const int N = (1 << 21);

int n, m, a[30], b[30], s[N],cnt[N];
vector < int > vc[30];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
	}
	
	for (int i = 0; i < m; i++)
		cin >> b[i];
	
	for (int j = 0; j < (1 << m); j++)
		vc[__builtin_popcount(j)].push_back(j);
	
	for (int i = 0; i < m; i++){
		//cout << i << endl;
		for (size_t j = 0; j < vc[i].size(); j++){
			int mask = vc[i][j];
			//cout << '\t'<< mask << endl;
			for (int k = 0; k < m; k++){
				if((mask & (1 << k)))
					continue;
				int msk = mask | (1 << k);
				//cout << "\t\t" << msk << endl;
				if(a[cnt[mask] + 1] == s[mask] + b[k]){
					cnt[msk] = max(cnt[msk], cnt[mask] + 1);
					s[msk] = s[mask] + b[k];
				}
				else{
					cnt[msk] = max(cnt[msk], cnt[mask]);
					s[msk] = s[mask] + b[k];
				}
			}
		}
	}
	/*
	for (int i = 0; i < (1 << m); i++){
		cout << cnt[i] << ' ';
	}
	cout << endl;
	*/
	for (int i = 0; i < (1 << m); i++){
		if(cnt[i] == n){
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	return 0;
}
/*

1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11

*/

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