問題一覧 > 通常問題

No.2225 Treasure Searching Rod (Easy)

レベル : / AI推定難易度 : 151 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 173
作問者 : 👑 AngrySadEight / テスター : akakimidori hari64
お気に入りにしたユーザー ProblemId : 8910 / 自分の提出
問題文最終更新日: 2023-01-22 17:08:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 378 (順位表) の他の問題:

This problem has the same setting as "Treasure Searching Rod (Hard)"; only the constraints differ.

Problem Statement

There is a grid with $H$ rows and $W$ columns, and the cell in row $i$ and column $j$ is denoted by $(i,j)$.

In $K$ cells of this grid, $10^{100}$ "treasures" are placed in each cell. The $k$-th treasure is in cell $(x_k, y_k)$, and the value of $1$ piece of it is $v_k$.

Now, the operation shown below is called "the operation on cell $(i,j)$".

If there are treasures in a cell $(x,y)$ that satisfies all of the following conditions with respect to cell $(i,j)$, obtain $1$ piece of the treasure in each such cell $(x,y)$.

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

You performed the operation on every cell $(i,j)$ satisfying $1 \leq i \leq H, 1 \leq j \leq W$, $1$ time each. Find the total value of the treasures obtained, modulo $998244353$.

Constraints

  • All input values are integers.
  • $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)$

Input

The input is given from standard input in the following format.

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

Output

Output the total value of the treasures obtained, modulo $998244353$.

Sample

Sample 1
Input
3 3 4
1 2 4
2 1 5
2 2 6
3 1 2
Output
55

The grid and the values of the treasures placed on it are as shown in the following figure.

2022-10-28-150226

For example, the range in which treasures can be obtained by the operation on cell $(1,2)$ is shown below.

2022-10-28-150254
  • The value of the treasures obtained by the operation on cell $(1,1)$ is $5+6+2=13$.
  • The value of the treasures obtained by the operation on cell $(1,2)$ is $4+5+6+2=17$.
  • The value of the treasures obtained by the operation on cell $(1,3)$ is $6+2=8$.
  • The value of the treasures obtained by the operation on cell $(2,1)$ is $5+2=7$.
  • The value of the treasures obtained by the operation on cell $(2,2)$ is $6+2=8$.
  • No treasures can be obtained by the operation on cell $(2,3)$.
  • The value of the treasures obtained by the operation on cell $(3,1)$ is $2$.
  • No treasures can be obtained by the operation on cell $(3,2)$.
  • No treasures can be obtained by the operation on cell $(3,3)$.

Therefore, the total value of the treasures obtained is $13+17+8+7+8+2=55$.

Sample 2
Input
3 8 4
2 2 10
2 3 10
3 2 20
3 5 30
Output
510

For example, the range in which treasures can be obtained by the operation on cell $(1,4)$ is as shown in the following figure.

2022-12-06-184418
Sample 3
Input
2 3 2
1 2 1000000000
2 3 1000000000
Output
7022588

Output the total value of the treasures modulo $998244353$.

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