1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
#include <numeric>
#include <bitset>
#include <map>
#include <algorithm>

const int MAX_SUM = 200001; // 假设 n<=200, a[i]<=1000

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 1. 统计每个数字的出现频率
    std::map<int, int> counts;
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        int num;
        std::cin >> num;
        counts[num]++;
        total_sum += num;
    }

    // 2. 二进制分组，将多重背包转化为0/1背包
    std::vector<int> new_items;
    for (auto const& [num, count] : counts) {
        int c = count;
        for (int p = 1; c > 0; p *= 2) {
            int k = std::min(p, c); // p是期望拆分的大小，c是剩余数量
            new_items.push_back(num * k);
            c -= k;
        }
    }

    // 3. 对新的物品列表执行0/1背包
    std::bitset<MAX_SUM> dp;
    dp[0] = 1;

    // 这里的循环次数从 n 减少到了 sum(log(counts[i]))
    for (int item_val : new_items) {
        dp |= (dp << item_val);
    }

    long long sum1 = 0;
    long long target = total_sum / 2;

    for (long long j = target; j >= 0; --j) {
        if (dp[j]) {
            sum1 = j;
            break;
        }
    }

    long long sum2 = total_sum - sum1;
    std::cout << sum1 * sum2 << std::endl;

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 递归函数，生成所有子集和
void generate_sums(int idx, int end_idx, long long current_sum, 
                   const std::vector<long long>& a, std::vector<long long>& sums) {
    if (idx == end_idx) {
        sums.push_back(current_sum);
        return;
    }
    // 选择不包含 a[idx]
    generate_sums(idx + 1, end_idx, current_sum, a, sums);
    // 选择包含 a[idx]
    generate_sums(idx + 1, end_idx, current_sum + a[idx], a, sums);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<long long> a(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        total_sum += a[i];
    }

    // 1. 分割数组并生成两部分的子集和
    std::vector<long long> sums1, sums2;
    int mid = n / 2;
    generate_sums(0, mid, 0, a, sums1);
    generate_sums(mid, n, 0, a, sums2);

    // 2. 对第二部分的和进行排序，为二分查找做准备
    std::sort(sums2.begin(), sums2.end());

    long long best_sum1 = 0;
    long long target = total_sum / 2;

    // 3. 遍历第一部分的和，在第二部分中寻找最佳匹配
    for (long long s1 : sums1) {
        if (s1 > target) {
            continue;
        }
        
        // 我们需要找到 sums2 中 <= (target - s1) 的最大元素
        // std::upper_bound 找到第一个 > (target - s1) 的元素
        auto it = std::upper_bound(sums2.begin(), sums2.end(), target - s1);

        // 如果 it 不是 sums2 的开头，那么它前面的那个元素就是我们要找的
        if (it != sums2.begin()) {
            it--; // 回退一个位置，得到 <= (target - s1) 的最大元素
            long long s2 = *it;
            best_sum1 = std::max(best_sum1, s1 + s2);
        } else {
            // 如果 it 是开头，说明 sums2 中没有 <= (target - s1) 的元素
            // 但我们仍然可以只从 sums1 中取 s1 (相当于 s2=0)
            // sums2 中必然包含0(空子集)，所以这种情况其实已经被上面的逻辑覆盖了
            // 为了代码严谨，我们还是可以考虑只用s1的情况
            best_sum1 = std::max(best_sum1, s1);
        }
    }

    long long sum2 = total_sum - best_sum1;
    std::cout << best_sum1 * sum2 << std::endl;

    return 0;
}