CCF GESP 2026年6月认证 C++ 5级
题目描述
老师正在和小朋友们分糖果。
小朋友们先在自己的手上写一个数字，然后坐成一排。
老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。
请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。
输入格式
输入 2 行，
第一行为一个正整数 $n$，表示小朋友的个数；
第二行为 $n$ 个正整数 $a_{1},a_{2},⋯,a_{n}$，表示小朋友们手上的数字，整数之间以空格分隔。
输出格式
输出一个整数，表示小朋友们可能分到的最大糖果总数量。
样例说明
样例 1
5
7 5 8 9 3111小朋友安排座位后从左向右每人手上数字依次是：9,8,7,5,3。 这时可以得到最多的糖果：(9)+(9+8)+(9+8+7)+(9+8+7+5)+(9+8+7+5+3)=111。
数据范围
$1≤n≤1000$，$1≤a_{i}≤1000$。
题目描述
小明去参加晚宴。晚宴中有 $n$ 个菜肴，每个菜肴都有一个美味度，第 $i$ 个菜肴的美味度为 $v_{i}$。
晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 1）。
请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。
输入格式
输入 2 行，
第一行为一个正整数 $n$，表示菜肴的个数；
第二行为 $n$ 个整数 $v_{1},v_{2},⋯,v_{n}$ 表示菜肴的美味度，整数之间以空格分隔。
输出格式
输出一个整数，表示两道互质菜肴美味度之和的最大值。
样例说明
样例 1
5
3 5 7 35 10538最优选择是3和35。
注意到，105与其他任意菜肴的最大公约数都大于1，因此无法参与合法选择。
数据范围
$2≤n≤1000$, $1≤v_{i}≤1000000$。
数据保证不存在相同美味度的菜肴。
数据保证至少存在一种选取两道菜肴的方案。