问题 AF: 环路运输
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:327
解决:152
题目描述
在一条环形公路旁均匀地分布着N座仓库,编号为1~N,编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min(|i-j|,N-|i-j|),也就是逆时针或顺时针从 i 到 j 中较近的一种。
每座仓库都存有货物,其中编号为 i 的仓库库存量为 AiA_iAi。
在 i 和 j 两座仓库之间运送货物需要的代价为Ai+Aj+dist(i,j)
求在哪两座仓库之间运送货物需要的代价最大
每座仓库都存有货物,其中编号为 i 的仓库库存量为 AiA_iAi。
在 i 和 j 两座仓库之间运送货物需要的代价为Ai+Aj+dist(i,j)
求在哪两座仓库之间运送货物需要的代价最大
输入
第一行包含一个整数N。
第二行包含N个整数A1∼AN。
第二行包含N个整数A1∼AN。
输出
输出一个整数,表示最大代价。
样例输入 复制
5
1 8 6 2 5
样例输出 复制
15
提示
1≤N≤106,
1≤Ai≤107
1≤Ai≤107