[CF 449A] Jzzhu and Chocolate

作法：

假設橫著切了$a$刀，直著切了$b$刀，那麼所求就會是$\left \lfloor \frac{n}{a+1} \right \rfloor\cdot \left \lfloor \frac{m}{b+1} \right \rfloor$，其中$a,b\geq 0$，並且$a+b=k$。可以先改成$\left \lfloor \frac{n}{x} \right \rfloor\cdot \left \lfloor \frac{m}{y} \right \rfloor$，其中$x,y\geq 1$，並且$x+y=k+2$，等等會比較好處理。枚舉所有的$x$顯然是不行的，而因為這條式子有高斯，所以可以用常見的優化方法，因為當上式中$x$慢慢增加時，$\left \lfloor \frac{n}{x} \right \rfloor$的值會在連續的區間保持不變。具體來說，設此時$\left \lfloor \frac{n}{x} \right \rfloor=q$，那麼不難證明$x$的值從$x$一直往上跑到$\left \lfloor \frac{n}{q} \right \rfloor$的話，$\left \lfloor \frac{n}{x} \right \rfloor$的值都會一直保持$q$，因此這段區間可以一起做。而$\left \lfloor \frac{m}{y} \right \rfloor$的部份因為$y$是往下跑的，這裡則可以推出$y$一直往下跑到$\left \lfloor \frac{m}{\left \lfloor \frac{m}{y} \right \rfloor+1} \right \rfloor+1$，因此只要對兩個可以一起做的區間取比較小的就可以了，類似的東西可以參考這篇。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    LL ans=0 ;
    for(int i=1;i<=n && i<=k+1;)
    {
        int x=i , y=k+2-i ;
        int x2=n/(n/i) , y2=m/(m/y+1)+1 ;
        ans=max(ans,(LL)(n/x)*(m/y)) ;
        i=min(x2,k+2-y2)+1 ;
    }
    printf("%lld\n",ans ? ans : -1) ;
}