A72038. 条形蛋糕
编程题
入门
知识点
题目描述
有一条长度为 n 的条形蛋糕。已知长度为 i 的蛋糕可以卖出价格 p_i。你可以把蛋糕切成若干段,每段长度为正整数,切割次数不限。请问这条长度为 n 的蛋糕最多能卖多少钱。
输入格式
第一行一个整数 n。
第二行 n 个正整数 p_1,p_2,\ldots,p_n,表示不同长度蛋糕的价格。
输出格式
输出一个整数,表示最大总价格。
输入输出样例
输入 #1
4 1 5 8 9
输出 #1
10
输入 #2
10 1 5 8 9 10 17 17 20 24 30
输出 #2
30
说明/提示
数据范围
1 \le n \le 10^3,1 \le p_i \le 10^5。