Bữa tiệc thịnh soạn
Đề bài
Mô tả
Sau cuộc đại di tản khỏi Tòa tháp của Thần, nhóm các thiếu nữ muốn ăn mừng bằng một bữa tiệc thật lớn. Và người phụ trách bữa tiệc không ai khác chính là thủ lĩnh tự phong của nhóm: Anh hùng Hameln!
Trong lúc vội vã, Hameln đã tìm được loại gia vị và lần lượt đặt chúng lên một băng chuyền dẫn thẳng vào nồi. Gia vị thứ có độ ngon là . Mải tự hào về tài nghệ khéo léo của mình, đến giây cuối cùng Hameln mới nhận ra một điều: một số gia vị có thể làm hỏng bữa tiệc! Nói cách khác, có thể âm.
Chỉ còn đúng một giây, Hameln nghĩ ra một kế hoạch tuyệt vời để cứu buổi ăn mừng:
- Đầu tiên, cô chọn hai số và () và đảo ngược đoạn băng chuyền chứa các gia vị .
- Sau đó, cô chọn một số (). Cô chỉ dùng gia vị đầu tiên và bỏ đi phần còn lại. Độ ngon của bữa tiệc là tổng độ ngon của gia vị được dùng. Lưu ý rằng nếu Hameln dùng gia vị thì độ ngon bằng .
Kế hoạch gần như ngọt ngào như bánh của Gretel, nhưng đầu óc của Hameln không sinh ra để đưa ra những quyết định này! Bạn hãy giúp cô tìm độ ngon lớn nhất của bữa tiệc nếu cô thực hiện kế hoạch một cách tối ưu.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
- Dòng đầu tiên chứa số nguyên (): số gia vị trên băng chuyền.
- Dòng thứ hai chứa số nguyên ().
Đảm bảo tổng trên tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số: độ ngon lớn nhất mà Hameln có thể đạt được cho bữa tiệc.
Ràng buộc
- .
- , tổng không vượt quá .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 1 3 5 -7 9 4 -7 -1 -4 -6 10 1 -3 5 -7 9 -11 13 -15 17 -19 |
18 0 24 |
Bộ 1: đảo đoạn , băng chuyền thành , lấy 4 gia vị đầu: . Có thể chứng minh là tốt nhất. Bộ 2: mọi gia vị đều âm nên bỏ hết, độ ngon bằng . |
| 3 3 4 5 6 5 2 -5 3 -1 4 2 -3 8 |
15 8 8 |
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: chọn (không đổi gì) và lấy cả 3 gia vị. Bộ 2: đảo đoạn thành , lấy 4 gia vị đầu. Bộ 3: đảo cả dãy thành , lấy 1 gia vị. |
Bình luận