問題一覧 > 通常問題

No.1288 yuki collection

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : chocorusk / テスター : ei1333333
17 ProblemId : 4975 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-14 19:31:49

問題文

ラスク君は文字 y, u, k, i からなる長さ N の文字列 S を拾いました。各文字には価値が定まっており、左から i 番目 (1≤i≤N) の文字の価値は Vi です。ラスク君は次の操作を 0 回以上何回でも行うことができます。

  • S から yuki という (連続しているとは限らない) 部分列を選んで取り除く。
取り除ける文字の価値の総和としてありうる最大値を求めてください。

入力

N
S
V1 V2 … VN

  • 1≤N≤2000
  • S は長さ N の文字列である。
  • S の各文字は y, u, k, i のいずれかである。
  • 1≤Vi≤109
  • N, Vi は整数である。

出力

操作を好きなだけ行うとき、取り除ける文字の価値の総和としてありうる最大値を出力してください。

サンプル

サンプル1
入力
12
uyiyukuiikiy
2 7 1 8 2 8 1 8 2 8 4 5
出力
46

  • 左から 4, 5, 6, 8 番目の文字を取り除く。S は uyi...u.ikiy となる (. は取り除かれた文字を表す)。
  • 次に、左から 2, 4, 6, 7 番目 (元の文字列における 2, 7, 10, 11 番目) の文字を取り除く。S は u.i.....i..y となる。
このとき、取り除いた文字の価値の総和は V2+V4+V5+V6+V7+V8+V10+V11=46 です。

サンプル2
入力
3
yui
3 2 6
出力
0

yuki という部分列が存在しないので、操作を行えません。

サンプル3
入力
15
kyukyukyuikiiki
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力
70

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