Submission #1203265

#TimeUsernameProblemLanguageResultExecution timeMemory
1203265dungttBank (IZhO14_bank)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; int N, M, a[20], b[20], total[1<<20], dp[1<<20]; int main() { cin >> N >> M; for (int i=0; i<N; ++i) cin >> a[i]; for (int j=0; j<M; ++j) cin >> b[j]; int FULL = (1<<M); // Tính tổng tiền mỗi mask tờ tiền trước for (int mask=0; mask<FULL; ++mask) { total[mask] = 0; for (int j=0; j<M; ++j) if (mask & (1<<j)) total[mask] += b[j]; } fill(dp, dp+FULL, -1); dp[0] = 0; // Ban đầu chưa dùng tờ nào, trả được 0 người for (int mask=0; mask<FULL; ++mask) { if (dp[mask] == -1 || dp[mask] >= N) continue; // thử chọn thêm tập con submask để trả cho người thứ dp[mask] int remain = FULL-1-mask; for (int sub = remain; sub; sub = (sub-1)&remain) { if (total[sub] == a[dp[mask]]) { dp[mask | sub] = max(dp[mask | sub], dp[mask] + 1); } } } if (dp[FULL-1] == N) 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...