Submission #1230082

#TimeUsernameProblemLanguageResultExecution timeMemory
1230082AmaarsaaBank (IZhO14_bank)C++20
100 / 100
350 ms205620 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll INF = 1e9;
vector < vector < ll > > dp(1048576, vector < ll > (21,INF));
int main() {
	ll n, m, r, x, y, i, j, s,sum, ans, t;
	
	cin >> n >> m;
	
	ll a[n + 2], b[m + 2];
	
	s = 0;
	for (i = 0; i < n; i ++) {
		cin >> a[i];
	}
	
	for (i = 0; i < m; i ++) {
		cin >> b[i];
	}
	dp[0][0] = a[0];
	ans = 0;
	// dp[mask][i] = mask-aar ehnii i-iig zaadalhad uldsen mungu
	for (i = 0; i < (1<< m); i ++) {
		sum = 0;
		for (j = 0; j < m; j++) {
			r = i& (1<< j);
			if (r ) {
				s = i ^ (1<< j);
				for ( r =0; r < n; r ++) {
					if( dp[s][r] - b[j] >= 0 && dp[s][r] != INF) {
						dp[i][r] = dp[s][r] - b[j];
						if ( dp[s][r] - b[j] == 0 ) {
							if ( r + 1 < n) dp[i][r + 1] =a[r + 1];
							else ans = 1;
						}
					}
				}
			}
		}
	}
	if ( ans) cout << "YES" << endl;
	else cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...