TopCoder

User's AC Ratio

100.0% (26/26)

Submission's AC Ratio

55.4% (67/121)

Description

有三個人(P, E, C)走在路上很無聊,於是他們開始了一個遊戲。
他們將要走的路是一條筆直的路徑,依序有$N\leq 2\times 10^ 6$ 顆石塊排成一排。這$N$顆石塊很特別,每一顆都只能被P、E、C其中一個人撿起。之後P、E、C會在走過這條路時選一個區間開始撿石塊,將區間內所有可以被他撿起的石塊都拿起來。然而為了避免P、E、C三個人在路途中打架,他們所選定的區間兩兩交集必須要是空的。

說石持那十塊,P、E、C三個人已經走完這條路並且撿好石塊了。請計算他們三人所持有的石塊個數總和最大是多少。

Input Format

第一行有一個正整數$N\leq 2\times 10^ 6$,代表石塊的個數。
第二行包含一個有$N$個字元的字串,第$i$個字元代表能撿起第$i$顆石塊的人。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 20$ 28
2 (0~9) $N\leq 10^ 4$ 36
3 (0~14) 無限制 36

Output Format

請輸出一個正整數,代表三人撿起的石塊個數總和最大值。

Sample Input

9
PEPCPCECE

Sample Output

6

Hints

以下為範例輸入中的最佳方案:
P將[PEP]中的兩個P撿起
E將[ECE]中的兩個E撿起
C將[CPC]中的兩個C撿起

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第二階段選訓第四次模擬考pB
說石持那十塊 by original description

Subtasks

For Testdata: 0 ~ 4, Score: 28
For Testdata: 0 ~ 9, Score: 36
For Testdata: 0 ~ 14, Score: 36
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144