103695: [Atcoder]ABC369 F - Gather Coins

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

There are $N$ coins on this grid, and the $i$-th coin can be picked up by passing through the cell $(R_i,C_i)$.

Your goal is to start from cell $(1,1)$, repeatedly move either down or right by one cell, and reach cell $(H,W)$ while picking up as many coins as possible.

Find the maximum number of coins you can pick up and one of the paths that achieves this maximum.

Constraints

• $2\leq H,W \leq 2\times 10^5$
• $1\leq N \leq \min(HW-2, 2\times 10^5)$
• $1\leq R_i \leq H$
• $1\leq C_i \leq W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$ are pairwise distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $N$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_N$ $C_N$

Output

Print two lines. The first line should contain the maximum number of coins you can pick up. The second line should contain one of the paths that achieves this maximum as a string of length $H+W-2$. The $i$-th character of this string should be D if the $i$-th move is downward, and R if it is rightward.

If there are multiple paths that maximize the number of coins picked up, you may print any of them.

Sample Input 1

3 4 4
3 3
2 1
2 3
1 4

Sample Output 1

3
DRRDR

As shown in the figure above, by moving $(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$, you can pick up three coins at $(2,1),(2,3),(3,3)$.

Sample Input 2

2 2 2
2 1
1 2

Sample Output 2

1
DR

The path RD is also acceptable.

Sample Input 3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

Sample Output 3

5
DRRRRRRRRDDDDDRRDRDDRRR

问题陈述

有一个有$H$行和$W$列的网格。 用$(i,j)$表示从顶部第$i$行和从左侧第$j$列的单元格。

在这个网格上有$N$枚硬币，第$i$枚硬币可以通过经过单元格$(R_i,C_i)$来拾取。

你的目标是从单元格$(1,1)$开始，重复向下或向右移动一个单元格，并在拾取尽可能多的硬币的同时到达单元格$(H,W)$。

找出你可以拾取的最大硬币数量以及实现这一最大值的其中一条路径。

约束条件

• $2\leq H,W \leq 2\times 10^5$
• $1\leq N \leq \min(HW-2, 2\times 10^5)$
• $1\leq R_i \leq H$
• $1\leq C_i \leq W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$两两不同。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$H$ $W$ $N$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_N$ $C_N$

输出

打印两行。 第一行应包含你可以拾取的最大硬币数量。 第二行应包含实现这一最大值的一条路径，该路径的长度为$H+W-2$。 这个字符串的第$i$个字符如果是向下移动，则为D；如果是向右移动，则为R。

如果有多条路径可以最大化拾取的硬币数量，你可以打印其中任何一条。

样本输入 1

3 4 4
3 3
2 1
2 3
1 4

样本输出 1

3
DRRDR

如上图所示，通过移动$(1,1)\rightarrow (2,1)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (3,4)$，你可以在$(2,1),(2,3),(3,3)$拾取三枚硬币。

样本输入 2

2 2 2
2 1
1 2

样本输出 2

1
DR

路径RD也是可接受的。

样本输入 3

10 15 8
2 7
2 9
7 9
10 3
7 11
8 12
9 6
8 1

样本输出 3

5
DRRRRRRRRDDDDDRRDRDDRRR