Intermediate.
Put your skills to the test.

Problem summary

Partition an m×n chocolate into exactly k nonempty rectangles along grid lines. Maximize the largest piece area.

Constraints

1≤m,n,k≤1000000; k≤mn.

Worked example

Input and output for the worked example discussed below.

4 5 4

16

Solution analysis

1. The other k−1 pieces each need a unit cell, so the largest area is at most limit=mn−k+1. Its integer sides must also fit the chocolate.
2. For every width w, choose height min(n,floor(limit/w)). For k≥3 put this rectangle at a corner; the complement consists of at most two rectangles and can be split further to exactly k−1 pieces.
3. Handle k=1 as the whole chocolate and k=2 as a straight cut with best area max((m−1)n,m(n−1)). For 4×5,k=4, retain a 4×4 piece and split its four-cell complementary strip into three pieces, giving 16.

Why it works

The reserve bound is necessary. For k≥3 the complement starts with one or two rectangles and can increase its piece count one at a time until all its unit cells are separate. Thus each positive candidate satisfying the reserve bound is realizable. Taking the best allowed height at every width finds the optimum. The special k=1,2 cases are exact directly.

Watch out. k counts final pieces, not cuts. The reserve bound need not itself factor into fitting side lengths.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    long long m;
    long long n;
    long long k;
    cin>>m>>n>>k;
    if(k==1){
        cout<<m*n<<'\n';
        return 0;
    }
    if(k==2){
        cout<<max((m-1)*n,m*(n-1))<<'\n';
        return 0;
    }
    if(m>n){
        swap(m,n);
    }
    long long limit=m*n-k+1;
    long long answer=0;
    for(long long width=1;width<=m;width++){
        // Reserve a unit cell for each other piece.
        long long height=min(n,limit/width);
        answer=max(answer,width*height);
    }
    cout<<answer<<'\n';
}