제출 #93042

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

bank

// solved by bitmask

# include <iostream>
# include <vector>

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()
{
	ios_base::sync_with_stdio(false);
	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++){
		for(auto mask: vc[i]){
			for (int k = 0; k < m; k++){
				if((mask & (1 << k)))continue;

				int msk = mask | (1 << k);
				
				s[msk] = s[mask] + b[k];
				
				if(a[cnt[mask] + 1] == s[mask] + b[k])
					cnt[msk] = max(cnt[msk], cnt[mask] + 1);
				
				else
					cnt[msk] = max(cnt[msk], cnt[mask]);
				
				if(cnt[msk] == n){
					cout << "YES";
					exit(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