Submission #671846

#TimeUsernameProblemLanguageResultExecution timeMemory
671846moday_morningBank (IZhO14_bank)C++17
71 / 100
1090 ms186104 KiB
#include <bits/stdc++.h> #define int long long #define fr first #define sc second #define pb push_back using namespace std; int n, m; int a[20], b[20], sum[20], s[1 << 20]; bool c[1 << 20][21]; vector <int> v[1<<20]; void update (int i, int j) { if (c[i][j]) { return; } c[i][j]=true; for (auto x : v[i]) { update((i | (1 << x)), j); } } void solve() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; if (i > 0) { sum[i] = sum[i-1]; } sum[i] += a[i]; } for (int j = 0; j < m; j++) { cin >> b[j]; } for (int i = 0; i < (1 << m); i++) { for (int j = 0; j < m; j++) { if (i & (1 << j)) { s[i] += b[j]; } else { v[i].push_back(j); } } } update(0, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < (1 << m); j++) { int x = 0; if (i > 0) { x = sum[i-1]; } if (c[j][i] && s[j] - x == a[i]) { update(j, i+1); } else { c[j][i]=false; } } } for (int j = 0; j < (1 << m); j++) { if (c[j][n]) { cout << "YES\n"; return; } } cout << "NO\n"; } signed main() { // usaco("triangles"); ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...