問題一覧 > 通常問題

No.1512 作文

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 187
作問者 : ぷらぷら / テスター : nok0nok0 だれだれ
6 ProblemId : 6480 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-21 23:43:55

問題文

ある文字列 $t$ について、$t$ の各文字が昇順に並んでいるとき、 $t$ を良い文字列であると呼ぶことにします。

例えばaabc,axz,空文字列などは良い文字列ですが、cba,azaなどは良い文字列ではないです。

英小文字からなる文字列が $N$ 個与えられます。

$N$ 個の文字列それぞれについて選択するか選択しないか選び、選択した文字列を好きな順番で連結して良い文字列 $X$ を作るとき、 $X$ としてありえる長さの最大値を求めてください。

入力

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

  • $N$ は整数
  • $S_i\ (1 \leq i \leq N)$ は英小文字のみからなる文字列
  • $1 \leq N \leq 200000$
  • $1 \leq |S_i| \leq 200000$
  • 一回の入力で与えられる $|S_i|$ の総和は $200000$ を超えない

    • 出力

    答えを出力し、最後に改行して下さい。

    サンプル

    サンプル1
    入力
    3
aa
ab
ba
    出力
    4

    $S_1+S_2=$aaab のとき最大になります。

    サンプル2
    入力
    3
cba
db
kji
    出力
    0

    長さが $1$ 以上の良い文字列が作れないこともあります。

    サンプル3
    入力
    4
abc
ab
bbccdd
de
    出力
    10

    abcde, abbbccddde のような文字列が考えられますが、この中で長さが最大の $10$ を出力してください。

    サンプル4
    入力
    3
ab
cd
f
    出力
    5

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。