No.755 Zero-Sum Rectangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 48
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
2 ProblemId : 2553 / 出題時の順位表

問題文

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

入力

$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$
入力はすべて整数で与えられる

出力

各 $(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を出力します。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。