問題一覧 > 通常問題

No.2225 Treasure Searching Rod (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 167
作問者 : 👑 AngrySadEightAngrySadEight / テスター : akakimidoriakakimidori hari64hari64
0 ProblemId : 8910 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-22 17:08:18

この問題は「Treasure Searching Rod (Hard)」と同じ設定の問題で,制約のみが異なります.

問題文

$H$ 行 $W$ 列のマス目があり,$i$ 行 $j$ 列目のマスを $(i,j)$ で表します.

このマス目の中の $K$ マスには,「宝」が $10^{100}$ 個ずつ置かれています.$k$ 番目の宝はマス $(x_k, y_k)$ にあり,その $1$ 個あたりの価値は $v_k$ です.

さて,次に示す操作を,「マス $(i,j)$ に対する操作」と呼びます.

マス $(i,j)$ に対して次の条件を全て満たすマス $(x,y)$ に宝があれば,マス $(x,y)$ にある宝を $1$ つずつ獲得する.

  • $x + y \geq i + j$
  • $x - y \geq i - j$

あなたは,$1 \leq i \leq H, 1 \leq j \leq W$ を満たす全てのマス $(i,j)$ に対する操作を $1$ 回ずつ行いました.このとき,獲得した宝の価値の総和を $998244353$ で割った余りを求めてください.

制約

  • 入力はすべて整数である.
  • $1 \leq H,W \leq 50$
  • $0 \leq K \leq HW$
  • $1 \leq x_k \leq H$
  • $1 \leq y_k \leq W$
  • $0 \leq v_k \leq 10^9$
  • $(x_k, y_k) \neq (x_l, y_l) (k \neq l)$

入力

入力は以下の形式で標準入力から与えられる.

$H$ $W$ $K$
$x_1$ $y_1$ $v_1$
$x_2$ $y_2$ $v_2$
$\vdots$
$x_K$ $y_K$ $v_K$

出力

獲得した宝の価値の総和を $998244353$ で割った余りを出力せよ.

サンプル

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

マス目と,そこに置かれている宝の価値は,次の図のようになります.

2022-10-28-150226

例えば,マス $(1,2)$ に対する操作で,宝を獲得できる範囲を次に示します.

2022-10-28-150254
  • マス $(1,1)$ に対する操作で獲得できる宝の価値は,$5+6+2=13$ です.
  • マス $(1,2)$ に対する操作で獲得できる宝の価値は,$4+5+6+2=17$ です.
  • マス $(1,3)$ に対する操作で獲得できる宝の価値は,$6+2=8$ です.
  • マス $(2,1)$ に対する操作で獲得できる宝の価値は,$5+2=7$ です.
  • マス $(2,2)$ に対する操作で獲得できる宝の価値は,$6+2=8$ です.
  • マス $(2,3)$ に対する操作で宝は獲得できません.
  • マス $(3,1)$ に対する操作で獲得できる宝の価値は,$2$ です.
  • マス $(3,2)$ に対する操作で宝は獲得できません.
  • マス $(3,3)$ に対する操作で宝は獲得できません.

したがって,獲得した宝の価値の総和は,$13+17+8+7+8+2=55$ となります.

サンプル2
入力
3 8 4
2 2 10
2 3 10
3 2 20
3 5 30
出力
510

例えば,マス $(1,4)$ に対する操作で宝を獲得できる範囲は次の図の通りです.

2022-12-06-184418
サンプル3
入力
2 3 2
1 2 1000000000
2 3 1000000000
出力
7022588

宝の価値の総和を $998244353$ で割った余りを出力してください.

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