返回题解分享
讨论 / 题解分享/ 帖子详情

统计子矩阵(编程题) - 题解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 510;
int a[N][N];
int n, m, k;

signed main()
{
    cin >> n >> m >> k;

    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];
        }
    int ans = 0;
    for(int i = 1; i <= n; i ++ )
        for(int j = i; j <= n; j ++ )
        {
            for(int x = 1, y = 1; x <= m; x ++ )
            {
                while(y <= m && a[j][y] - a[i - 1][y] - a[j][x - 1] + a[i - 1][x - 1] <= k) y ++ ;
                ans += y - x;
            }
        }
    cout << ans;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!