Submission #1691944

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


long long vh(long long H, long long W)
{
  long long dp = INF;
  
  for (int i = -500; i < 500; i ++) {
    long long W1 = W / 3 + i, W2 = W - W1;

    if (W1 < 0 || W2 < 0)
      continue;

    for (int j = -500; j < 500; j ++) {
      long long H1 = H / 2 + j, H2 = H - H1;

      if (H1 < 0 || H2 < 0)
        continue;

      std::vector<long long> A = {
        H  * W1,
        H1 * W2,
        H2 * W2
      };

      assert(A[0] + A[1] + A[2] == H * W);

      std::sort(ALL(A));

      dp = std::min(A[2] - A[0], dp);
    }
  }

  return dp;
}

long long vv(long long H, long long W)
{
  long long dp = INF;
  
  for (int i = -500; i < 500; i ++) {
    long long W1 = W / 3 + i, WW = W - W1;

    if (W1 < 0 || WW < 0)
      continue;

    for (int j = -500; j < 500; j ++) {
      long long W2 = WW / 2 - j, W3 = WW - W2;

      if (W2 < 0 || W3 < 0)
        continue;

      std::vector<long long> A = {
        H * W1,
        H * W2,
        H * W3
      };

      assert(A[0] + A[1] + A[2] == H * W);

      std::sort(ALL(A));

      dp = std::min(A[2] - A[0], dp);
    }
  }

  return dp;
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int H, W;

  std::cin >> H >> W;

  long long dp = INF;

  dp = std::min(dp, vh(H, W));
  dp = std::min(dp, vv(H, W));

  std::swap(H, W);

  dp = std::min(dp, vh(H, W));
  dp = std::min(dp, vv(H, W));

  std::cout << dp << std::endl;

  return 0;
}

Submission Info

Judge Result