Carnival Game

Points: 7

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Annually, from July 27 to August 11, the local carnival opens for business! The main attraction of the carnival this year is a peculiar looking game that you and your friends have decided to try out. The game has $N-1$ $N - 1$ layers of wooden boards arranged in a pyramid-like structure (layer $i$ $i$ has $i$ $i$ boards), with each board either pointing downwards and to the left or downwards and to the right.

You are told that a ball will be dropped on the topmost board.

There are $N$ $N$ buckets at the bottom of the structure. Bucket $i$ $i$ contains $t_i$ $t_{i}$ dollars worth of coins (because carnivals are a scam, $t_i$ $t_{i}$ can be negative). You take home all the money in the bucket that the ball eventually lands in.

A ball that lands on the $j^{th}$ $j^{t h}$ board on the $i^{th}$ $i^{t h}$ layer, $b_{i, j}$ $b_{i, j}$ , will fall to the $j^{th}$ $j^{t h}$ board on the $i+1^{th}$ $i + 1^{t h}$ layer if $b_{i, j}$ $b_{i, j}$ is facing downwards and to the left, or to the $j+1^{th}$ $j + 1^{t h}$ board on the $i+1^{th}$ $i + 1^{t h}$ layer if $b_{i, j}$ $b_{i, j}$ is facing downwards and to the right. On the $N-1^{th}$ $N - 1^{t h}$ layer, the same rules are applied, however, the ball falls into a bucket on row $N$ $N$ instead of another board.

Before you drop the ball on the topmost board, you are allowed to flip any board to face downwards and to the left if it was originally facing downwards and to the right, and vice versa. Doing so will cost you $1$ $1$ dollar. Not wanting to hold up the line, quickly calculate the maximum profit $P$ $P$ (even if it has to be negative) you can make, and what boards to flip to achieve $P$ $P$ !

Constraints

$2 \le N \le 2 \times 10^3$ $2 \leq N \leq 2 \times 10^{3}$

$-10^9 \le t_i \le 10^9$ $- 10^{9} \leq t_{i} \leq 10^{9}$

Input Specification

The first line contains $N$ $N$ , the number of levels in the carnival game and the number of buckets.

The next $N-1$ $N - 1$ lines represent the layers of the pyramid, with the $j^{th}$ $j^{t h}$ character on the $i^{th}$ $i^{t h}$ line representing the orientation of the $j^{th}$ $j^{t h}$ board on the $i^{th}$ $i^{t h}$ layer, L for facing downwards and to the left or R for facing downwards and to the right.

The final line contains $N$ $N$ space separated integers $t_i$ $t_{i}$ .

Output Specification

First, output an integer $P$ $P$ , the maximum profit you can make.

Next, output an integer $K$ $K$ $\left(0 \le K \le \frac{N(N-1)}{2}\right)$ $(0 \leq K \leq \frac{N (N - 1)}{2})$ , the number of flips made to obtain $P$ $P$ .

Lastly, output $K$ $K$ lines each containing two space-separated integers $i$ $i$ and $j$ $j$ , representing that the $j^{th}$ $j^{t h}$ board on the $i^{th}$ $i^{t h}$ layer was flipped.

Any $K$ $K$ steps that achieve $P$ $P$ will be accepted.

Sample Input 1

Copy

3
L
RR
-1 0 1

Sample Output 1

Copy

0
1
1 1

Explanation for Sample 1

Flipping the first board on the first layer gets us to:

Copy

R
RR

We can see that the ball reaches the third bucket in row $N$ $N$ and we get a profit of $1-1 = 0$ $1 - 1 = 0$ dollars. Alternatively, we could flip no boards and have the ball land in the second bucket and make the same profit of $0-0 = 0$ $0 - 0 = 0$ dollars.

Sample Input 2

Copy

6
L
LL
LLL
LLLL
LLLLL
-727 69 3735 -8210 420 3737

Sample Output 2

Copy

Comments

There are no comments at the moment.