제출 #1271098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271098		nthvn	은행 (IZhO14_bank)	C++20	100 / 100	598 ms	11864 KiB

bank

#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	// Thay đổi tên file cho đúng với đề bài
	if(fopen("bank.in", "r")){
		freopen("bank.in", "r", stdin);
		freopen("bank.out", "w", stdout);
	}
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n); // Mảng lương của N người
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	vector<int> b(m); // Mảng giá trị của M tờ tiền
	for(int i = 0; i < m; ++i) {
		cin >> b[i];
	}
	
	// --- Bước 1: Tiền xử lý tính tổng của mọi tập con tờ tiền ---
	// Map một tổng tiền tới danh sách các mặt nạ bit (tập tiền) có tổng đó
	map<int, vector<int>> sum_to_masks;
	for (int mask = 0; mask < (1 << m); ++mask) {
		ll current_sum = 0;
		for (int i = 0; i < m; ++i) {
			if ((mask >> i) & 1) { // Nếu tờ tiền thứ i có trong tập
				current_sum += b[i];
			}
		}
		if (current_sum <= 1000 * 20) { // Giới hạn tổng để tránh tràn map
		    sum_to_masks[current_sum].push_back(mask);
		}
	}
	
	// --- Bước 2: Quy hoạch động ---
	// dp[mask] = mặt nạ các tờ tiền dùng để trả cho tập người trong `mask`
	// Khởi tạo dp với -1 (trạng thái không thể đạt tới)
	vector<int> dp(1 << n, -1);
	
	// Trạng thái cơ sở: không trả cho ai thì không tốn tờ tiền nào
	dp[0] = 0; 
	
	// Duyệt qua tất cả các mặt nạ của tập người
	for (int mask_nguoi = 0; mask_nguoi < (1 << n); ++mask_nguoi) {
		// Nếu trạng thái hiện tại không thể đạt tới, bỏ qua
		if (dp[mask_nguoi] == -1) {
			continue;
		}
		
		// Thử trả lương cho một người `i` chưa được trả
		for (int i = 0; i < n; ++i) {
			// Nếu người i đã có trong mask_nguoi, bỏ qua
			if ((mask_nguoi >> i) & 1) {
				continue;
			}
			
			int luong_can_tra = a[i];
			
			// Kiểm tra xem có tập tiền nào có tổng bằng luong_can_tra không
			if (sum_to_masks.count(luong_can_tra)) {
				// Duyệt qua các tập tiền có thể trả được lương này
				for (int mask_tien_tra_luong : sum_to_masks[luong_can_tra]) {
					// Kiểm tra xem tập tiền này có chung tờ nào với tập đã dùng không
					if ((dp[mask_nguoi] & mask_tien_tra_luong) == 0) {
						// Nếu không chung, ta tìm được một cách trả lương hợp lệ
						int mask_nguoi_moi = mask_nguoi | (1 << i);
						int mask_tien_moi = dp[mask_nguoi] | mask_tien_tra_luong;
						
						// Cập nhật trạng thái mới. 
						// Chỉ cần tìm được 1 cách là đủ.
						if (dp[mask_nguoi_moi] == -1) {
						    dp[mask_nguoi_moi] = mask_tien_moi;
						}
					}
				}
			}
		}
	}
	
	// --- Bước 3: Kiểm tra kết quả ---
	// Nếu dp[(1<<n) - 1] khác -1, nghĩa là có cách trả lương cho tất cả mọi người
	if (dp[(1 << n) - 1] != -1) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'int main()':
bank.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen("bank.in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 freopen("bank.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29