Codeforces #257 Div1 A. Jzzhu and Chocolate

CF#257に参加。ABを解いたと思ったらどっちも落とした。
Aを落とした分Hackで稼いだけど、レートをだいぶ暴落させて黄色に戻ってしまった。
http://codeforces.com/contest/449/problem/A

問題

縦Nx横Mのグリッドがある。
このグリッドに沿ってK本の直線を入れてグリッドを分割する。
最小のグリッドの面積を最大化せよ。

解法

横にa本、縦にK-a本線を引くと、答えは概ね(N/(a+1))*(M/*1<=(N*M)/*2となる。
(a+1)*(K-a+1)を小さくするには、横か縦かどちらかに線を集中させた方が良い。

よってどちらかに線を集中させたときの最大値を答えるだけ。

ll N,M,K;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	if((N-1)+(M-1)<K) return _P("-1\n");
	
	ll ma=max(M*(N/(K+1)),N*(M/(K+1)));
	if(N<=K+1) ma=max(ma,M/(K-(N-1)+1));
	if(M<=K+1) ma=max(ma,N/(K-(M-1)+1));
	
	cout << ma << endl;
}

まとめ

aの数に対し最小グリッドの面積は下に凸になるので、aを大きい方か小さい方に極振りした方が良い。
本番なぜか逆に凸の頂点を求めてしまった…。

*1:K-a)+1

*2:a+1)*(K-a+1