CEOI 2021 - Tortoise
Xem PDFĐề bài
Chú rùa Wilco muốn mua kẹo. Để làm vậy, cậu sẽ đến phố mua sắm Nakamise ở Tokyo.
Chú thỏ Tom là một người bạn lo rằng Wilco ăn quá nhiều đường. Để giảm số kẹo Wilco có thể mua, Tom sẽ mua bớt một số viên kẹo trước cậu.
Con phố có \(N\) địa điểm. Mỗi địa điểm là một cửa hàng hoặc một sân chơi trẻ em. Khoảng cách giữa hai địa điểm kề nhau là như nhau; có thể hình dung các địa điểm là \(N\) điểm cách đều trên một đường thẳng.
Mỗi cửa hàng có một số viên kẹo, có thể bằng không. Wilco đi từ địa điểm đầu tiên đến địa điểm cuối cùng và ghé qua tất cả các địa điểm theo thứ tự. Mỗi khi đến một cửa hàng, cậu mua toàn bộ số kẹo còn lại và bỏ vào túi.
Tom di chuyển nhanh gấp đôi Wilco. Khác với Wilco, Tom có thể di chuyển theo cả hai hướng. Để tránh bị nghi ngờ, Tom chỉ mang nhiều nhất một viên kẹo tại một thời điểm. Sau khi mua một viên kẹo, Tom phải mang nó cho đến khi trao cho trẻ em tại một sân chơi. Tom không được bỏ kẹo ở nơi nào khác, nhưng có thể bỏ kẹo tại sân chơi sau khi Wilco đã đến địa điểm cuối cùng. Mục tiêu của Tom là giảm nhỏ nhất số kẹo Wilco sẽ mua.
Cả hai bắt đầu ở địa điểm đầu tiên tại thời điểm \(0\). Việc mua và bỏ kẹo không mất thời gian. Nếu cả hai cùng ở một cửa hàng tại một thời điểm, Tom có thể mua kẹo trước Wilco, nhưng Tom vẫn chỉ được mua nhiều nhất một viên. Vì vậy, nếu địa điểm đầu tiên là cửa hàng, Tom có thể mua một viên trước Wilco ngay tại thời điểm \(0\).
Giả sử Tom di chuyển và mua kẹo một cách tối ưu, tổng cộng Wilco sẽ mua bao nhiêu viên kẹo?
Dữ liệu vào
Dòng đầu tiên chứa số nguyên \(N\).
Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), mô tả \(N\) địa điểm trên phố. Nếu \(a_i=-1\), địa điểm thứ \(i\) là sân chơi. Nếu không, địa điểm đó là cửa hàng và \(a_i\) là số kẹo trong cửa hàng. Một cửa hàng có thể không có viên kẹo nào, tức là \(a_i\) có thể bằng \(0\).
Có ít nhất một địa điểm là sân chơi.
Dữ liệu ra
In số viên kẹo Wilco sẽ mua.
Chấm điểm
- Subtask 1 (8 điểm): \(1\le N\le20\), \(|a_i|\le1\).
- Subtask 2 (10 điểm): \(1\le N\le300\), \(|a_i|\le1\).
- Subtask 3 (30 điểm): \(1\le N\le300\), \(-1\le a_i\le10\,000\).
- Subtask 4 (25 điểm): \(1\le N\le5\,000\), \(-1\le a_i\le10\,000\).
- Subtask 5 (27 điểm): \(1\le N\le500\,000\), \(-1\le a_i\le10\,000\).
Ví dụ
Ví dụ 1
Input
5
-1 1 1 1 1Output
2Giải thích
Tom đi đến cửa hàng ở địa điểm thứ hai khi Wilco còn ở giữa địa điểm thứ nhất và thứ hai. Tom mua một viên kẹo tại đó rồi mang về sân chơi. Khi Tom đến sân chơi, Wilco vừa đến địa điểm thứ hai. Tom lập tức đi đến cửa hàng ở địa điểm thứ ba và đến đó cùng lúc với Wilco. Cậu mua một viên kẹo rồi mang về sân chơi. Lúc này Wilco đã ở địa điểm thứ tư và Tom không thể mua thêm viên nào trước Wilco. Cuối cùng, Wilco mua kẹo tại hai cửa hàng cuối.
Ví dụ 2
Input
8
-1 1 0 0 -1 0 0 3Output
1Giải thích
Tom mua một viên kẹo ở địa điểm thứ hai và mang đến sân chơi thứ hai ở địa điểm thứ năm. Sau đó, cậu mua một viên ở địa điểm cuối và mang về địa điểm thứ năm. Lúc này Wilco đang ở địa điểm thứ sáu. Tom lại đi đến địa điểm cuối và đến đó ngay trước Wilco; khi ấy Wilco đang ở giữa địa điểm thứ bảy và thứ tám. Tom mua thêm một viên tại đó. Cậu không còn đủ thời gian để bỏ viên này rồi mua viên khác, nên Wilco vẫn mua được một viên ở địa điểm cuối.
Ví dụ 3
Input
8
2 -1 2 -1 2 -1 2 -1Output
1Giải thích
Ban đầu, Tom và Wilco đều ở địa điểm thứ nhất, là một cửa hàng. Tom mua một viên kẹo trước Wilco. Sau đó, Tom bỏ viên kẹo ở địa điểm thứ hai, đi đến địa điểm thứ ba, mua một viên và mang đến một trong các sân chơi gần đó. Cậu quay lại đúng lúc Wilco đến địa điểm thứ ba, nên có thể mua thêm một viên trước Wilco rồi mang đến sân chơi ở địa điểm thứ tư. Tiếp theo, Tom đến địa điểm thứ năm, mua một viên, bỏ nó ở một sân chơi gần đó và quay lại đúng lúc Wilco đến địa điểm thứ năm để mua thêm một viên rồi mang đến sân chơi ở địa điểm thứ sáu. Tom lặp lại cách này với cửa hàng cuối cùng.
Kỳ thi:
- CEOI 2021 - Ngày 2 (4 Tháng 9., 2021)
Bình luận