Elearning CodePath – CTP Online Judge

SUMS

Cho một dãy gồm n số nguyên dương phân biệt a1, a2, ..., an. Xét các số có thể tạo thành bằng cách lấy tổng của một hoặc nhiều phần tử trong dãy. Mỗi phần tử chỉ có thể được sử dụng tối đa một lần trong một tổng.

Hãy viết chương trình tính toán các giá trị sau:
- Số lượng các tổng khác nhau có thể tạo thành.
- Giá trị tổng có thể được tạo thành bằng nhiều cách nhất và số cách tạo thành nó. Nếu có nhiều giá trị như vậy, hãy chọn giá trị lớn nhất trong đó.
- Dãy có tổng bằng giá trị xác định được ở trên và có thứ tự từ điển nhỏ nhất (các số sắp xếp tăng dần).

### Dữ liệu

- Dòng 1: Chứa số nguyên n (1 < n <= 70).
- Dòng 2: Chứa n số nguyên dương phân biệt a1, a2, ..., an (1 <= ai <= 1000).

### Kết quả

- Dòng 1: Số lượng các tổng khác nhau có thể tạo thành.
- Dòng 2: Hai số nguyên — tổng có nhiều cách tạo thành nhất và số cách tạo thành nó. Dữ liệu đảm bảo số cách tạo thành không vượt quá 5 * 10^18.
- Dòng 3: Dãy các số có tổng trên và có thứ tự từ điển nhỏ nhất (các số sắp xếp tăng dần).

### Ràng buộc
- Subtask 1 (30%): n <= 25.
- Subtask 2 (70%): Không có ràng buộc bổ sung (n <= 70).

### Ví dụ
Input (sums.inp):
4
1 3 4 6

Output (sums.out):
12
10 2
1 3 6

Giải thích ví dụ:
Có 12 tổng có thể tạo thành là: 1, 3, 5, 6, 8, 9, 11, 13 (và các tổng khác tương ứng).
Các tổng 4, 7, 10 đều có thể tạo thành bằng 2 cách.
Tổng lớn nhất trong đó là 10 = 1 + 3 + 6 hoặc 10 = 4 + 6. Đề bài yêu cầu chọn cách có thứ tự từ điển nhỏ nhất là {1, 3, 6}.

✅ Đã AC: 33 / 47 submissions