题目链接
Codeforces Round 872 (Div. 2)

Example
input
5
2 2
1 3 1 4
2 2
-1 -1 -1 -1
2 3
7 8 9 -3 10 8
3 2
4 8 -3 0 -7 1
4 3
-32030 59554 16854 -85927 68060 -64460 -79547 90932 85063 82703 -12001 38762
output
9
0
64
71
1933711

题目大意：

每组测试给一个n和m，随后给出nm个数。
要求将这些数放进nm的矩阵数组中，求上述式子的最大值。
其实每次都是取矩阵(1,1)到(i,j)这个子矩阵中最大值和最小值，将最大值减去最小值即可，最后将所有的值相加。

解题思路：

因为数字放的位置不同，最后的结果可能会有变化，但会注意到每次是取矩阵中的最大值和最小值，那么就分两种情况：
1.最大值只有一个，那么最大值就应该放在（1，1）的位置，然后取max(n,m)，如果行数比列数大，那么最小值就放在(2,1)的位置，否则放在(1,2)的位置，然后第二小的值放在(2,1)/(1,2)剩下的位置
2.最小值只有一个，其实情况和最大值一样，至是一开始是最小值放在（1，1）的位置！
将两种情况取最大值即可

这里简单推到一下，因为是取矩阵的最大值和最小值，如果最大值和最小值已经在蓝色和红色的区域，那么剩下的值就会被随机放在其他位置。但会发现，绿色区域的值，永远都是数组b里面最大值-最小值。

这是情况1最大值只有1，而且列数比行数多，也就是说红色区域比蓝色区域大，那么最小值会放在(1,2)，如果随机取i，j，也就是紫色区域，那么从(0,0)到(i,j)的矩阵就是红蓝和橙色圈起来的，会发现该矩阵一定会包含最大值和最小值。证明结束。

反证(证明为什么如果列数比行数多，小一放在(1,2))：如果小一不放在(1,2)，那么(1，2)这个子矩阵的值是 最大值-n=ans1，如果是小一放在里面 ans2=最大值-小一，明显ans1<ans2，如果小一越“远离”(1,1)那么将会有更多的子矩阵的值比该方法小。而为什么不放(2,1)原因很简单，如下图，如果放在(1,2)将会有3个子矩阵是最大值，而放在(1,2)只有2个子矩阵是最大值！

C++

#include <iostream>
#include <algorithm>
#define int long long
using namespace  std;
const int N = 101 * 101 +101;
int a[N];
signed main(void){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=0;i<n*m;i++){scanf("%lld",&a[i]);}sort(a,a+n*m);int minans=a[0];int minans2=a[1];int maxans=a[n*m-1];int maxans2=a[n*m-2];int maxnm=max(n,m);int minnm=min(n,m);int ans=(maxnm-1)*(maxans-minans)+(minnm-1)*(maxans2-minans)+(n*m-n-m+1)*(maxans-minans);int ans2=(maxnm-1)*(maxans-minans)+(minnm-1)*(maxans-minans2)+(n*m-n-m+1)*(maxans-minans);cout<<max(ans,ans2)<<endl;}return 0;
}

C语言

#include <stdio.h>
#include <limits.h>
#define int long long
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
signed main(void){int t;scanf("%lld",&t);while(t--){int n,m;scanf("%lld%lld",&n,&m);int minans=LLONG_MAX;int minans2=LLONG_MAX;int maxans=LLONG_MIN;int maxans2=LLONG_MIN;int maxnm=max(n,m);int minnm=min(n,m);for(int i=0;i<n*m;i++){int num;scanf("%lld",&num);if(maxans<=num) {maxans2= maxans;maxans = num;}else if(maxans2<=num)maxans2= num;if(minans>=num) {minans2=minans;minans = num;}else if(minans2>=num)minans2=num;}int ans=(maxnm-1)*(maxans-minans)+(minnm-1)*(maxans2-minans)+(n*m-n-m+1)*(maxans-minans);int ans2=(maxnm-1)*(maxans-minans)+(minnm-1)*(maxans-minans2)+(n*m-n-m+1)*(maxans-minans);printf("%lld\n",max(ans,ans2));}return 0;
}