JOI '20 Open P2 - Monochrome Points - Olympiads Online Judge

JOI '20 Open P2 - Monochrome Points

Points: 35 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

There are $2N$ ~2N~ points on a circle numbered from $1$ ~1~ through $2N$ ~2N~, in clockwise order. Each point is either white or black. There are $N$ ~N~ white points and $N$ ~N~ black points.

We will draw $N$ ~N~ line segments connecting these points so that the following conditions are satisfied.

Each point is an end point of exactly one line segment.
Each line segment connects a white point and a black point.

Among the $N$ ~N~ line segments, the number of pairs of line segments intersecting each other is called the intersection number. Write a program which, given the information of the colors of the points, calculates the maximum of the intersection number when we draw $N$ ~N~ line segments.

Input Specification

Read the following data from the standard input.

$N$ ~N~

$S$ ~S~

Here $S$ ~S~ is a string of length $2N$ ~2N~ representing the colors of the points. Each character of $S$ ~S~ is either B or W, and the $i$ ~i~-th character $(1 \le i \le 2N)$ ~(1 \le i \le 2N)~ is the color of the $i$ ~i~-th point. It is B if the point is black, and W if the point is white.

Output Specification

Write one line to the standard output. The output should contain the maximum of the intersection number when we draw $N$ ~N~ line segments satisfying the conditions.

Constraints

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~.
$S$ ~S~ is a string of length $2N$ ~2N~ which consists of B and W. The character B appears $N$ ~N~ times in the string $S$ ~S~, and the character W appears $N$ ~N~ times in the string $S$ ~S~.

Subtasks

(4 points) $N \le 8$ ~N \le 8~.
(21 points) $N \le 300$ ~N \le 300~.
(10 points) $N \le 2\,000$ ~N \le 2\,000~.
(65 points) No additional constraints.

Sample Input 1

3
BBWWBW

Sample Output 1

Explanation for Sample 1

If we draw line segments as in the figure on the left, then the intersection number is $2$ ~2~. On the other hand, if we draw line segments as in the figure on the right, then the intersection number is $3$ ~3~, but the conditions in the task statement are not satisfied.

$\text{[math]}$

Sample Input 2

5
BWBWBBWBWW

Sample Output 2

Sample Input 3

10
WBBBWBBWWBWWBWWBWBWB

Sample Output 3

Sample Input 4

16
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW

Sample Output 4

Comments

There are no comments at the moment.