제출 #338356

#제출 시각아이디문제언어결과실행 시간메모리
338356Dilshod_Imomov은행 (IZhO14_bank)C++17
71 / 100
1065 ms748 KiB
# include <bits/stdc++.h> # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) # define int long long # define fi first # define se second using namespace std; const int N = 2e6 + 7; const int mod = 1e9 + 7; int n, m, a[23], b[23]; vector < int > vc[23]; bool dp[23][N], used[23][N]; bool rec( int i, int mask ) { if ( i < 0 ) { return 1; } int ok = 0; if ( used[i][mask] ) { return dp[i][mask]; } used[i][mask] = 1; for ( auto msk: vc[ i ] ) { if ( (mask & msk) == msk ) { int x = rec( i - 1, (mask ^ msk) ); if ( x ) { ok = 1; break; } } } dp[i][mask] = ok; return ok; } int32_t main() { speed; cin >> n >> m; for ( int i = 0; i < n; i++ ) { cin >> a[i]; } for ( int j = 0; j < m; j++ ) { cin >> b[j]; } for ( int i = 0; i < n; i++ ) { for ( int mask = 0; mask < (1 << m); mask++ ) { int sum = 0; for ( int bit = 0; bit < m; bit++ ) { if ( (mask >> bit) & 1 ) { sum += b[bit]; } } if ( sum == a[i] ) { vc[i].push_back(mask); // cout << a[i] << ' ' << mask << endl; } } } int ok = rec( n - 1, (1 << (m)) - 1 ); if ( ok ) { cout << "YES\n"; } else { cout << "NO\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...