ARC 074 C - Chocolate Bar ( Ad hoc )

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder

題意：
把巧克力沿著線切，分成三個非空的塊。
問最大和最小的塊的面積差最小是多少。

制約：
2 ≤ H, W ≤ 1e5

解法：
只可能有兩種切法 | | | 或 | -。90 度旋轉再做一樣的事情。
第一刀切下去之後顯然剩下的要盡量對半切。

複雜度：
O( H + W )

#include <bits/stdc++.h>
using namespace std;
 
int H, W;
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> H >> W;
  long long ans = 1LL << 60;
  for( int _ = 0; _ < 2; ++_ ) {
    for( int i = 1; i <= H - 1; ++i ) {
      ans = min( ans, max( 1LL * i * W - 1LL * W / 2 * ( H - i ), 1LL * ( W + 1 ) / 2 * ( H - i ) - 1LL * i * W ) ) ;
      if( H - i > 1 ) {
        ans = min( ans, max( 1LL * i * W - 1LL * ( H - i ) / 2 * W, 1LL * ( H - i + 1 ) / 2 * W - 1LL * i * W ) );
      }
    }
    swap( H, W );
  }
  cout << ans << endl;
  return 0;
}