multiset

Luogu
IDLGP9160
Time1000ms
Memory128MB
DifficultyP2
O2优化
给定一个 **多重集合**(集合中元素可重复)$S$,请求出一个最大的多重集合 $T$,满足 $T$ 是 $S$ 的一个 **真子集**,且对于 $T$ 中的每一个元素 $i$,要么 $i$ 在 $S$ 中没有前驱,要么 $i$ 在 $S$ 中的前驱 $\in T$。若有多个大小相同的集合满足条件,则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。 --- 一个数 $x$ 在一个集合 $S$ 中的前驱的定义为所有在 $S$ 中且 $<x$ 的元素 $y$ 的最大值。 ## Input 第一行一个正整数 $n$,表示 $S$ 的大小。 第二行 $n$ 个正整数,表示 $S$ 中的元素。 ## Output 一行两个整数。第一个数表示 $T$ 的大小,第二个数表示 $T$ 的所有元素之和。 [samples] ## Background ZHY 有很多集合。集合多了,也就成了多重集合。 ## Note **样例 $1$ 解释** $T$ 为 $\{5,1,4\}$。 **样例 $2$ 解释** $T$ 为 $\{1,4,2,5,7\}$。 ### 数据范围 对于 $30\%$ 的数据,$n \le 15$。 对于 $100\%$ 的数据,$2 \le n \le 10^5$,$1 \le S$ 中的元素 $\le 10^9$。
Samples
Input #1
4
4 5 1 4
Output #1
3 10
Input #2
6
1 4 2 8 5 7
Output #2
5 19
API Response (JSON)
{
  "problem": {
    "name": "multiset",
    "description": {
      "content": "给定一个 **多重集合**(集合中元素可重复)$S$,请求出一个最大的多重集合 $T$,满足 $T$ 是 $S$ 的一个 **真子集**,且对于 $T$ 中的每一个元素 $i$,要么 $i$ 在 $S$ 中没有前驱,要么 $i$ 在 $S$ 中的前驱 $\\in T$。若有多个大小相同的集合满足条件,则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。 --- 一个数 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9160"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 **多重集合**(集合中元素可重复)$S$,请求出一个最大的多重集合 $T$,满足 $T$ 是 $S$ 的一个 **真子集**,且对于 $T$ 中的每一个元素 $i$,要么 $i$ 在 $S$ 中没有前驱,要么 $i$ 在 $S$ 中的前驱 $\\in T$。若有多个大小相同的集合满足条件,则 $T$ 为所有元素之和最大的一个。请输出 $T$ 的大小和其中元素之和。\n\n---\n\n一个数 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments