|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||0||0||0||0.000%|
Wilco the tortoise wants to buy some candy. In order to do so, he will visit the Nakamise Shopping Street in Tokyo.
Tom the hare is a friend who is concerned that Wilco eats too much sugar. In order to decrease the number of candies Wilco is able to buy, Tom is going to buy some candies before him.
There are $N$ locations on the street. Each of them is either a shop or a playground for kids. The distance between adjacent locations is constant. In other words, locations can be pictured as $N$ equally spaced points on a line.
Each shop has some number of candies (possibly zero). Wilco will walk from first to last location, visiting all locations in order. Everytime he reaches a shop he will buy all available candies and put them in his bag.
Tom the hare is moving exactly twice as fast as Wilco. Contrary to Wilco, he can also move in both directions. To avoid suspicion on his mission, Tom will carry at most one candy at a time. Once he buys a candy, he will carry it until he gives it to kids on some playground. He cannot drop it anywhere else, but may drop it at some playground after Wilco has reached the final location. Tom’s goal is to minimize the number of candies Wilco is going to buy.
Both of them start at the first location at time 0. Buying and dropping candies takes no time. If at some time both of them are located on the same shop, Tom can buy candy before Wilco (although Tom is always allowed to buy at most one candy). That also means that if the first location is a shop, Tom can buy candy before Wilco at time 0.
What is the total number of candies Wilco will buy under the assumption that Tom’s movements and purchases are optimal?
The first line contains the integer $N$ from the task description.
The second line contains $N$ integers $a_1, a_2, \dots , a_N$ describing the $N$ locations on the street.
For each $i$, if $a_i$ equals -1, then the $i$-th location is a playground, otherwise it is a shop and $a_i$ specifies the number of candies in it. It is possible for a shop to have no candies (i.e. $a_i$ can be zero).
At least one location will be a playground.
Output the number of candies Wilco will buy.
$1 \le N \le 20$, $|a_i| \le 1$
$1 \le N \le 300$, $|a_i| \le 1$
$1 \le N \le 300$, $-1 \le a_i \le 10\,000$
$1 \le N \le 5\,000$, $-1 \le a_i \le 10\,000$
$1 \le N \le 500\,000$, $-1 \le a_i \le 10\,000$
5 -1 1 1 1 1
Tom goes to the shop at the second location (at that time Wilco is in-between first and second location), he buys a candy there and brings it to the playground. At the moment he reaches the playground Wilco arrives at the second location. Tom then immediately goes to the shop at the third location, arriving at the same time as Wilco. He buys a candy and brings it back to the playground. At that point Wilco is at the fourth location and Tom is not able to buy anymore candy before Wilco. So in the end Wilco buys candies at the final two shops.
8 -1 1 0 0 -1 0 0 3
Tom buys a candy at the second location and carries it to the second playground at the fifth location. He then buys a candy at the last location and brings it to the fifth location. At this point Wilco is at the sixth location. He then goes to the last location one more time and reaches just before Wilco. At that point Wilco is in-between seventh and eight location. He buys a candy there. He cannot drop this candy and buy another in time so Wilco will be able to buy a candy at last location.
8 2 -1 2 -1 2 -1 2 -1
In the beginning both Tom and Wilco are located at the first location which is a shop. Tom buys one candy before Wilco. Next, Tom drops that candy at the second location and goes to the third location, buys a candy and brings it to one of the playgrounds nearby. Then he comes back just in time as Wilco arrives at the third location so he can buy another candy before him. He brings it to the playground at the fourth location, then goes to the fifth location and buys a candy there. He drops that candy at one of the nearby playgrounds and comes back to the fifth location just in time as Wilco arrives to the fifth location so he buys another candy and brings it to playground at sixth location. He repeats the same for the last shop.