問題一覧 > 通常問題

No.1288 yuki collection

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 61
作問者 : chocorusk / テスター : ei1333333
お気に入りにしたユーザー ProblemId : 4975 / 自分の提出
問題文最終更新日: 2020-11-14 19:31:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 274 (順位表) の他の問題:

Problem Statement

Rusk-kun picked up a string $S$ of length $N$ consisting of the characters y, u, k, i. Each character has a fixed value, and the value of the $i$-th character from the left ($1\leq i\leq N$) is $V_i$. Rusk-kun can perform the following operation any number of times, possibly $0$.

  • Choose a (not necessarily contiguous) subsequence yuki from $S$ and remove it.
Find the maximum possible total value of the characters that can be removed.

Input

$N$
$S$
$V_1\ V_2\ \ldots\ V_N$

  • $1\leq N\leq 2000$
  • $S$ is a string of length $N$.
  • Each character of $S$ is one of y, u, k, i.
  • $1\leq V_i\leq 10^9$
  • $N$ and $V_i$ are integers.

Output

Output the maximum possible total value of the characters that can be removed when performing the operation as many times as you like.

Sample

Sample 1
Input
12
uyiyukuiikiy
2 7 1 8 2 8 1 8 2 8 4 5
Output
46

  • Remove the $4$-th, $5$-th, $6$-th, and $8$-th characters from the left. $S$ becomes uyi...u.ikiy (. represents a removed character).
  • Next, remove the $2$-nd, $4$-th, $6$-th, and $7$-th characters from the left (the $2$-nd, $7$-th, $10$-th, and $11$-th characters in the original string). $S$ becomes u.i.....i..y.
In this case, the total value of the removed characters is $V_2+V_4+V_5+V_6+V_7+V_8+V_{10}+V_{11}=46$.

Sample 2
Input
3
yui
3 2 6
Output
0

There is no subsequence yuki, so the operation cannot be performed.

Sample 3
Input
15
kyukyukyuikiiki
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Output
70

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