自动搬运

查看原文

来自洛谷，原作者为

	彭天宇 高效太重要了，也太难了

搬运于2025-08-24 21:34:50，当前版本为作者最后更新于2020-11-23 21:08:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

基础计数类、基础数学思维类好题。

一看这$n,m\le 30000$就不是$O(n^2)$的算法，又不像是$O(n)$的，怎么办？慢慢分析。

首先，如果面对下面一种情况（一个$o$对应一个石子）：

$oooo$

$oooo$

$ooo$

要再放一个石子进去，应该如何放？当然要补在缺口处。这样新放上去的石子就可以和9个位置的石子组成矩形，然而放在别的位置都不能。（证明略）

所以结论就是：将石子阵摆成接近矩形，只有一个缺口的时候最优。

一个矩形石子阵$(n\times m)$可以有多少不同矩形呢？

就是说有两次求和个矩形右下角可以选择，每一个右下角有$i\times j$个左上角与之对应，这样就不重不漏了。

化简一下：

好了，那就用类似二维前缀和的方法计算一个不是矩形的石子阵就好了。

注意$3\times 3$的石子阵长和宽都只能以$2$带入上面的式子，为什么？请审题。

最后要做的就是枚举不完全矩阵的长度，分别计算。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
	int maxn=0;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		if(k/i>=m)continue;
		int len=k/i;
		int mod=k%i;
		maxn=max(maxn,(i*(i-1)/2*len*(len-1)/2+(len+1)*len/2*mod*(mod-1)/2-(len*(len-1)/2*mod*(mod-1)/2)));
	}
	for(int i=1;i<=m;i++){
		if(k/i>=n)continue;
		int len=k/i;
		int mod=k%i;
		maxn=max(maxn,(i*(i-1)/2*len*(len-1)/2+(len+1)*len/2*mod*(mod-1)/2-(len*(len-1)/2*mod*(mod-1)/2))); 
	}
	cout<<maxn<<endl;
	return 0;
}