AcWing 4405. 统计子矩阵
原题链接
中等
作者:
no_one
,
2022-10-11 20:19:35
,
所有人可见
,
阅读 334
双指针
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510;
int n, m, k;
int a[N][N], s[N][N];
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n ; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
for(int i = 1; i <= n ; i ++)
for(int j = 1; j <= m; j ++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
LL res = 0;
for (int i = 1; i <= m; i ++ ) // 左边界
for (int j = i; j <= m; j ++ ) // 右边界
for (int u = 1, d = 1; d <= n; d ++ )
{
while (u <= d && s[d][j] - s[u - 1][j] - s[d][i - 1] + s[u - 1][i - 1] > k) u ++ ; // 双指针
if (u <= d) res += d - u + 1; // 更新答案
}
cout << res << endl;
return 0;
}
很不错