Submission #1089284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089284		vjudge1	Bank (IZhO14_bank)	C++17	71 / 100	1061 ms	2108 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;
map <string, bool> mp[22];
vector <string> v[22];

void mask( int i, string s, int need, int st, int sum = 0, string ss = "" )
{
	if( sum > need ) return;
	
	if( i == m )
	{
		if( sum != need || mp[st][ss] ) return;
		mp[st][ss] = 1;
		v[st].push_back( ss );
		
		return;
	}
	mask( i + 1, s, need, st, sum, ss + s[i] );
	if( s[i] == '0' ) mask( i + 1, s, need, st, sum + b[i + 1], ss + '1' );
}
void rec( int i, string s )
{
	if( i > n ) 
	{
		ok = 1;
		return;
	}
	mask( 0, s, a[i], i );
	
	for( auto mas : v[i] )
	{
		rec( i + 1, mas );
		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: 0 / 29