PKU 2951 Cake cutting

w*hのケーキをm個の長方形に分割。
w,h,m<=20
まあDPやるだけです
3分探索を入れてかっこつけましたが普通に3分探索しなくても通ると思います
（実は毎回計算しててTLEだったので無理やり3探いれましたごめんなさい）

int main(){	
	REP(i,21) REP(j,21) REP(k,21) dp[i][j][k]=INF;
	REP(i,21) REP(j,21) dp[i][j][1]=i*j;
		REPN(i,21,1) REPN(j,21,1) REPN(k,21,2){
			int &r=dp[i][j][k];
			for(int i2=1;i2<=i/2;++i2){
				int ub=k,lb=0;
				while(ub-lb>2){
					int fr=(ub-lb)/3+lb,sc=(ub-lb)/3*2+lb;
					int left=max(dp[i2][j][fr],dp[i-i2][j][k-fr]),
						right=max(dp[i2][j][sc],dp[i-i2][j][k-sc]);
					if(right>left)
						ub=sc;
					else lb=fr;
				}
				lb=(lb+ub)/2;
				r=min(r,max(dp[i2][j][lb],dp[i-i2][j][k-lb]));
			}
			for(int i2=1;i2<=j/2;++i2){
				int ub=k,lb=0;
				while(ub-lb>2){
					int fr=(ub-lb)/3+lb,sc=(ub-lb)/3*2+lb;
					int left=max(dp[i][i2][fr],dp[i][j-i2][k-fr]),
						right=max(dp[i][i2][sc],dp[i][j-i2][k-sc]);
					if(right>left)
						ub=sc;
					else lb=fr;
				}
				lb=(lb+ub)/2;
				r=min(r,max(dp[i][i2][lb],dp[i][j-i2][k-lb]));
			}
		}
	int w,h,m;
	while(scanf("%d%d%d",&w,&h,&m) && (w||h||m)){
		printf("%d\n",dp[w][h][m]);
	}
	return 0;
}