KPMATRIX - Matrix
The company you work in has got a secret job to do. Just a few persons know what it is all about. To keep a secret every programmer works on a small part of the project.
Your job is as follows. You are given a matrix of integer numbers with N rows and M columns. Also two integer numbers A and B are given. Your task is to find a number of submatrices of a given matrix with the sum of elements between A and B inclusively.
The first line contains two integer numbers N and M (1 ≤ N, M ≤ 250). After that matrix description follows. N lines with M numbers each. The last line contains two integer numbers A and B (-10^9 ≤ A ≤ B ≤ 10^9). All numbers separated with spaces. It's guaranteed that for every submatrix the absolute value of sum of it's elements will not exceed 10^9.
Write to the output the number of submatrices of a given matrix with sum of their elements between A and B inclusively.
Input: 3 3 1 0 0 0 1 0 0 0 1 1 3 Output: 26
code running till 20th test case even if it is not working for smaller test cases. Please have a look into it.
O(n^3 log n)
don't take this problem seriously :3
this problem is solvable by using segment tree and DP
Hussain Kara Fallah:
I love this kind of problems
is there any other better algorithm other than o(n^2*m^2)
hw is the output 26 for the above test case?