A6317 | $「JSOI2016」灯塔$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

JSOI 的国境线上有 $N$ 座连续的山峰,其中第 $i$ 座的高度是 $h_i$​​。为了简单起见,我们认为这 $N$ 座山峰排成了连续一条直线。 山峰与灯塔高度均为非负整数。如果在第 $i$ 座山峰上建立一座高度为 $p\ (p \geq 0)$ 的灯塔，JYY 发现,这座灯塔能够照亮第 $j$ 座山峰,当且仅当满足如下不等式： $$h_j \leq h_i+p-\sqrt{|i−j|}$$ JSOI国王希望对于每一座山峰，JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么？

输入第一行为一个整数 $N$，代表山峰的数目。 接下来 $N$ 行，每行一个数 $h_i$，代表第 $i$ 座山峰的高度是 $h_i$。

输出 $N$ 行，表示每座山峰需要建造的灯塔高度 $p_i$。

输入 #1

输出 #1

C++ 编辑器

输入

输出