每日一题 第五十七期 洛谷 统计子矩阵

[蓝桥杯 2022 省 B] 统计子矩阵

题目描述

给定一个 $N\times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1\times 1$, 最大 $N\times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$。

输入格式

第一行包含三个整数 $N,M$ 和 $K$。

之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

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

样例输出 #1

19

提示

【样例说明】

满足条件的子矩阵一共有 $19$，包含:

大小为 $1\times 1$ 的有 $10$ 个。

大小为 $1\times 2$ 的有 $3$ 个。 大小为 $1\times 3$ 的有 $2$ 个。

大小为 $1\times 4$ 的有 $1$ 个。

大小为 $2\times 1$ 的有 $3$ 个。

【评测用例规模与约定】

对于 $30\%$ 的数据, $N,M\le 20$.

对于 $70\%$ 的数据, $N,M\le 100$.

对于 $100\%$ 的数据, $1\le N,M\le 500,0\le A_{ij}\le 1000,1\le K\le 2.5\times 10^8$.

蓝桥杯 2022 省赛 B 组 F 题。

AC代码：

#include<iostream>

using namespace std;

typedef long long ll;
const int N = 510;
ll a[N][N];
ll n, m, k;
ll sum[N][N];
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> sum[i][j];
            sum[i][j] += sum[i - 1][j]; 
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j <= n; j ++)
        {
            for(ll l = 1, r = 1, s = 0; r <= m; r ++)
            {
                s += sum[j][r] - sum[i - 1][r];
                while(s > k)
                {
                    s -= sum[j][l] - sum[i - 1][l];
                    l ++;
                }
                res += r - l + 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}