問題一覧 > 通常問題

No.3210 Fixed Sign Sequense

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : 👑 loop0919 / テスター : yuusaan lif4635 Cafe1942
ProblemId : 12383 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-25 21:11:48
コンテストの他の問題:

問題文

正整数 $N$ と、+, 0, - からなる長さ $N$ の文字列 $S$ が与えられます。

長さ $N$ の整数列 $A$ が嬉しい数列であるとは、すべての $i ~ (1 \leq i \leq N)$ について以下の条件を満たすことを指します。

  • $S$ の $i$ 文字目が + ならば $A_i > 0$ である。
  • $S$ の $i$ 文字目が 0 ならば $A_i = 0$ である。
  • $S$ の $i$ 文字目が - ならば $A_i < 0$ である。

長さ $N$ の嬉しい数列に対する、最長増加部分列の長さとしてあり得る最大値を求めてください。

ここで数列 $X$ の最長増加部分列とは、$X$ の狭義単調増加な（連続とは限らない）部分列の中で長さが最大のものを指します。

制約

  • $1 \leq N \leq 3 \times 10^5$
  • $N$ は整数である
  • $S$ は +, 0, - からなる長さ $N$ の文字列である

入力

入力は以下の形式で標準入力から与えられます。

$N$
$S$

出力

長さ $N$ の嬉しい数列に対する、最長増加部分列の長さとしてあり得る最大値を出力してください。

サンプル

サンプル1
入力
5
-+-+0
出力
3

嬉しい数列 $A$ を $(-1, 1, -2, 2, 0)$ としたとき、$A$ の最長増加部分列は $(-1, 1, 2)$ となります。

最長増加部分列の長さが $4$ 以上となる嬉しい数列は存在しないため、答えは $3$ となります。

サンプル2
入力
3
+0-
出力
1

いかなる嬉しい数列であっても、最長増加部分列の長さが $2$ 以上になりません。

サンプル3
入力
12
+-+-00+-+-00
出力
5

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