Submission #92950

#	Time	Username	Problem	Language	Result	Execution time	Memory
92950		Nodir_Bobiev	Bank (IZhO14_bank)	C++14	52 / 100	1092 ms	16760 KiB

bank

# include <iostream>
# include <vector>
# include <set>

# define fi first
# define se second

using namespace std;

int a[30], b[30];
int s[30000];
int n, m;
set < 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].insert({0, 0});
	
	for (int i = 0; i < a[n]; i++){
		
		for (auto c:vc[i]){
			int mask = c.fi;
			int cnt = c.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]].insert({mask1, cnt});
				
				else if(a[s[i + b[k]]] == i + b[k] && s[i + b[k]] == cnt + 1)
					vc[i + b[k]].insert({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: 27 / 27
• Subtask 4: 0 / 29