Problem:


長方形探索

 縦に H 行、横に W 列並べられた、合計 W &times; H のマス目があります。いくつかのマス目には印がついています。各マス目の印の状態を読み込み、印のついていないマス目だけからなる最大の長方形の面積を出力するプログラムを作成してください。 

入力データは 1 行 W 文字から構成され、H 行が与えられます。たとえば以下のようなデータが与えられます。

..*....**.
..........
**....***.
....*.....
..*.......
...**.....
.*.*......
..........
..**......
.*..*.....

 入力データの一行が、一行のマス目を表現します。入力データの文字列のうち、. (ピリオド) は印のついていないマス目、* (アスタリスク) は印のついているマス目を示しています。入力データの文字列には、ピリオド、アスタリスク、改行以外の文字は含まれません。

 上記の例では、下図の 0 で示される長方形が最大となります。

..*....**.
..........
**....***.
....*00000
..*..00000
...**00000
.*.*.00000
.....00000
..**.00000
.*..*00000

よって、35 と出力すれば正解になります。なお、すべてのマス目に印がついている場合には、0 を出力してください。

Input

複数のデータセットが与えられます。各データセットはスペースで区切られた H と W からなる行から始まり、つづいて H &times; W の長方形が与えられます。H, W はともに 500　以下とします。

入力は２つの 0 を含む行で終わります。データセットの数は 20 を超えません。

Output

各データセットごとに、最大の長方形の面積を１行に出力してください。

Sample Input

10 10
...*....**
..........
**....**..
........*.
..*.......
**........
.*........
..........
....*..***
.*....*...
10 10
..*....*..
.*.*...*..
*****..*..
*...*..*..
*...*..*..
..........
****.*...*
..*..*...*
.*...*...*
****..***.
2 3
...
...
0 0

Output for the Sample Input

28
12
6



Sample input:
10 10
...*....**
..........
**....**..
........*.
..*.......
**........
.*........
..........
....*..***
.*....*...
10 10
..*....*..
.*.*...*..
*****..*..
*...*..*..
*...*..*..
..........
****.*...*
..*..*...*
.*...*...*
****..***.
2 3
...
...
0 0


Sample output:
28
12
6

Submission status: Memory Limit Exceeded

Solution code:
def dotHeight(y,x):
    cnt=0
    for i in range(y,-1,-1):
        if L[i][x]=="*":
            return cnt
        cnt+=1

def dotLength(y,x):
    cnt=0
    for i in range(x,-1,-1):
        if L[y][i]=="*":
            return cnt
        cnt+=1

while True:
    H,W=map(int,raw_input().split())
    if H==W==0:break
    L=[["*"]+list(raw_input())+["*"] for i in range(H)]
    L.append(["*"]*(W+2))
    L.insert(0,["*"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]==".":
                if L[i-1][j]==L[i][j-1]=="*":
                    dp[i][j].add((1,1))
                elif L[i-1][j]=="*":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                elif L[i][j-1]=="*":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                else:
                    h=dotHeight(i,j)
                    l=dotLength(i,j)
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,min(k[1],h)))
                    for k in dp[i-1][j]:
                        dp[i][j].add((min(k[0],l),k[1]+1))
    maxInt=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in dp[i][j]:
                maxInt=max(maxInt,k[0]*k[1])
    print maxInt

Submission status: Accepted

Solution code:
# ref: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=924554#1
from itertools import product
while(True):
    H,W = map(int,input().split())
    if not H: break
    ma = [list(map(int,input().replace(".","1").replace("*","0")))+[0] for _ in range(H)]
    for i,j in product(range(1,H),range(W)):
        if ma[i][j]: ma[i][j] += ma[i-1][j]
    ans = 0
    for i in range(H):
        stk = []
        for j in range(W+1):
            cur = ma[i][j]
            if (not stk) or stk[-1][1] < cur:
                stk.append([j,cur])
            elif stk[-1][1] > cur:
                idx = j
                while stk and stk[-1][1] >= cur:
                    idx = stk[-1][0]
                    ans = max(ans,stk[-1][1]*(j-stk[-1][0]))
                    stk.pop()
                stk.append([idx,cur])
    print(ans)

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*":
        c=0
      elif x[j]==".":
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b[:]
  s=0
  for i in range(h+1):
    s=max(s,M[i]*i)
  print s

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = list(raw_input())
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*":
        c=0
      elif x[j]==".":
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b[:]
  s=0
  for i in range(h+1):
    s=max(s,M[i]*i)
  print s

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = map(int,list(raw_input().replace("*","0").replace(".","1")))
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]==0:
        c=0
      elif x[j]==1:
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b[:]
  s=0
  for i in range(h+1):
    s=max(s,M[i]*i)
  print s

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*":
        c=0
      elif x[j]==".":
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b[:]
  s=max([a*b for a,b in zip(M,range(h+1))])
  print s

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, H+[h])])
  print s

Submission status: Accepted

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s

Submission status: Accepted

Solution code:
while True:
  h, w = map(int, input().split())
  if h == 0:
    break

  mp = []
  for _ in range(h):
    lst = list(input())
    cum = []
    acc = 0
    for i in lst:
      acc = acc + 1 if i == "." else 0
      cum.append(acc)
    mp.append(cum)
  mp.append([-1] * w)
  
  ans = 0
  for i in range(w):
    stack = []
  
    for j in range(h + 1):
      score = mp[j][i]
  
      if not stack:
        stack.append((score, j))
  
      else:
        last_score, last_ind = stack[-1][0], stack[-1][1]
        if score > last_score:
          stack.append((score, j))
        
        elif score == last_score:
          continue
        
        else:
          while stack != [] and stack[-1][0] >= score:
            last_score, last_ind = stack.pop()
            ans = max(ans, last_score * (j - last_ind))
          stack.append((score, last_ind))
  
  print(ans)

Submission status: Accepted

Solution code:
# Rectangular Searching

from collections import deque

while True:
    h, w = map(int, raw_input().split())
    if (h, w) == (0, 0):
        break

    g = []
    for i in range(h):
        g.append([1 if c == '.' else 0 for c in raw_input()] + [0])

    for i in range(1, h):
        for j in range(w):
            if g[i][j] != 0:
                g[i][j] = g[i - 1][j] + 1

    stack = deque()
    area = 0
    for i in range(h):
        for j in range(w + 1):
            if len(stack) == 0:
                stack.append((j, g[i][j]))
            else:
                if stack[-1][1] < g[i][j]:
                    stack.append((j, g[i][j]))
                elif stack[-1][1] > g[i][j]:
                    idx = j
                    while len(stack) != 0 and stack[-1][1] >= g[i][j]:
                        prev = stack.pop()
                        idx = prev[0]
                        area = max(area, prev[1] * (j - idx))
                    stack.append((idx, g[i][j]))

    print area

Submission status: Accepted

Solution code:
# Rectangular Searching

from collections import deque

while True:
    h, w = map(int, raw_input().split())
    if (h, w) == (0, 0):
        break

    g = []
    for i in range(h):
        g.append([1 if c == '.' else 0 for c in raw_input()] + [0])

    for i in range(1, h):
        for j in range(w):
            if g[i][j] != 0:
                g[i][j] = g[i - 1][j] + 1

    stack = deque()
    area = 0
    for i in range(h):
        for j in range(w + 1):
            curr = g[i][j]
            if len(stack) == 0:
                stack.append((j, curr))
            else:
                if stack[-1][1] < curr:
                    stack.append((j, curr))
                elif stack[-1][1] > curr:
                    idx = j
                    while len(stack) != 0 and stack[-1][1] >= curr:
                        prev = stack.pop()
                        idx = prev[0]
                        area = max(area, prev[1] * (j - idx))
                    stack.append((idx, curr))

    print area

Submission status: Accepted

Solution code:
def re_push(stack,num):#re_push and return max
    count = 0
    pre = num
    ma = 0
    while True:
        count += 1
        cur = stack.pop()
        if cur <= num:
            ma = max(ma,(count-1) * pre)
            stack += [cur]
            stack += [num]*(count-1)
            break
        if cur < pre:
            ma = max(ma,(count-1) * pre)
            stack += [cur]*count
            count = 0
        pre = cur
    return ma
            
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    table = [[0]*(W+1) for _ in xrange(H)]
    for y in xrange(H-1,-1,-1):
        for x in (x for x in xrange(W-1,-1,-1) if field[y][x] != "*"):
            table[y][x] = table[y][x+1] + 1
    ma = 0
    for x in xrange(W):
        stack = [0,table[0][x]]
        for y in xrange(1,H):
            if table[y-1][x] > table[y][x]:
                ma = max(ma, re_push(stack,table[y][x]))
            stack.append(table[y][x])
        ma = max(ma, re_push(stack,0))
    print ma

Submission status: Accepted

Solution code:
def histogram(mass, h, w):
    table = [[0]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if mass[i][j] == '*':
                table[i][j] = 0
            else:
                table[i][j] = table[i-1][j] + 1
    return table


def get_rectangle_area(table, w):
    maxv = 0
    stack = []
    table.append(0)
    for i, rect in enumerate(table):
        if stack == []:
            stack.append((rect, i))
        elif stack[-1][0] < rect:
            stack.append((rect, i))
        elif stack[-1][0] == rect:
            pass
        elif stack[-1][0] > rect:
            while stack != [] and stack[-1][0] >= rect:
                high, pos = stack.pop()
                maxv = max(maxv, high*(i-pos))
            stack.append((rect, pos))
    return maxv

while True:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break
    mass = [raw_input() for i in range(h)]
    table = histogram(mass, h, w)
    ans = 0
    for tab in table:
        ans = max(ans, get_rectangle_area(tab, w))
    print ans

Submission status: Accepted

Solution code:
while 1:
    H,W = map(int,raw_input().split())
    if H == 0: break
    A = [raw_input() for i in range(H)]
    S = [[[0,0] for j in range(W)] for i in range(H)]
    ans = 0
    for h in range(H):
    	L = 0
        for w in range(W):
            if A[h][w] == ".":
                L += 1
            else:
                L = 0
            S[h][w][0] = L
            try: S[h][w][1] = S[h-1][w][1] + 1 if L > 0 else 0
            except: S[h][w][1] = 1 if L > 0 else 0
            if L*S[h][w][1] > ans:
                a = L
                for hi in range(1,S[h][w][1]):
                    a = min(a,S[h-hi][w][0])
                    ans = max(ans,a*(hi+1))
                    if a*S[h][w][1] < ans:
                    	break
    print ans

Submission status: Accepted

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			try: B[h][w] = B[h-1][w] + 1 if L > 0 else 0
			except: B[h][w] = 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = L
				for hi in range(B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Accepted

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	if sum([M[h].count(".") for h in range(H)]) == 0:
		print 0
		continue
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 1
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = L
				for hi in range(B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Accepted

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				for hi in range(B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Accepted

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = L
				for hi in range(B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int, input().split())
    if H == 0:
        return False
    MP = [input() for i in range(H)]
    C = [[0]*W for i in range(H)]
    for j in range(W):
        cnt = 0
        for i in range(H-1, -1, -1):
            if MP[i][j] == '.':
                cnt += 1
            else:
                cnt = 0
            C[i][j] = cnt
    ans = 0
    for i in range(H):
        st = [(0, -1)]
        for j in range(W):
            e = C[i][j]
            last = j
            while st and e <= st[-1][0]:
                f, k = st.pop()
                ans = max(ans, (j - k) * f)
                last = k
            st.append((e, last))
        while st:
            f, k = st.pop()
            ans = max(ans, (W - k) * f)
    print(ans)
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Rectangular Searching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116

"""
import sys


def solve(m, height, width):
    def calc_hist(m):
        hist = [[0]* width for _ in range(height)]
        for y, row in enumerate(m):
            for x, ch in enumerate(row):
                if ch == '.':
                    hist[y][x] = hist[y-1][x]+1 if y >0 else 1
        return hist

    def calc_area(hist):
        stack = []
        area = 0
        for x, h in enumerate(hist):
            if not stack or stack[-1][0] < h:
                stack.append((h, x))
            elif stack[-1][0] > h:
                while stack and stack[-1][0] >= h:
                    hh, left = stack.pop()
                    area = max(area, hh*(x-left))
                stack.append((h, left))
        return area

    hist = calc_hist(m)
    ans = 0
    for y in range(height):
        ans = max(ans, calc_area(hist[y]+[0])) #  [0]はヒストグラムを最後にリフレッシュして処理するために必要
    return ans


def main(args):
    while True:
        height, width = map(int, input().split())
        if height == 0 or width == 0:
            break
        m = [input() for _ in range(height)]
        ans = solve(m, height, width)
        print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  A = []
  for i in range(h):
    A.append(map(int,list(raw_input().replace(".", "1").replace("*", "0"))))
  B = A[:]
  C = []
  for j in range(1,h):
    m=[]
    for i in range(j,h):
      x=[e1&e2 for e1,e2 in zip(B[i-j],A[i])]
      B[i-j]=x
      m.append(max("".join(map(str,x)).split("0")))
    C.append(len(max(m))*(j+1))
  print max(C)

Submission status: Runtime Error

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  A = []
  for i in range(h):
    A.append(map(int, list(raw_input().replace(".", "1").replace("*", "0"))))
  B = A[:]
  C = []
  for j in range(1,h):
    m=[]
    for i in range(j,h):
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x
      m.append(max("".join(map(str, x)).split("0")))
    C.append(len(max(m))*(j+1))
  print max(C)

Submission status: Runtime Error

Solution code:
import sys
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  A = []
  for _ in [0]*h:
    A.append(map(int, list(raw_input().replace(".", "1").replace("*", "0"))))
  B = A[:]
  C = []
  for j in range(1,h):
    m=[]
    for i in range(j,h):
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x
      m.append(max("".join(map(str, x)).split("0")))
    C.append(len(max(m))*(j+1))
  print max(C)

Submission status: Runtime Error

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  A = [0]*h
  for i in range(h):
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = []
  for j in range(1,h):
    M = []
    for i in range(j,h):
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x
      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C.append(len(sorted(M)[-1])*(j+1))
  print max(C)

Submission status: Runtime Error

Solution code:
def f(j,k):
  tmp=j-C[k]
  if tmp>M[k]: M[k]
  return

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): f(j,k)
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([M[i]*i for i in range(h+1) if M[i]>0])
  print s

Submission status: Runtime Error

Solution code:
def f(j,k):
  tmp=j-C[k]
  if tmp>M[k]: M[k]=tmp
  return

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): f(j,k)
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([M[i]*i for i in range(h+1) if M[i]>0])
  print s

Submission status: Runtime Error

Solution code:
class Rect():
    
    def __init__(self, x_range, y_range):
        self.x_range = x_range
        self.y_range = y_range

    @property
    def w(self):
        return len(self.x_range)

    @property
    def h(self):
        return len(self.y_range)
        
    def __str__(self):
        return "Rect({},{})".format(str(self.x_range),str(self.y_range))

    def __contains__(self, pos):
        x,y = pos
        left,right = self.x_range[0],self.x_range[-1]
        buttom,top = self.y_range[0],self.y_range[-1]        
        return left<=x<=right and buttom<=y<=top

    def divide(self, pos):
        x,y = pos
        x_i = self.x_range.index(x)
        y_i = self.y_range.index(y)
        rects = [Rect(self.x_range[:x_i],self.y_range),
                 Rect(self.x_range[x_i+1:],self.y_range),
                 Rect(self.x_range,self.y_range[:y_i]),
                 Rect(self.x_range,self.y_range[y_i+1:])]        
        rem_list = [] #TEMP
        for r in rects:
            if r.x_range == [] or r.y_range == []:
                rem_list.append(r)

        for r in rem_list:
            rects.remove(r)

        return rects
def ge(H,W):
    from collections import deque
    q = deque([(0,0)])
    while q:
        x,y = q.popleft()
        yield (x,y)
        if y == 0 and x+1 < W:
            q.append([x+1,y])
        if y+1 < H:
            q.append([x,y+1])

def solveA(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    x,y = 0,0
    for x,y in ((xx,yy) for xx,yy in ge(H,W) if field[yy][xx] == "."):
        mi = space[y][x]
        for h in xrange(y,H):
            if(field[h][x] == "*"):
                break
            mi = min(mi, space[h][x])
            ans = max(ans, mi*(h-y+1))
            if (W-x+1)*(H-y+1) < ans:
                return ans
    return ans

def solveB(field,H,W):
    rects = [Rect(range(W),range(H))]
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[yy][x] == "*"):
            for r in filter(lambda rr:(x,y) in rr, rects):
                rects.extend(r.divide((x,y)))
                rects.remove(r)
    return max(r.w*r.h for r in rects)

while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    count = sum(f.count("*") for f in field)
    if count > 15:
        print solveA(field,H,W)
    else:
        print solveB(field,H,W)

Submission status: Runtime Error

Solution code:
def get_rectangle_area(table, w):
    maxv = 0
    stack = []
    table.append(0)
    for i, rect in enumerate(table):
        if stack == []:
            stack.append((rect, i))
        elif stack[-1][0] < rect:
            stack.append((rect, i))
        elif stack[-1][0] == rect:
            pass
        elif stack[-1][0] > rect:
            while stack != [] and stack[-1][0] >= rect:
                high, pos = stack.pop()
                maxv = max(maxv, high*(i-pos))
            stack.append((rect, pos))
    return maxv

while True:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break
    mass = [raw_input() for i in range(h)]
    table = histgram(mass, h, w)
    ans = 0
    for tab in table:
        ans = max(ans, get_rectangle_area(tab, w))
    print ans

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
#http://www.checkio.org/mission/spaceship-landing-strip/ verifier.

def checkio(data):
	y=len(data)
	x=len(data[0])
	m=[[0]*x for i in range(y)]
	for j in range(y):
		r=0
		for i in range(x):
			if data[j][i]=='.': r+=1
			else: r=0
			m[j][i]=r
	r=0
	for i in range(x):
		for j in range(y):
			M=9999999
			for k in range(j,y):
				M=min(M,m[k][i])
				r=max(r,M*(k-j+1))
	return r

while True:
	x,y=[int(e) for e in raw_input().split()]
	if y==0: break
	data=[raw_input().rstrip() for i in range(y)]
	print(checkio(data))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
#http://www.checkio.org/mission/spaceship-landing-strip/ verifier.

def checkio(data):
	y=len(data)
	x=len(data[0])
	m=[[0]*x for i in range(y)]
	for j in range(y):
		r=0
		for i in range(x):
			if data[j][i]=='.': r+=1
			else: r=0
			m[j][i]=r
	r=0
	for i in range(x):
		for j in range(y):
			M=9999999
			for k in range(j,y):
				M=min(M,m[k][i])
				r=max(r,M*(k-j+1))
	return r

if __name__=='__main__':
	try:
		while True:
			x,y=[int(e) for e in raw_input().split()]
			if y==0: break
			data=[raw_input().rstrip() for i in range(y)]
			print(checkio(data))
	except EOFError:
		pass