#BZOJ4850. 灯塔
-
ID: 3501
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
灯塔
No submission language available for this problem.
题目描述
JSOI的国境线上有N一座连续的山峰,其中第ii座的高度是hi??.为了简单起见,我们认为这N座山峰排成了连续一条
直线.如果在第ii座山峰上建立一座高度为p(p≥0)的灯塔,JYY发现,这座灯塔能够照亮第jj座山峰,当且仅当满足如
下不等式:hj≤hi+p-sqrt(|i-j|)JSOI国王希望对于每一座山峰,JYY都能提供建造一座能够照亮全部其他山峰的灯
塔所需要的最小高度.你能帮助JYY么?
1< N ≤ 10^5
0 < hi ≤ 10^9
输入格式
输入一行包含一个正整数N。
接下来N行，第i行包含一个正整数ℎi，表示第i座山峰的高度。
输出格式
第i行包含一个非负整数，表示在第i座山峰上修建灯塔所需要的最小高度Pi
6 5 3 2 4 2 4
2 3 5 3 5 4