P5155 [USACO18DEC] Balance Beam P

To save money to build a new stall in her barn, Bessie starts performing at a local circus, showing off her excellent balance by carefully walking back and forth on a balance beam. How much money Bessie can earn depends on the position where she finally jumps off the beam successfully. Positions on the beam from left to right are labeled $0,1,\ldots,N+1$. If Bessie reaches position $0$ or $N+1$, she will fall off the end of the beam and unfortunately receive no reward. If Bessie is at a given position $k$, she may do either of the following: 1. Toss a coin. If it lands tails up, she moves to position $k-1$; if it lands heads up, she moves to position $k+1$ (that is, each happens with probability $1/2$). 2. Jump off the beam and receive a reward of $f(k)$ ($0 \leq f(k) \leq 10^9$). Bessie realizes she cannot guarantee getting any particular reward, since her movement is controlled by the random coin tosses. However, based on her starting position, she wants to compute the expected reward she can obtain after making a sequence of optimal decisions (where “optimal” means the decisions that yield the highest possible expected reward). For example, if her strategy gives her a reward of $10$ with probability $1/2$, a reward of $8$ with probability $1/4$, and a reward of $0$ with probability $1/4$, then her expected reward is the weighted average $10 \times (1/2)+8 \times (1/4)+0 \times (1/4)=7$.

The first line of input contains $N$ ($2 \leq N \leq 10^5$). The next $N$ lines contain $f(1) \ldots f(N)$.

Output $N$ lines. On the $i$-th line, output $10^5$ times the expected reward Bessie can obtain when starting from position $i$ and using an optimal strategy, rounded down.

Translated by ChatGPT 5