SRM547 Div1 Medium

500

式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?

サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S

const lli inf = 1LL << 60;

inline
bool valid(lli S, lli i, lli j, lli W, lli H)
{
  if (i <= H && j <= W) ; else return false;

  const lli ij = i * j;
  lli x = 2LL * S / ij;
  x -= (j - 1);
  x -= W * (i - 1);
  if (x < 0 || x % 2LL) return false;
  x /= 2LL;

  return x % W + j <= W && x / W + i <= H;
}

class RectangularSum {
public:
  long long minimalArea(int height, int width, long long S)
  {
    lli mn = inf;
    for (lli m = 1; m * m <= 2LL * S; ++m) {
      if (2LL * S % m) continue;
      lli ij[2] = {m, 2LL * S / m};

      for (int l = 0; l < 2; ++l) {
        if (ij[l] < mn) ; else continue;
        for (lli k = 1; k * k <= ij[l]; ++k) {
          if (ij[l] % k) continue;
          lli i, j;

          i = k;
          j = ij[l] / k;
          if (valid(S, i, j, width, height)) mn = min(mn, i * j);

          i = ij[l] / k;
          j = k;
          if (valid(S, i, j, width, height)) mn = min(mn, i * j);
        }
      }
    }
    return mn == inf ? -1 : mn;
  }
};