Mì chính
Đề bài
Mô tả
MSG, tức mì chính (monosodium glutamate), ở Việt Nam còn được gọi là bột ngọt hay vị tinh, là một chất điều vị rất phổ biến trong ẩm thực Việt. MSG nổi tiếng với khả năng tạo vị umami cho các món canh, nước dùng và món xào. Nói ngắn gọn, theo lời một ông chú người Malaysia nọ, MSG là viết tắt của "Make Sh't Good". Fuiyoh!
Minh vừa mở một nhà hàng. Thực đơn của Minh gồm món ăn, món thứ thuộc loại . Một hôm, một ông chú người Malaysia ghé nhà hàng. Sau khi nếm cả món của Minh, ông lắc đầu và thốt lên: "Đồ ăn của cậu có vị như nỗi buồn. MSG đâu? MSG là vua của hương vị. Thảo nào nhà hàng của cậu trống trơn như cuộc hôn nhân của tôi. Haiyaaa…". Minh lập tức nhận ra ông chú này là cao thủ thật sự, và quyết định nghe theo lời khuyên, thêm MSG vào các món ăn.
Sau khi phân tích kỹ, Minh xác định được rằng thêm MSG vào món thứ sẽ làm độ ngon của món đó tăng thêm ( có thể âm: trái với suy nghĩ của ông chú, MSG không làm mọi thứ ngon lên). Hơn nữa, thêm MSG vào nhiều món cùng một loại thì chỉ có tác dụng với món cuối cùng của loại đó. Nói cách khác, nếu Minh thêm MSG vào các món cùng một loại, thì chỉ món được tăng độ ngon thêm , còn độ ngon của các món giữ nguyên.
Vì quá bận để tìm cách thêm MSG tối ưu, Minh quyết định chọn một đoạn khác rỗng của thực đơn và thêm MSG vào tất cả các món . Minh muốn biết tổng độ ngon tăng thêm lớn nhất có thể đạt được trong mọi đoạn . Hãy giúp Minh tìm đáp án.
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 của mỗi bộ dữ liệu chứa số nguyên (): số món trong thực đơn của Minh.
- Dòng thứ hai chứa số nguyên (): loại của các món ăn.
- Dòng thứ ba chứa số nguyên (): độ ngon tăng thêm của các món ăn.
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 duy nhất: tổng độ ngon tăng thêm lớn nhất.
Ràng buộc
- .
- ; ; .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 1 1 2 1 -2 3 4 1 2 3 4 5 6 -7 8 2 1 1 -6 -7 5 1 3 2 3 4 100 -1000000000 1 -100 100 |
3 12 -6 101 |
Bộ thứ nhất: đoạn tối ưu là với tổng . Với đoạn , món và món cùng loại nên chỉ món có tác dụng, tổng chỉ là . Bộ thứ hai: các món đôi một khác loại nên tổng của một đoạn chính là ; đoạn tối ưu là với tổng . Bộ thứ ba: mọi đoạn đều có tổng âm; vì đoạn phải khác rỗng nên đoạn tối ưu là với tổng . Bộ thứ tư: đoạn tối ưu là ; món và món cùng loại nên chỉ món có tác dụng và mức giảm rất lớn của món bị bỏ qua, tổng là . |
| 2 4 1 2 3 2 5 -9 6 -1 3 1 1 1 3 -1 2 |
10 3 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: đoạn có món bị món cùng loại thay thế, tổng là , lớn hơn mọi đoạn khác (ví dụ chỉ được ). Bộ thứ hai: mọi món cùng một loại nên tổng của đoạn luôn là ; đáp án là . |
Bình luận