| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
2022-10-03 17:11:18
is there any other better algorithm other than o(n^2 mlogm) |
|
|
2020-06-05 22:36:52 Sigma Kappa
OK I am getting TLE with an O(n^2mlog(m)) algo, where n <= m. What did you use? EDIT: Nevermind, got Acc. Last edit: 2020-06-06 00:29:03 |
|
|
2016-08-10 06:41:23 Palashvijay4O
code running till 20th test case even if it is not working for smaller test cases. Please have a look into it. |
|
|
2016-03-18 20:04:37 abdou_93
O(n^3 log n) |
|
|
2016-03-16 19:43:07 Noureldin Yosri
don't take this problem seriously :3 |
|
|
2014-07-20 21:41:49 nour samir
this problem is solvable by using segment tree and DP |
|
|
2014-01-03 09:25:19 Hussain Kara Fallah
I love this kind of problems just try the 1D version :D |
|
|
2012-05-17 10:51:16 rajnish
is there any other better algorithm other than o(n^2*m^2) |
|
|
2011-02-21 20:48:00 Prabakaran
hw is the output 26 for the above test case? |
RSS