Ruy băng
Đề bài
Mô tả
Jeremy có một dải ruy băng dài gồm mảnh bằng nhau, trên mỗi mảnh ghi một số nguyên; có thể mô tả dải ruy băng bằng mảng gồm số nguyên. Jeremy muốn cắt từ dải ruy băng ra một số đoạn (ít nhất một đoạn), mỗi đoạn gồm đúng mảnh liên tiếp; các đoạn không được chồng lên nhau và có thể bỏ đi một số mảnh không dùng. Độ đẹp của một đoạn là tổng các số trên các mảnh của nó.
Ví dụ với và , Jeremy có thể cắt ra , hoặc , hoặc , ... nhưng không thể cắt ra (đoạn đầu có mảnh) hay (các mảnh và không liền nhau).
Sau đó Jeremy dán các đoạn đã cắt lại với nhau, giữ nguyên thứ tự như trên dải ban đầu, và tô màu các đoạn đen hoặc trắng xen kẽ nhau (đen, trắng, đen, trắng, ... hoặc trắng, đen, trắng, đen, ...).
Giả sử Jeremy cắt ra đoạn, đoạn thứ có độ đẹp và hệ số màu , với nếu đoạn được tô trắng và nếu được tô đen. Giá trị của dải ruy băng mới là
Hãy tìm giá trị lớn nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên () là số bộ dữ liệu.
Mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa hai số nguyên và () là số mảnh của dải ruy băng và độ dài mỗi đoạn.
- Dòng thứ hai chứa số nguyên ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra giá trị lớn nhất trên một dòng.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 3 -2 -3 2 5 2 6 5 2 -5 -6 6 2 -3 1 -2 6 2 3 |
3 22 10 |
Bộ thứ nhất: lấy cả dải làm một đoạn có độ đẹp và tô đen. Bộ thứ ba: lấy hai đoạn (tô đen) và (tô trắng), bỏ các mảnh , , ; . |
| 1 4 1 5 -1 3 -2 |
11 | Lấy cả bốn mảnh, tô trắng, đen, trắng, đen: . |
Bình luận