#P13322. [2025年队测]孙子兵法

    ID: 12506 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-线性 DP状态维度消除前后缀状态分解耐心排序求 LIS懒标记线段树有序集合

[2025年队测]孙子兵法

题目描述

wshcl 和 ET-G 分别带领一支队伍。nn 个人依次上场,他们的战力值 p1,p2,…,pnp_1,p_2,\ldots,p_n 构成 1,2,…,n1,2,\ldots,n 的一个排列。每个人必须分配到其中一支队伍。

  • 分配到 wshcl 队伍的人,若其战力值大于该队此前所有上场者的战力值,就对敌方造成一点伤害。
  • 分配到 ET-G 队伍的人,若其战力值小于该队此前所有上场者的战力值,就对敌方造成一点伤害。

每支队伍的首位上场者满足该队的条件。求在所有分配方案中,两支队伍合计能造成的最大伤害。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,依次表示各人的战力值。

输出格式

输出一行一个整数,表示最大总伤害。

样例

3
1 2 3
3
5
4 1 2 3 5
5

战力值为 1,2,3,51,2,3,5 的人分配给 wshcl,战力值为 44 的人分配给 ET-G,两队分别造成 44 和 11 点伤害。

6
4 2 5 1 6 3
5

战力值为 2,5,6,32,5,6,3 的人分配给 wshcl,战力值为 4,14,1 的人分配给 ET-G,两队分别造成 33 和 22 点伤害。

10
3 8 10 4 1 2 7 9 5 6
6

战力值为 3,8,4,1,2,93,8,4,1,2,9 的人分配给 wshcl,战力值为 10,7,5,610,7,5,6 的人分配给 ET-G,两队各造成 33 点伤害。

原题的样例 5 另见赛时选手目录 shung/shung5.in 与 shung/shung5.ans。

数据范围

对于全部数据,2≤n≤2×1052\le n\le2\times10^5,p1,p2,…,pnp_1,p_2,\ldots,p_n 是 1,2,…,n1,2,\ldots,n 的一个排列。

测试点 nn 的上限 特殊性质
1~2 1616 无
3~6 200200
7~13 20002000
14~16 10410^4
17~18 10510^5 排列随机
19~20 最长下降子序列长度不超过 22
21~23 无
24~25 2×1052\times10^5

原题 PDF