HSG9 Bắc Giang 2025 - Chia quà

Xem dạng PDF

Gửi bài giải

Điểm: 25,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    duongminhhieu500  đã bình luận lúc 7, Tháng 11, 2026, 13:49

    include <bits/stdc++.h>

    using namespace std;

    int a[105]; int type[105]; bool dp[500005]; // Tổng tối đa S = 100 * 10000 = 10^6. Nửa tổng S/2 = 500000.

    int main() { iosbase::syncwith_stdio(0); cin.tie(0); freopen("CHIAQUA.INP", "r", stdin); freopen("CHIAQUA.OUT", "w", stdout);

    int n;
    if (cin >> n) {
        int sum_total = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum_total += a[i];
        }
    
        long long s1 = 0, s2 = 0;
        for (int i = 1; i <= n; i++) {
            cin >> type[i];
            if (type[i] == 1) s1 += a[i];
            else s2 += a[i];
        }
    
        // In ra dòng 1: Độ chênh lệch ban đầu
        cout << abs(s1 - s2) << "\n";
    
        // Tính dòng 2: Quy hoạch động tìm chênh lệch nhỏ nhất
        int half_sum = sum_total / 2;
        dp[0] = true;
    
        for (int i = 1; i <= n; i++) {
            for (int j = half_sum; j >= a[i]; j--) {
                if (dp[j - a[i]]) {
                    dp[j] = true;
                }
            }
        }
    
        int best_sum = 0;
        for (int j = half_sum; j >= 0; j--) {
            if (dp[j]) {
                best_sum = j;
                break;
            }
        }
    
        // Độ chênh lệch nhỏ nhất là: (Tổng S - best_sum) - best_sum
        cout << sum_total - 2 * best_sum << "\n";
    }
    return 0;
    

    }