先想一下暴力如何枚举 如果我们想确定一个矩形 我们需要枚举它的两个对顶点的坐标 这样时间复杂度就是O(N^4) 一定会tle 再来考虑如何优化

本题的关键在于所有元素都是非负的 所以对于任意一个矩形 在它的基础上增加元素 总和一定会大于等于原来的和 是具有单调性的

对于图中的矩形他们的两个对顶点坐标为****(i, l)和(j, r)****

考虑固定i、j，l和r如何移动？（将列i-j看成一个整体，那么这就成了一个一维问题）

两种情况

1. 当前矩阵和大于k r如果往右一定会大于等于现在的和 所以只能移动l 直至和不大于k

2. 矩阵和不超过k 统计子矩阵数量r - l + 1

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long ll;
   const int N = 510;
   int g[N][N], s[N][N];
   int n, m, k;
   
   void solve()
   {
       cin>>n>>m>>k;
   
       for(int i = 1; i <= n; i ++ )
           for(int j = 1; j <= m; j ++ )
           {
               cin>>g[i][j];
               s[i][j] = s[i - 1][j] + g[i][j];//在列方向上求前缀和
           }
   
       ll cnt = 0;
       for(int i = 1; i <= n; i ++ )
           for(int j = i; j <= n; j ++ )
               for(int l = 1, r = 1, sum = 0; r <= m; r ++ )
               {
                   sum += s[j][r] - s[i - 1][r];
                   while(sum > k)
                   {
                       sum -= s[j][l] - s[i - 1][l];
                       l++;
                   }
                   cnt += r - l + 1;
               }
   
       cout<<cnt<<endl;
   }
   
   int main()
   {
       ios::sync_with_stdio(false);
       cin.tie(nullptr);
       cout.tie(nullptr);
   
       solve();
       return 0;
   }