Submission #344640

#TimeUsernameProblemLanguageResultExecution timeMemory
344640maskoffBank (IZhO14_bank)C++14
25 / 100
9 ms12140 KiB
#include <bits/stdc++.h> #define file "" #define all(x) x.begin(), x.end() #define sc second #define fr first #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; const ll inf = 1e18 + 5; const ll mod = 1e9 + 7; const int N = 5e5 + 5; int dx[] = {+1, 0, -1, 0}; int dy[] = {0, +1, 0, -1}; int n, m; int a[N], b[N]; void solve2() { vector<int> all[N]; int dp[n + 5][N]; dp[0][0] = true; for (int mask = 0; mask < (1 << m); mask++) { int sum = 0; for (int i = 0; i < m; i++) if ((1 << i) & mask) sum += b[i + 1]; for (int i = 1; i <= n; i++) if (a[i] == sum) all[i].pb(mask); } for (int i = 1; i <= n; i++) { for (int j : all[i]) { for (int mask = 0; mask < (1 << m); mask++) { if (j & mask) continue; dp[i][mask ^ j] |= dp[i - 1][mask]; } } } for (int mask = 0; mask < (1 << m); mask++) if (dp[n][mask]) cout << "YES", exit(0); cout << "NO", exit(0); } void solve1() { vector<int> dp(N); dp[0] = true; for (int i = 1; i <= m; i++) { for (int w = 1000; w >= 0; w--) { dp[w + b[i]] |= dp[w]; } } if (dp[a[1]]) cout << "YES", exit(0); else cout << "NO", exit(0); } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); srand(time(nullptr)); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> b[i]; /*if (n == 1) { solve1(); } */ if (n <= 10 && m <= 10) { solve2(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...