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 (-109 ≤ A ≤ B ≤ 109). All numbers separated with spaces. It is guaranteed that for every submatrix the absolute value of the sum of its elements will not exceed 109.
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 |
RSS