つーさのくーかん

http://tu3.jp/0897 の続き。

昨晩なんかTwitterで微妙にICPCっぽい話が出た気がしたので、
アジアの問題読んでみようとか思う前に国内途中だったの思い出して。

Eをよく考えてみたら、停電させる区画の選び方って、
X*Y*W*Hだから104万通りしかないのね。
あとはどうちょん切るかで、もしかして分割統治法いける？

で、書いてみたら微妙にTLEっぽい。
後、区画内の総需要求めるとこが毎回馬鹿正直にぐるぐる回ってるので、
たぶん、ここをもうちょっと直したらいいと思うんだけどよくわからん。

ねむい。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Diagnostics;

namespace E
{
  using Result = Point;
  class Program
  {
    static void Main(string[] args)
    {
      while (true)
      {
        int[] head = Array.ConvertAll(Console.ReadLine().Split(' '), d => int.Parse(d));
        int H = head[0], W = head[1], S = head[2];
        if (H == 0 && W == 0 && S == 0)
          break;

        List<List<int>> map = new List<List<int>>();
        for (int i = 0; i < H; i++)
          map.Add((from d in Console.ReadLine().Split(' ') select int.Parse(d)).ToList());

        var totalDemand = (from l in map select l.Sum()).Sum();
        var lack = totalDemand - S;

        Converter<Rectangle, int> cnv = r => ((((r.X) << 5 | r.Y) << 6 | r.Width) << 6 | r.Height);
        Result[] cache = new Result[1048576 * 4];

        Func<Rectangle, Result> f = null;
        f = r =>
        {
          if (cache[cnv(r)] != Result.Empty)
            return cache[cnv(r)];

          // 区画内総需要
          int areaDemand = 0;
          for (int y = r.Top; y < r.Bottom; y++)
            for (int x = r.Left; x < r.Right; x++)
              areaDemand += map[y][x];

          // この区画は実現できん。
          if (areaDemand < lack)
            return cache[cnv(r)] = new Result(-99999999, 0);

          // 分割してみる。
          var cur = new Result(1, areaDemand - lack);
          Action<Rectangle, Rectangle> trySplit = (r1, r2) =>
          {
            Result a1 = f(r1), a2 = f(r2);
            int splits = a1.X + a2.X, excess = Math.Min(a1.Y, a2.Y);
            if (cur.X < splits || cur.X == splits && cur.Y < excess)
              cur = new Result(splits, excess);
          };

          for (int x = 1; x < r.Width; x++)
            trySplit(new Rectangle(r.X, r.Y, x, r.Height),
              new Rectangle(r.X + x, r.Y, r.Width - x, r.Height));

          for (int y = 1; y < r.Height; y++)
            trySplit(new Rectangle(r.X, r.Y, r.Width, y),
              new Rectangle(r.X, r.Y + y, r.Width, r.Height - y));

          return cache[cnv(r)] = cur;
        };
        
        Result result = f(new Rectangle(0, 0, W, H));
        Console.WriteLine("" + result.X + " " + result.Y);
      }
    }
  }
}