시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 94 | 66 | 65 | 70.652% |
JOI 商店街には大通りに沿って N 個の店があり,JOI 商店街の入口から出口に向かってそれぞれ 1, 2, . . . , N の番号が付けられている.JOI 商店街は一方通行で,入口から出口方向へしか移動することはできない.
まちおこしのため,JOI 商店街でスタンプラリーを行うことになった.このスタンプラリーでは,それぞれの店は J,O,I のいずれかのスタンプを用意し,店で買い物をした人はスタンプカードにスタンプを押してもらう.スタンプラリーに参加する人はちょうど 3 つの店に入る.商店街の入口では 3 つの欄のあるスタンプカードを配り,1 回目に入った店,2 回目に入った店,3 回目に入った店のスタンプを押してもらう.商店街の出口でスタンプカードを回収し,押されたスタンプが先に入った店のものから順に J,O,Iになっているとき,出口で商品券がもらえるキャンペーンを実施することになった.押されたスタンプの種類や順番が異なるときは商品券はもらえない.
すでに N 個のすべての店はどのスタンプを用意するか決めたが,新たに 1 つの店を JOI 商店街に出すことになり,新しく出店する場所と,その店が用意するスタンプを決めることになった.新しい店を出す場所は,店 i と店 i + 1 の間 (1 ≦ i ≦ N − 1),入口と店 1 の間,店 N と出口の間のいずれかから決める.また,新しい店のスタンプは J,O,I の 3 通りから決める.
商品券をもらえるような店の選び方の数が大きいほど,スタンプラリーが盛り上がると商店街は考えた.そこで,新しく出す店の場所と用意するスタンプを決めたときの,上記の店の選び方の数の最大値を求めたい.
JOI 商店街のすでにある店が用意したスタンプの情報が与えられたとき,新しく出す店の場所と用意す るスタンプを決めたときの,商品券をもらえるような店の選び方の数の最大値を求めるプログラムを作成 せよ.
標準入力から以下の入力を読み込め.
商品券をもらえるような店の選び方の数の最大値を標準出力に 1 行で出力せよ.
商品券をもらえるような店の選び方の数が 32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 30 | N ≦ 200 を満たす. |
2 | 20 | N ≦ 3 000 を満たす. |
3 | 50 | 追加の制限はない. |
5 JOIOI
6
入力例 1 では,店 1 と店 2 の間に,スタンプ J を用意する新しい店を出したとき,店が用意したスタン プを入口から順に並べると JJOIOI となる.
このとき,商品券をもらえるような店の選び方は以下の 6 通りである.
入力例 1 において,商品券をもらえるような店の選び方が 7 通り以上になることはない.
7 JJJOIII
18
4 OIIJ
2
入力例 3 では,入口と店 1 の間にスタンプ J を用意する新しい店を出したとき,商品券をもらえるよう な店の選び方の数が最大となる.