102685: [AtCoder]ABC268 F - Best Concatenation

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

You are given $N$ strings $S_1, S_2, \ldots, S_N$ consisting of digits from 1 through 9 and the character X.

We will choose a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ to construct a string $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$, where $+$ denotes a concatenation of strings.

Then, we will calculate the "score" of the string $T = T_1T_2\ldots T_{|T|}$ (where $|T|$ denotes the length of $T$).
The score is calculated by the following $9$ steps, starting from the initial score $0$:

  • Add $1$ point to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 1.
  • Add $2$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 2.
  • Add $3$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 3.
  • $\cdots$
  • Add $9$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 9.

Find the maximum possible score of $T$ when $P$ can be chosen arbitrarily.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $N$ is an integer.
  • $S_i$ is a string of length at least $1$ consisting of digits from 1 through 9 and the character X.
  • The sum of lengths of $S_1, S_2, \ldots, S_N$ is at most $2 \times 10^5$.

Input

Input is given from Standard Input in the following format:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print the answer.


Sample Input 1

3
1X3
59
XXX

Sample Output 1

71

When $P = (3, 1, 2)$, we have $T = S_3 + S_1 + S_2 = $ XXX1X359. Then, the score of $T$ is calculated as follows:

  • there are $3$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 1;
  • there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 3;
  • there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 5;
  • there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i = $ X, and $T_j = $ 9.

Therefore, the score of $T$ is $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$, which is the maximum possible value.


Sample Input 2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

Sample Output 2

3010

Input

题意翻译

给定 $ n $ 个由 `X` 和数字构成的字符串,你需要对其进行排列并拼接成新的字符串 $ T $ 以最大化其分数。定义其分数为对于字符串中每一个数字,使数字对应的数值乘上其之前 `X` 的数量,并求和。输出分数最大值。

Output

得分:$500$分

问题描述

给你 $N$ 个由数字从 19 以及字符 X 组成的字符串 $S_1, S_2, \ldots, S_N$。

我们将选择一个排列 $P = (P_1, P_2, \ldots, P_N)$,其中 $(1, 2, \ldots, N)$ 是一个排列,来构造一个字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$,其中 $+$ 表示字符串的连接。

然后,我们将计算字符串 $T = T_1T_2\ldots T_{|T|}$(其中 $|T|$ 表示 $T$ 的长度)的“得分”。
得分是通过以下 $9$ 步计算的,从初始得分 $0$ 开始:

  • 将 $1$ 分加到得分上,次数等于 $(i, j)$ 整数对的数量,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 1
  • 将 $2$ 分加到得分上,次数等于 $(i, j)$ 整数对的数量,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 2
  • 将 $3$ 分加到得分上,次数等于 $(i, j)$ 整数对的数量,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 3
  • $\cdots$
  • 将 $9$ 分加到得分上,次数等于 $(i, j)$ 整数对的数量,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 9

当 $P$ 可以任意选择时,找出 $T$ 的最大可能得分。

约束条件

  • $2 \leq N \leq 2 \times 10^5$
  • $N$ 是一个整数。
  • $S_i$ 是一个长度至少为 $1$ 的字符串,由数字从 19 和字符 X 组成。
  • $S_1, S_2, \ldots, S_N$ 的长度之和最多为 $2 \times 10^5$。

输入

输入从标准输入中给出,格式如下:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印答案。


样例输入 1

3
1X3
59
XXX

样例输出 1

71

当 $P = (3, 1, 2)$ 时,我们有 $T = S_3 + S_1 + S_2 = $ XXX1X359。 然后,$T$ 的得分为以下计算结果:

  • 有 $3$ 个整数对 $(i, j)$,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 1
  • 有 $4$ 个整数对 $(i, j)$,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 3
  • 有 $4$ 个整数对 $(i, j)$,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 5
  • 有 $4$ 个整数对 $(i, j)$,其中 $1 \leq i \lt j \leq |T|$, $T_i = $ X,并且 $T_j = $ 9

因此,$T$ 的得分为 $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$,这是最大可能值。


样例输入 2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

样例输出 2

3010

加入题单

上一题 下一题 算法标签: