No.755 Zero-Sum Rectangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 80
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
2 ProblemId : 2553 / 出題時の順位表
問題文最終更新日: 2018-12-02 11:43:15

問題文

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

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