Submission #1203273

#TimeUsernameProblemLanguageResultExecution timeMemory
1203273dungttBank (IZhO14_bank)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; int N, M; int salary[21], banknote[21]; int sumSalary[1 << 20]; bool dp[1 << 20]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> M; for (int i = 0; i < N; i++) cin >> salary[i]; for (int i = 0; i < M; i++) cin >> banknote[i]; int totalMasks = 1 << M; // Tính tổng tiền tương ứng với mỗi trạng thái bitmask vector<int> sumBanknote(totalMasks, 0); for (int mask = 0; mask < totalMasks; mask++) for (int i = 0; i < M; i++) if (mask & (1 << i)) sumBanknote[mask] += banknote[i]; // DP bottom-up dp[0] = true; // Ban đầu chưa dùng tờ tiền nào for (int mask = 0; mask < totalMasks; mask++) { if (!dp[mask]) continue; // Đếm số người đã trả lương được theo trạng thái mask int currentPaid = 0, tempSum = sumBanknote[mask]; for (int i = 0, s = 0; i < N && s < tempSum; i++) { s += salary[i]; if (s <= tempSum) currentPaid++; } if (currentPaid == N) continue; // Đã trả xong tất cả lương rồi // Thử chọn các tờ tiền còn lại để trả tiếp cho người currentPaid for (int nextMask = (totalMasks - 1) ^ mask; nextMask; nextMask = (nextMask - 1) & ((totalMasks - 1) ^ mask)) { if (sumBanknote[nextMask] == salary[currentPaid]) { dp[mask | nextMask] = true; } } } cout << (dp[totalMasks - 1] ? "YES" : "NO") << "\n"; 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...