← 返回题目列表

AtCoder · abc268_f

I. 最佳串联

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你被给予 N 字符串 S_1, S_2, \ldots, S_N 由以下数字组成 1 通过 9 和角色 X.

我们将选择一个排列 P = (P_1, P_2, \ldots, P_N) of (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.

找出以下的最大可能分数 T 当 P 可以任意选择。

约束

  • 2 \leq N \leq 2 \times 10^5
  • N 是一个整数。
  • S_i 是长度至少为 1 由以下数字组成 1 通过 9 和角色 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 is 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