Acwing4405. Statistical submatrix

Given a  N×M Matrix  A, Please count how many sub matrices there are ( Minimum  1×1, Maximum  N×M) Satisfy that the sum of all numbers in the submatrix does not exceed the given integer  K?

Input format

The first line contains three integers  N,M and  K.

after  N  Each line contains  M  It's an integer , Representative matrix  A.

Output format

An integer represents the answer .

Data range

about  30% The data of ,N,M≤20,
about  70%  The data of ,N,M≤100,
about  100%  The data of ,1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000.

sample input ：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

sample output ：

19

Sample explanation

The submatrix satisfying the condition has  19, contain ：

• The size is  1×1  There are  10  individual .
• The size is  1×2  There are  3  individual .
• The size is  1×3  There are  2  individual .
• The size is  1×4  There are  1  individual .
• The size is  2×1  There are  3  individual .

If you use it directly The prefix and + violence , The complexity will be O(N^4), Must be optimized

The way to optimize is ：
1） Enumerating submatrix Left boundary i and Right border j,
2） use Quick pointer t enumeration The lower boundary of the submatrix , Slow pointer s maintain Upper boundary of submatrix (s ≤ t)
3） If the sum of the weights of the obtained submatrix Greater than k, Slow pointer s Forward , And the sum of submatrixes must be monotonic
4） Slow pointer s To move forward （ Pictured ）, until The sum of submatrix No more than k, There is no need for the slow pointer to move forward , Because all widths of this submatrix are j - i + 1 The submatrix of （ in total t - s + 1 Kind of ） Must meet the requirements , Update the contribution of this situation to the answer t - s + 1; conversely , If the slow pointer s Transboundary （s > t）, Do not operate , Directly enter the lower circulation

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int a[N][N] , qz[N][N] ,  n , m;
long long int k , sum = 0;
int main()
{
    cin >> n >> m >> k;
// Prefix and representation 
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ){
            cin >> a[i][j];
            //a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            qz[i][j] = a[i][j] + qz[i - 1][j] + qz[i][j - 1] - qz[i - 1][j - 1];
        }
// Double pointer algorithm 
    for(int i = 1; i <= m; i ++){
        for(int j = i; j <= m; j ++){
            for(int s = 1, t = 1; t <= n; t ++ ){
                while(s <= t && qz[t][j] - qz[s - 1][j] - qz[t][i - 1] + qz[s - 1][i - 1] > k) s ++;
                if(s <= t) sum += t - s + 1;
            }
        }
    }
            
    cout << sum << endl;
    return 0;
}