Thổi bóng bay
Đề bài
Mô tả
Trong kỳ thi ICPC, mỗi bài có một màu bóng bay riêng: bài A có thể là màu đỏ, bài B màu xanh dương, bài C màu vàng, v.v. Mỗi khi một đội giải được một bài, một tình nguyện viên sẽ đến khu bóng bay lấy quả bóng màu đó và mang nhanh tới bàn của đội. Hôm nay khu bóng bay do Paul điều phối. Khu của anh đã có sẵn nhiều quả bóng: một số đã được thổi một phần từ khâu chuẩn bị trước đó, số khác vẫn còn xẹp và đang chờ được thổi. Có quả bóng, đánh số từ đến . Ban đầu quả bóng thứ chứa lít không khí. Dựa vào kinh nghiệm, Paul ước lượng được khi nào mỗi quả bóng sẽ cần dùng: quả bóng thứ sẽ được mang đi sau giây kể từ khi bắt đầu kỳ thi.
Kỳ thi vừa bắt đầu, và Paul có thể bắt đầu thổi ngay. Trong mỗi giây, anh có thể thổi đúng lít không khí vào đúng một quả bóng. Vì quả bóng thứ được mang đi sau giây kể từ khi bắt đầu, nó chỉ có thể được thổi ở các thời điểm trước giây (không tính thời điểm ). Khi một quả bóng đã được mang đi, nó không thể được thổi thêm.
Paul muốn bóng thật to vì chúng giúp ảnh chụp đẹp hơn và các đội vui hơn. Anh định nghĩa điểm đẹp của một quả bóng là bình phương lượng không khí cuối cùng của nó (tính bằng lít). Nói cách khác, nếu lượng không khí cuối cùng của một quả bóng là lít thì điểm đẹp của nó bằng . Với mỗi quả bóng, lượng không khí cuối cùng bằng lượng không khí ban đầu cộng với lượng Paul thổi vào trước khi nó được mang đi. Tổng điểm đẹp là tổng điểm đẹp của tất cả các quả bóng.
Nhiệm vụ của bạn là giúp Paul phân bổ việc thổi theo thời gian sao cho tổng điểm đẹp lớn nhất có thể.
Dữ liệu vào
Mỗi file dữ liệu 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ố quả bóng.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (; ), lần lượt là thời điểm mang đi (số giây kể từ khi bắt đầu kỳ thi) và lượng không khí ban đầu (lít) của quả bóng thứ .
Dữ liệu đảm bảo tổng qua 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ố nguyên là tổng điểm đẹp lớn nhất.
Ràng buộc
- .
- , tổng không vượt quá .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 3 2 1 4 2 3 2 5 0 1 3 |
50 34 |
Bộ thứ nhất, một cách tối ưu: thổi quả bóng trong giây (thêm lít), rồi thổi quả bóng trong giây (thêm lít). Lượng không khí cuối cùng là , tổng điểm đẹp là . Có thể chứng minh không có cách nào cho tổng lớn hơn. |
| 1 4 2 10 3 9 7 0 7 4 |
308 | Ví dụ bổ sung (không có trong đề gốc). Thổi quả bóng trong giây đầu (thành lít), rồi thổi quả bóng trong giây còn lại (thành lít): . |
Bình luận