AT_jsc2024_final_d.Max of Sum of Prefix Min

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于数列 $a=(a_1,a_2,\cdots,a_k)$ ，定义 $f(a)$ 如下：

$f(a)=\sum_{1 \leq i \leq k} \min(a_1,a_2,\cdots,a_i)$

给定一个长度为 $N$ 的整数数列 $A=(A_1,A_2,\cdots,A_N)$ 。

请将整数数列 $A$ 分成两个（不一定连续）（可以为空）子序列，分别记为 $X_1, X_2$ 。分割时， $A$ 的每个元素必须恰好属于一个子序列。求 $f(X_1)+f(X_2)$ 的可能最大值。

输入格式

输入按以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出答案。

输入输出样例

输入#1
```
6
5 3 6 1 4 7
```
输出#1
```
23
```
输入#2
```
10
22 7 20 26 1 11 7 1 15 10
```
输出#2
```
104
```

输入#3

15
140039457 164832983 239276621 245532751 274195604 320064892 499774361 419370025 249168130 521915711 744280520 561032101 857077284 543856068 910500852

输出#3

4618736183

输入#4

20
596982638 713892371 987307025 722757772 759622047 853214705 628902494 623807668 755031424 486834509 272961036 423817262 434140395 284114341 88860862 222135106 69837030 210989591 225447688 86416231

输出#4

9047041486

说明/提示

样例解释 1

例如，将 $X_1 = (5,3,1), X_2 = (6,4,7)$ 这样分割，则 $f(X_1)+f(X_2)=9+14=23$ 。因为无法获得比 $23$ 更大的值，所以这个答案是最优的。

数据范围

$1 \leq N \leq 500000$
$1 \leq A_i \leq 10^9$
输入的所有数都是整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页