【CSP】CSP-XL 2025辽宁复赛真题-第二题, 积分（points）

1#include <algorithm>
2#include <climits>
3#include <iostream>
4
5long long a_array[1005][1005];     // 存放原始二维数组，行列下标从1开始
6long long pre_sum[1005][1005];    // 二维前缀和数组，pre_sum[i][j]表示(1,1)到(i,j)子矩阵的和
7int main() {
8    freopen("points.in", "r", stdin);   // 复赛标准输入文件
9    freopen("points.out", "w", stdout); // 复赛标准输出文件
10    int n, m, x, y;                     // n行m列，x×x与y×y两种尺寸的正方形区域
11    std::cin >> n >> m >> x >> y;
12    // 读入原始矩阵
13    for (int i = 1; i <= n; i++) {
14        for (int j = 1; j <= m; j++) {
15            std::cin >> a_array[i][j];
16        }
17    }
18
19    // 计算二维前缀和
20    for (int i = 1; i <= n; i++) {
21        for (int j = 1; j <= m; j++) {
22            pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] -
23                            pre_sum[i - 1][j - 1] + a_array[i][j];
24        }
25    }
26
27    // 枚举所有x×x正方形区域，求最大积分
28    long long max_x_points = LLONG_MIN; // 初始化为最小值
29    for (int i = 1; i <= n; i++) {
30        for (int j = 1; j <= m; j++) {
31            if (i + x - 1 <= n && j + x - 1 <= m) {
32                long long cur_points =
33                    pre_sum[i + x - 1][j + x - 1] - pre_sum[i - 1][j + x - 1] -
34                    pre_sum[i + x - 1][j - 1] + pre_sum[i - 1][j - 1];
35                max_x_points = std::max(max_x_points, cur_points);
36            } else {
37                break; // 当前行剩余位置无法满足x×x区域，直接跳出内层循环
38            }
39        }
40    }
41
42    // 枚举所有y×y正方形区域，求最大积分
43    long long max_y_points = LLONG_MIN;
44    for (int i = 1; i <= n; i++) {
45        for (int j = 1; j <= m; j++) {
46            if (i + y - 1 <= n && j + y - 1 <= m) {
47                long long cur_points =
48                    pre_sum[i + y - 1][j + y - 1] - pre_sum[i - 1][j + y - 1] -
49                    pre_sum[i + y - 1][j - 1] + pre_sum[i - 1][j - 1];
50                max_y_points = std::max(max_y_points, cur_points);
51            } else {
52                break; // 同理，提前结束本行后续枚举
53            }
54        }
55    }
56
57    // 输出两种尺寸中的最大积分
58    long long max_points = std::max(max_x_points, max_y_points);
59    std::cout << max_points << std::endl;
60    return 0;
61}