Program.cs

using System;
using System.IO;

namespace paizen
{
    class Program
    {
        const int NewLine = 10;
        const int Space = 32;
        const int ZeroChar = 48;

        static int ReadInt(Stream stream)
        {
            var chars = new int[6]; //最大値は 300*300
            var count = 0;
            while (true)
            {
                var b = chars[count] = stream.ReadByte();
                if (b == NewLine || b == Space) break;
                count++;
            }
            var tmp = 1;
            var result = chars[count - 1] - ZeroChar;
            for (var i = 2; i <= count; i++)
            {
                tmp *= 10;
                result += tmp * (chars[count - i] - ZeroChar);
            }
            return result;
        }

        static void ReadLineAsBytes(Stream stream, int[] result)
        {
            var i = 0;
            while ((result[i++] = stream.ReadByte()) != NewLine)
            { }
        }

        static void Main(string[] args)
        {
            const int bufsize = int.MaxValue / 100;
            var buffer = new byte[bufsize];
            using (var inStream = Console.OpenStandardInput(bufsize))
            {
                inStream.Read(buffer, 0, bufsize);
            }
            using (var inStream = new MemoryStream(buffer))
            using (var outStream = Console.OpenStandardOutput(bufsize))
            {
                var h = ReadInt(inStream);
                var w = ReadInt(inStream);

                var points = new bool[w, h];
                for (var y = 0; y < h; y++)
                {
                    var line = new int[w + 1];
                    ReadLineAsBytes(inStream, line);
                    for (var x = 0; x < w; x++)
                    {
                        points[x, y] = line[x] == ZeroChar;
                    }
                }

                var cache = new int[h][]; //縦方向の連続の空き
                for (var y = 0; y < h; y++)
                {
                    var cache_x = new int[w];
                    for (var x = 0; x < w; x++)
                    {
                        var count = 0;
                        for (var test_y = y; test_y < h; test_y++)
                        {
                            if (!points[x, test_y]) break;
                            count++;
                        }
                        cache_x[x] = count;
                    }
                    cache[y] = cache_x;
                }

                var n = ReadInt(inStream);

                for (var _ = 0; _ < n; _++)
                {
                    var wid_h = ReadInt(inStream);
                    var wid_w = ReadInt(inStream);
                    var count = 0;

                    if (wid_h <= h && wid_w <= w)
                    {
                        for (var x = 0; x <= w - wid_w; x++)
                        {
                            for (var y = 0; y <= h - wid_h; y++)
                            {
                                var flag = true;
                                var max_x = x + wid_w;
                                var cache_x = cache[y];
                                for (var test_x = x; flag && test_x < max_x; test_x++)
                                {
                                    flag = cache_x[test_x] >= wid_h;
                                }
                                if (flag) count++;
                            }
                        }
                    }

                    var writeBuf = new byte[6];
                    int i;
                    if (count < 10)
                    {
                        i = 1;
                        writeBuf[0] = (byte)(count + ZeroChar);
                    }
                    else if (count < 100)
                    {
                        i = 2;
                        int rem;
                        writeBuf[0] = (byte)Math.DivRem(count, 10, out rem);
                        writeBuf[1] = (byte)rem;
                    }
                    else if (count < 1000)
                    {
                        i = 3;
                        int rem;
                        writeBuf[0] = (byte)Math.DivRem(count, 100, out rem);
                        writeBuf[1] = (byte)Math.DivRem(rem, 10, out rem);
                        writeBuf[2] = (byte)rem;
                    }
                    else if (count < 10000)
                    {
                        i = 4;
                        int rem;
                        writeBuf[0] = (byte)Math.DivRem(count, 1000, out rem);
                        writeBuf[1] = (byte)Math.DivRem(rem, 100, out rem);
                        writeBuf[2] = (byte)Math.DivRem(rem, 10, out rem);
                        writeBuf[3] = (byte)rem;
                    }
                    else
                    {
                        i = 5;
                        int rem;
                        writeBuf[0] = (byte)Math.DivRem(count, 10000, out rem);
                        writeBuf[1] = (byte)Math.DivRem(rem, 1000, out rem);
                        writeBuf[2] = (byte)Math.DivRem(rem, 100, out rem);
                        writeBuf[3] = (byte)Math.DivRem(rem, 10, out rem);
                        writeBuf[4] = (byte)rem;
                    }
                    writeBuf[i] = NewLine;
                    outStream.Write(writeBuf, 0, i + 1);
                }
            }
        }
    }
}