ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

Codeforces 449A : Jzzhu and Chocolate

概要


問題文はこちら
http://codeforces.com/problemset/problem/449/A

チョコレートを割って複数個の欠片を作る。
その欠片の最小値を最大化する問題。

解法


(あんまり納得はできてないけど)縦と横の両方から割るよりは片側から割りまくったほうが良いっぽい。

可能な限り片方向から割っていく方針で解くことができる。

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;

lli n, m, k;

int main() {
  // ios_base::sync_with_stdio(false);
  
  cin >> n >> m >> k;
  
  if(n + m - 2 < k) cout << "-1" << endl;
  else {
    lli ans = 0;
    
    if(k < n) ans = max(ans, n / (k + 1) * m);
    else ans = max(ans, m / (k + 1 - n + 1));
    if(k < m) ans = max(ans, m / (k + 1) * n);
    else ans = max(ans, n / (k + 1 - m + 1));

    cout << ans << endl;
  }

  return 0;
}