Submission #1089346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089346		KluydQ	Bank (IZhO14_bank)	C++17	100 / 100	669 ms	50772 KiB

bank

#include <bits/stdc++.h>
#define Shrek_Crush228 ios_base::sync_with_stdio(0), cin.tie(0);

using namespace std;

const int N = 1e5 + 123;

int a[N], b[N], l, r, n, k, m, w, sum, sum1, y, ans1, ans, x;
string s, s1;

int nt[N], taked[N];
bool ok;
vector <int> v[22];
int mp[22][N * 11];

void mask( int i, int sop, int need, int st, int sum = 0, int ss = 0 )
{
	if( sum > need ) return;
	
	if( i == m )
	{
		if( sum != need || mp[st][ss] ) return;
		mp[st][ss] = 1;
		v[st].push_back( ss );
		//cout << ss << '\n';
		
		return;
	}
	mask( i + 1, sop, need, st, sum, ss + ((( sop >> i ) & 1 ) ? ( 1 << i ) : 0 ));
	if( !(( sop >> i ) & 1 )) mask( i + 1, sop, need, st, sum + b[i + 1], ss + ( 1 << i ));
}
void rec( int i, string s )
{
	if( i > n ) 
	{
		ok = 1;
		return;
	}
	v[i].clear();
	int sop = 0;
	
	for( int bit = 0; bit < m; bit ++ )
	{
		if( s[bit] == '1' ) sop += ( 1 << bit );
	}
	mask( 0, sop, a[i], i );
	
	for( auto mas : v[i] )
	{
		string sss = "";
		int sam = mas;
		
		for( int bit = 0; bit < m; bit ++ )
		{
			if(( sam >> bit ) & 1 ) sss += '1';
			else sss += '0';
		}
		//cout << sss << ' ' << i << '\n';
		
		rec( i + 1, sss );
		if( ok ) return;
	}
}
void solve()
{
	cin >> n >> m;
	
	string nw = "";
	
	for( int i = 1; i <= n; i ++ ) cin >> a[i];
	for( int i = 1; i <= m; i ++ ) cin >> b[i], nw += '0';
	
	rec( 1, nw );
	
	if( ok ) cout << "YES\n";
	else cout << "NO\n";
}
int main() 
{
	//freopen("rmq.in", "r", stdin);
	//freopen("rmq.out", "w", stdout);
	    
    Shrek_Crush228	
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ

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