問題一覧 > 通常問題

No.1910 High Element on Grid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 45
作問者 : chineristACchineristAC / テスター : HYEA LEEHYEA LEE tokusakuraitokusakurai
4 ProblemId : 7139 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-22 21:15:32

問題文

(21:15 サンプルを修正)

長さ $n$ の整数列 $X=(X_1,\ X_2,\ \dots,\ X_n)$ において任意の整数 $j< i$ に対し $X_j < X_i$ が成り立つとき、 $X_i$ は「高い項」であるといいます。

長さ $H,\ W$ の整数列 $R=(R_1,\ R_2,\ \dots,\ R_H),\ C=(C_1,\ C_2,\ \dots,\ C_W)$ が与えられます。ここで、 $R_1=C_1=1$ が成り立ちます。

以下の条件を満たす $H \times W$ 行列 $A=(A_{i,j})_{1\le i \le H,\ 1\le j \le W}$ を $1$ つ求めてください。この問題の制約の下で、条件を満たす $A$ が $1$ つ以上存在することが証明できます

条件

  • $1 \le A_{i,j} \le 10^9$
  • 任意の $1\le i \le H$ に対し、整数列 $(A_{i,1},\ A_{i,2},\ \dots,\ A_{i,W})$ の「高い項」はちょうど $R_i$ 個存在する
  • 任意の $1 \le j \le W$ に対し、整数列 $(A_{1,j},\ A_{2,j},\ \dots,\ A_{H,j})$ の「高い項」はちょうど $C_j$ 個存在する

入力

$H$ $W$
$R_1$ $R_2$ $\dots$ $R_H$
$C_1$ $C_2$ $\dots$ $C_W$
  • $1 \le H,\ W \le 500$
  • $1 \le R_i \le W$
  • $1 \le C_j \le H$
  • $R_1=C_1=1$
  • 与えられる入力はすべて整数

出力

条件を満たす $A$ を $1$ つ以下の形式で出力してください。条件を満たすものが複数存在する場合はいずれを出力してもかまいません。

$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$

最後に改行してください。

サンプル

サンプル1
入力
2 4
1 2
1 1 2 2
出力
6 3 4 1 
5 2 8 2

整数列 $(A_{1,1},\ A_{1,2},\ A_{1,3},\ A_{1,4})=(6,\ 3,\ 4,\ 1)$ の「高い項」は $A_{1,1}=6$ の $R_1=1$ 個です。

整数列 $(A_{2,1},\ A_{2,2},\ A_{2,3},\ A_{2,4})=(5,\ 2,\ 8,\ 2)$ の「高い項」は $A_{2,1}=5,\ A_{2,3}=8$ の $R_2=2$ 個です。

よって $2$ 番目の条件を満たしています。同様にして $3$ 番目の条件を満たすことも確認できます。

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