제출 #92947

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

bank

# include <iostream>
# include <vector>

# define fi first
# define se second

using namespace std;

int a[30], b[30];
int s[30000];
int n, m;
vector < pair < int, int > > vc[30000];

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 i = 1; i <= a[n]; i++){
		s[i] = s[i - 1];
		if(i == a[s[i] + 1])
			s[i]++;
	}
	
	vc[0].push_back({0, 0});
	
	for (int i = 0; i < a[n]; i++){
		
		for (size_t j = 0; j < vc[i].size(); j++){
			int mask = vc[i][j].fi;
			int cnt = vc[i][j].se;
			
			for (int k = 0; k < m; k++){
				if( mask & (1 << k) ) continue;
				int mask1 = mask | (1 << k);
				
				if(s[i + b[k]] == cnt)
					vc[i + b[k]].push_back({mask1, cnt});
				
				else if(a[s[i + b[k]]] == i + b[k] && s[i + b[k]] == cnt + 1)
					vc[i + b[k]].push_back({mask1, cnt + 1});
			}
		}
		vc[i].clear();
	}
	if(vc[a[n]].empty() == false)
		cout << "YES";
	else
		cout << "NO";
	
}
/*

1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11

*/

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