제출 #1089292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089292		vjudge1	은행 (IZhO14_bank)	C++17	0 / 100	0 ms	348 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, string s, int need, int st, int sum = 0, int ss = 0 )
{
	if( sum > need || mp[st][ss] ) return;
	mp[st][ss] = 1;
	
	if( i == m )
	{
		if( sum != need ) return;
		v[st].push_back( ss );
		
		return;
	}
	mask( i + 1, s, need, st, sum, ss + ( s[i] == '1' ? ( 1 << i ) + 1 : ( 1 << i )));
	if( s[i] == '0' ) mask( i + 1, s, need, st, sum + b[i + 1], ss + ( 1 << i ) + 1 );
}
void rec( int i, string s )
{
	if( i > n ) 
	{
		ok = 1;
		return;
	}
	mask( 0, s, a[i], i );
	
	for( auto mas : v[i] )
	{
		string sss = "";
		int sam = mas;
		while( sam > 0 ) sss += ( sam % 2 ) + '0', sam /= 2;
		reverse( sss.begin(), sss.end() );
		
		//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: 0 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29