AcWing 4405. 统计子矩阵(前缀和 + 双指针)
原题链接
中等
作者:
Cathyqiii
,
2024-03-20 22:52:43
,
所有人可见
,
阅读 56
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 5e2+3;
int a[N][N];
int main(){
ios::sync_with_stdio(false);
int n,m,k;
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> a[i][j];
// 计算前缀和,存储在数组 a 的当前位置
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
ll ans = 0;
for(int i=1; i<=m; i++){
for(int j=i; j<=m; j++){
// 遍历子矩阵的右上角坐标,从 (1,1) 开始
for(int s = 1, t = 1; t <= n; t ++ ){
// 计算当前子矩阵的和,如果和大于 k,则递增 s 直到和不大于 k
while(s <= t && a[t][j] - a[s - 1][j] - a[t][i - 1] + a[s - 1][i - 1] > k) s ++ ;
// 如果 s <= t,则说明找到了一个满足条件的子矩阵,增加 ans 的值
if(s <= t) ans += t - s + 1;
}
}
}
cout << ans << '\n';
}