Submission #1207226

#TimeUsernameProblemLanguageResultExecution timeMemory
1207226nekolieBank (IZhO14_bank)C++20
100 / 100
118 ms5700 KiB
// When she's prettier than any DP you've ever seen... #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin >> n >> m; int a[n+1], b[m], suma[1<<m]; bool dp[1<<m], odp = false; dp[0] = true; a[0] = suma[0] = 0; for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i-1]; for (int i = 0; i < m; i++) cin >> b[i]; for (int mask = 1; mask < (1<<m); mask++) { int bit = __builtin_ctz(mask); dp[mask] = false, suma[mask] = b[bit]+suma[mask^(1<<bit)]; } for (int k = 1; k <= n; k++) { for (int mask = 0; mask < (1<<m); mask++) { if (suma[mask] < a[k-1] || suma[mask] > a[k]) continue; for (int i = 0; i < m; i++) if (mask&(1<<i)) dp[mask] = (dp[mask] || dp[mask^(1<<i)]); } for (int mask = 0; mask < (1<<m); mask++) if (suma[mask] != a[k]) dp[mask] = false; } for (int mask = 0; mask < (1<<m); mask++) odp = (odp || dp[mask]); cout << ((odp) ? "YES" : "NO") << endl; 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...