Skip to content
Sign in

白色光 2 (White Light 2)

Unrated
日本語

Language

Contribute a translation
Time limit
1000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

\(N\) 個のライトが横一列に並んでおり，左から順に \(1\) から \(N\) までの番号が付けられている．それぞれのライトの色は赤，緑，青のいずれかである．ライトの色は文字列 \(S\) によって表され，ライト \(i\) (\(1 \leqq i \leqq N\)) の色は，\(S\) の \(i\) 文字目が R のとき赤，G のとき緑，B のとき青である．最初すべてのライトは点灯している．

JOI 君は点灯しているライトが \(1\) つ以上ある限り，以下の \(3\) 種類の操作を好きな順番で好きな回数行うことができる．操作を \(1\) 回も行わなくても構わない．

  • \(A\) 円を払って点灯しているライトの中で最も左にあるものを消灯する．
  • \(B\) 円を払って点灯しているライトの中で最も右にあるものを消灯する．
  • \(C\) 円を払って点灯しているライトを \(1\) つ選び，好きな色へ点灯し直す．

JOI 君は，遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい．そのためには，点灯しているライトを左から見たときの色の並びが RGBRGB...RGB のように RGB（赤緑青）の繰り返しになっている必要がある．ただし，\(1\) つも点灯しているライトが存在しない場合も RGB の繰り返しであるとみなす． GBRGBR や RGBRG などの色の並びは条件を満たさないことに注意せよ．

ライトと操作に必要な金額の情報が与えられたとき，点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を求めるプログラムを作成せよ．

Constraints

  • \(1 \leqq N \leqq 200\,000\)．
  • \(S\) は長さ \(N\) の文字列である．
  • \(S\) の各文字は R，G，B のいずれかである．
  • \(1 \leqq A \leqq 10^9\)．
  • \(1 \leqq B \leqq 10^9\)．
  • \(1 \leqq C \leqq 10^9\)．
  • \(N, A, B, C\) は整数である．

Subtasks

  1. (\(4\) 点) \(N = 3\)．
  2. (\(22\) 点) \(N \leqq 300\)．
  3. (\(19\) 点) \(N \leqq 10\,000\)．
  4. (\(9\) 点) \(N\) は \(3\) の倍数，\(A = 10^9\)，\(B = 10^9\)，\(C = 1\)．
  5. (\(10\) 点) \(A = 10^9\)，\(B = 10^9\)，\(C = 1\)．
  6. (\(36\) 点) 追加の制約はない．

Input

入力は以下の形式で与えられる．

\(N\)
\(S\)
\(A\) \(B\) \(C\)

Output

点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を，単位 (円) を省いて \(1\) 行で出力せよ．

Examples

Sample input 1
6
GRBBRG
3 4 5
Sample output 1
16

例えば以下のように \(4\) 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

  1. \(3\) 円を払って点灯しているライトのうち最も左にあるライト \(1\) を消灯させる．それぞれのライトの状態は文字列 -RBBRG で表される．
  2. \(4\) 円を払って点灯しているライトのうち最も右にあるライト \(6\) を消灯させる．それぞれのライトの状態は文字列 -RBBR- で表される．
  3. \(4\) 円を払って点灯しているライトのうち最も右にあるライト \(5\) を消灯させる．それぞれのライトの状態は文字列 -RBB-- で表される．
  4. \(5\) 円を払ってライト \(3\) を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 -RGB-- で表される．

\(16\) 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，\(16\) を出力する．

この入力例は小課題 \(2,3,6\) の制約を満たす．

Sample input 2
3
BRG
1000000000 1000000000 1
Sample output 2
3

例えば以下のように \(3\) 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

  1. \(1\) 円を払ってライト \(2\) を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 BGG で表される．
  2. \(1\) 円を払ってライト \(3\) を選び，青色へ点灯し直す．それぞれのライトの状態は文字列 BGB で表される．
  3. \(1\) 円を払ってライト \(1\) を選び，赤色へ点灯し直す．それぞれのライトの状態は文字列 RGB で表される．

\(3\) 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，\(3\) を出力する．

この入力例は小課題 \(1,2,3,4,5,6\) の制約を満たす．

Sample input 3
3
GRB
9 11 14
Sample output 3
27

例えば以下のように \(3\) 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

  1. \(9\) 円を払って点灯しているライトのうち最も左にあるライト \(1\) を消灯させる．それぞれのライトの状態は文字列 -RB で表される．
  2. \(9\) 円を払って点灯しているライトのうち最も左にあるライト \(2\) を消灯させる．それぞれのライトの状態は文字列 --B で表される．
  3. \(9\) 円を払って点灯しているライトのうち最も左にあるライト \(3\) を消灯させる．それぞれのライトの状態は文字列 --- で表される．

\(27\) 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，\(27\) を出力する．\(1\) つも点灯しているライトが存在しない場合も条件を満たすものとすることに注意せよ．

この入力例は小課題 \(1,2,3,6\) の制約を満たす．

Sample input 4
9
RGBRGBRGB
1000000000 1000000000 1
Sample output 4
0

既にライトの色の並びは RGB の繰り返しになっているため，\(0\) を出力する．

この入力例は小課題 \(2,3,4,5,6\) の制約を満たす．

Sample input 5
20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1
Sample output 5
2000000008

この入力例は小課題 \(2,3,5,6\) の制約を満たす．

Sample input 6
23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229
Sample output 6
10107224827

この入力例は小課題 \(2,3,6\) の制約を満たす．

Notes

JOI 2024 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source