蓝桥杯2022试题F统计子矩阵

时间限制: 1.0s 内存限制: 256.0MB 本题总分&＃xff1a;15 分
【问题描述】
给定一个 N × M 的矩阵 A&＃xff0c;请你统计有多少个子矩阵 (最小 1 × 1&＃xff0c;最大
N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
【输入格式】
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数&＃xff0c;代表矩阵 A.
【输出格式】
一个整数代表答案。
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
19
【样例说明】
满足条件的子矩阵一共有 19&＃xff0c;包含&＃xff1a;
大小为 1 × 1 的有 10 个。
大小为 1 × 2 的有 3 个。
大小为 1 × 3 的有 2 个。
大小为 1 × 4 的有 1 个。
大小为 2 × 1 的有 3 个。
【评测用例规模与约定】
对于 30% 的数据&＃xff0c;N, M ≤ 20.
对于 70% 的数据&＃xff0c;N, M ≤ 100.
对于 100% 的数据&＃xff0c;1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.
 

#include
using namespace std;
typedef long long ll;
ll dp[500&＃43;10][500&＃43;10];int main()
{ ll n,m,x,k,co&＃61;0;cin>>n>>m>>k;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){ cin>>x;dp[i][j]&＃61;dp[i-1][j]&＃43;dp[i][j-1]-dp[i-1][j-1]&＃43;x;}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)//起点{for(int ii&＃61;i;ii<&＃61;n;ii&＃43;&＃43;)for(int jj&＃61;j;jj<&＃61;m;jj&＃43;&＃43;)//终点 {if(dp[ii][jj]-dp[i-1][jj]-dp[ii][j-1]&＃43;dp[i-1][j-1]<&＃61;k)co&＃43;&＃43;;//if(dp[ii][jj]-dp[ii-1][j]-dp[i][jj-1]&＃43;dp[i-1][j-1]<&＃61;k)co&＃43;&＃43;;//刚开始想错了&＃xff0c;终点线没问题}}cout<}