ref https://paiza.jp/poh/paizen

jd.rb

# 仕様:
#  ホーム画面の領域を「field」とする。
#  fieldは[縦][横]の２次元配列。
#  fieldの各マスについて、配置できるウィジェットの高さ毎の最大横幅を持を格納した２次元配列を「fmap」とし、
#  縦幅と最大横幅ごとに配置可能なマスの数を集計したものを「wctable」とする。
#
#  ホーム画面に配置するウィジェットの属性を「widget」とし、その配列を「widgets」とする。
#
#  判定について
#    fieldのマスに対し、widgetをいくつ配置できるか判定する
#
# データ構造:
#    field[y][x] = 0 or 1
#    fmap[y][x] = {:max_height => n, widget_height => max_widget_width..}
#    wctable[widget_height][max_widget_width] = count
#    widget = [widget_height, widget_width]

def scanField()
    head = $stdin.readline.split
    h = head[0].to_i
    w = head[1].to_i
    field = $stdin.read(h * (w.succ)).split("\n").map do |row|
        row.split("").map(&:to_i)
    end

    fmap = []
    (h-1).downto(0).each do |y|
        fmap[y] = []
        (w-1).downto(0).each do |x|
            fmap[y][x] = searchMaxWidthes(
                field[y][x],
                fmap[y][x+1],
                if fmap[y+1] != nil && fmap[y+1][x][:max_height] != nil then 
                    fmap[y+1][x][:max_height] else 0 end,
                h - y)
        end
    end
    fmap
end

def searchMaxWidthes(value, right_value, bottom_max_height, count_y)
    hs = {}
    if value == 1
        hs[:max_height] = 0
    elsif right_value == nil || right_value[:max_height] == 0
        max_height = bottom_max_height + 1
        hs = fillMap(max_height, 1)
        hs[:max_height] = max_height
    else
        max_height = bottom_max_height + 1
        hs = headPlusMap(right_value, max_height)
        hs[:max_height] = max_height
    end
    hs
end

def fillMap(size, value)
    hs = {}
    (1..size).each do |i|
        hs[i] = value
    end
    hs
end

def headPlusMap(srcMap, size)
    hs = {}
    (1..size).each do |i| 
        if srcMap[i] == nil
            hs[i] = 1
        else
            hs[i] = srcMap[i] + 1
        end
    end
    hs
end

def scanWidgets()
    n = $stdin.readline.chomp.to_i
    widgets = Array.new(n)
    lines = $stdin.read.split
    offset = 0
    n.times {|i|
        widgets[i] = [
            lines[offset].to_i,
            lines[offset.succ].to_i
        ]
        offset = offset.succ.succ
    }
    widgets
end

def countWidgets(fmap)
    wctable = []
    fmap.each do |row|
        row.each do |cell|
            (1..cell[:max_height]).each do |h|
                max_widget_width = cell[h]
                wctable[h] = [] if wctable[h] == nil
                if wctable[h][max_widget_width] == nil
                    wctable[h][max_widget_width] = 1
                else
                    wctable[h][max_widget_width] += 1
                end
            end
        end
    end
    wctable
end

# MAIN
begin
    fmap = scanField
    widgets = scanWidgets
    wctable = countWidgets(fmap)

    result = ""
    widgets.each do |widget|
        widget_height, widget_width = widget
        count = 0
        max_widget_width = 0
        max_widget_width = wctable[widget_height].size if wctable[widget_height] != nil
        (widget_width..max_widget_width).each do |w|
            count += wctable[widget_height][w] if wctable[widget_height][w] != nil
        end
        result << count.to_s << "\n"
    end
    print result
end

result of rev6 https://paiza.jp/poh/paizen/result/e2fe88c724b3446157910e2924ed9654

■結果
　提出言語：Ruby
　得点：100 点

　結果：
　テストケース1：success　0.01秒
　テストケース2：success　0.01秒
　テストケース3：success　0.03秒
　テストケース4：success　0.06秒
　テストケース5：success　0.2秒
　テストケース6：success　0.41秒
　テストケース7：success　0.74秒

※アルゴリズムを根本的に見直した。