問題一覧 > 通常問題

No.755 Zero-Sum Rectangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
3 ProblemId : 2553 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-02 00:11:33

問題文

$M \times M$ マスの正方形 $A$ があります。 $A$ の各マスには値が設定されていて、マス $(i,j)$ の値は $A_{i,j}$ です。
ぽかーん懐古DPさんは、各 $(x_i,y_i)$ について、$A$ の中の空でない長方形の範囲のうち、マス $(x_i,y_i)$ を含み、その総和が $0$ になるものの個数を数えたいです。
ただし、ここで数えるのは長方形の範囲の取り出し方であることに注意してください。つまり、ある $2$ つの長方形の範囲に含まれる数が同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。

入力

$N\ M$
$A_{1,1} \cdots A_{1,M}$
$\hspace{6pt}\vdots$
$A_{M,1} \cdots A_{M,M}$
$x_1\ \ y_1$
$\hspace{3pt}\vdots$
$x_N\ \ y_N$
  • $1≤N≤10$
  • $1≤M≤130$
  • $-10^9≤A_{i,j}≤10^9$
  • $1≤x_i,y_i≤M$
  • 入力はすべて整数

また、$N = 1300$ の evil ケースが存在する。このテストケースは提出結果には影響しない。

出力

各 $(x_i,y_i)$ について、$A$ の中の空でない長方形の範囲のうち、マス $(x_i,y_i)$ を含み、その総和が $0$ になるものの個数を出力してください。

サンプル

サンプル1
入力
4 4
0 -1 5 5
-3 3 0 -3
5 -1 -5 4
-4 4 -5 0
2 4
4 1
4 3
2 2
出力
2
1
1
5

$x_i=2,y_i=4$ のとき、 $(2,1),(3,4)$ と $(2,2),(2,4)$ の $2$ 個の長方形が条件を満たすので、$2$ を出力します。
$x_i=4,y_i=1$ のとき、 $(4,1),(4,2)$ の $1$ 個の長方形が条件を満たすので、$1$ を出力します。

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