Codeforces Round #257 (Div. 2) C. Jzzhu and Chocolate
1 second
256 megabytes
standard input
standard output
Jzzhu has a big rectangular chocolate bar that consists of n × m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:
- each cut should be straight (horizontal or vertical);
- each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);
- each cut should go inside the whole chocolate bar, and all cuts must be distinct.
The picture below shows a possible way to cut a 5 × 6 chocolate for 5 times.
Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactly k cuts? The area of a chocolate piece is the number of unit squares in it.
A single line contains three integers n, m, k (1 ≤ n, m ≤ 109; 1 ≤ k ≤ 2·109).
Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.
3 4 1
6
6 4 2
8
2 3 4
-1
In the first sample, Jzzhu can cut the chocolate following the picture below:
In the second sample the optimal division looks like this:
In the third sample, it's impossible to cut a 2 × 3 chocolate 4 times.
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include<vector>
#include<map>
#include<deque>
#include<list>
using namespace std;
#define M 1000000007
__int64 n,m;
__int64 f(__int64 a, __int64 b)
{
if(a< || b<) return ;
return max((n/(a+))*(m/(b+)), (n/(b+))*(m/(a+)));
} int main()
{
__int64 k,ans=; scanf("%I64d%I64d%I64d",&n, &m, &k); if(k>n+m-) printf("-1\n");
else if(k==n+m-) printf("1\n");
else
{
ans=max(ans, f(, k));
ans=max(ans, f(m-, k-m+));
ans=max(ans, f(n-, k-n+));
printf("%I64d\n", ans);
} return ;
}
最新文章
- 切换npm源
- bootstrap 之 xs,sm,md,lg &;&; 主要颜色
- Mono登录界面记住密码的控件
- Makefile 开发环境全能管家
- 传奇的通迅协议与base64算法
- C++ Frequently asking question
- 第二百三十六天 how can I 坚持
- UVA 11396 Claw Decomposition(二分图)
- Java多线程(五) Lock接口,ReentranctLock,ReentrantReadWriteLock
- Castle Windsor Fluent Registration API
- asp.net+Sqlserver 通过存储过程读取数据
- google反向代理网址收集
- CloudStack API访问权限控制
- Azure上如何在Linux下挂载数据磁盘
- 组合,关联,聚合的区别(转自http://jimmyleeee.blog.163.com/blog/static/9309618200932014422932/)
- C# Note38: Export data into Excel
- NFine框架全选checkBox列错位
- lombok插件:Data自动get/set方法, Slf4j实现Logger的调用
- java多线程和Calendar(日历)常用API
- C语言中的控制语句: 判断、环循等;