B3975 [语言月赛 202405] 最大的和

屈老师

[语言月赛 202405] 最大的和

原文

题目描述

小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。

所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个整数 $A_{i, j}$。

接下来你可以在 $A$ 上任取一行、一列或一条与任意对角线平行且只经过网格交叉点的直线（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。

如果对上面的表述有疑惑，请参考样例解释辅助理解。

你需要告诉小 S 这个最大的数字之和。

输入格式

输入共 $n+1$ 行。

第一行，一个正整数 $n$，表示方阵的行数、列数。
接下来 $n$ 行，每行 $n$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 个整数表示 $A_{i, j}$。

输出格式

输出一行一个整数，表示最大的数字之和。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

3
-1 -1 -1
-1 -1 -1
-1 -1 -1

样例输出 #3

-1

样例 #4

样例输入 #4

3
-100 -10 -100
-10 99999 -10
-100 -10 -100

样例输出 #4

提示

样例 1 解释

对于样例 $1$，不难看出第 $3$ 行数字之和最大，有 $3 + 3 + 3 = 9$。

样例 2 解释

对于样例 $2$，数字之和最大的，满足条件的线如下所示：

此时有 $4 + 9 = 13$。

注意，因为要求与对角线平行的直线只能经过网格交点，所以并不能出现同时取 $4, 1, 9$ 或同时取 $4, 1, 9, 2$ 这样的情况。

样例 $3$ 解释

取某条只经过一个 $-1$ 的直线即为最大。注意，不可以一个数字都不选。

样例 $4$ 解释

显然，取斜着的线一定不优，只能选择中间那一行或一列，答案是 $-10 + 99999 - 10 = 99979$。

数据范围

对于前 $30 \%$ 的数据，保证 $A{1, 1}$ 或 $A{n, n}$ 的值为网格中唯一的非负整数。
对于另 $20 \%$ 的数据，保证每一行数字相同，且最后一行中的数字之和为最大值。
对于另 $20 \%$ 的数据，保证每一行数字相同，网格中不存在负数。
对于 $100 \%$ 的数据，保证 $1 \leq n \leq 2 \times 10³, -10⁵ \leq A_{i, j} \leq 10⁵$。

屈老师

#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	int num_max = INT16_MIN;


	vector<pair<int, int>> zuo;
	vector<pair<int, int>> you;
	vector<vector<int>> a(n,vector<int>(n,0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) {
			if (i==0 || j==0)
			{
				zuo.push_back({i,j});
			}
			if (i == 0 || j == n-1)
			{
				you.push_back({ i,j });
			}
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = 0; j < n; j++)
		{
			sum += a[i][j];
		}
		if (sum>num_max)
		{
			num_max = sum;
		}
	}

	for (int i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = 0; j < n; j++)
		{
			sum += a[j][i];
		}
		if (sum > num_max)
		{
			num_max = sum;
		}
	}
	
	for (auto o : zuo)
	{
		int hang, lie, sum = 0;
		hang = o.first;
		lie = o.second;
		while (hang < n && lie < n)
		{
			sum += a[hang][lie];
			hang++;
			lie++;
		}
		if (sum > num_max)
		{
			num_max = sum;
		}
	}

	for (auto o : you)
	{
		int hang, lie, sum = 0;
		hang = o.first;
		lie = o.second;
		while (hang < n && lie >=0)
		{
			sum += a[hang][lie];
			hang++;
			lie--;
		}
		if (sum > num_max)
		{
			num_max = sum;
		}
	}

	cout << num_max;

	return 0;
}