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.
Input
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.
Output
Write to the output the number of submatrices of a given matrix with sum of their elements between A and B inclusively.
Example
Input: 3 3 1 0 0 0 1 0 0 0 1 1 3 Output: 26
hide comments
wutiruo:
2022-10-03 17:11:18
is there any other better algorithm other than o(n^2 mlogm) |
|
Sigma Kappa:
2020-06-05 22:36:52
OK I am getting TLE with an O(n^2mlog(m)) algo, where n <= m. What did you use?
|
|
Palashvijay4O:
2016-08-10 06:41:23
code running till 20th test case even if it is not working for smaller test cases. Please have a look into it. |
|
abdou_93:
2016-03-18 20:04:37
O(n^3 log n) |
|
Noureldin Yosri:
2016-03-16 19:43:07
don't take this problem seriously :3 |
|
nour samir:
2014-07-20 21:41:49
this problem is solvable by using segment tree and DP |
|
Hussain Kara Fallah:
2014-01-03 09:25:19
I love this kind of problems
|
|
rajnish:
2012-05-17 10:51:16
is there any other better algorithm other than o(n^2*m^2) |
|
Prabakaran:
2011-02-21 20:48:00
hw is the output 26 for the above test case? |
Added by: | Pavel Kuznetsov |
Date: | 2007-02-23 |
Time limit: | 1s-1.841s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | IT Festival Arkhangelsk 2006 |