Problem:


Get a Rectangular Field

Karnaugh is a poor farmer who has a very small field.
He wants to reclaim wasteland in the kingdom to get a new field.
But the king who loves regular shape
made a rule that a settler can only get a rectangular land as his field.
Thus, Karnaugh should get the largest rectangular land suitable for
reclamation.

The map of the wasteland is represented with a 5 x 5 grid as shown
in the following figures, where '1' represents a place suitable for
reclamation and '0' represents a sandy place.
Your task is to find the largest rectangle consisting only of 1's in the map,
and to report the size of the rectangle.
The size of a rectangle is defined by the number of 1's in it.
Note that there may be two or more largest rectangles of the same size.

                
Figure 1. The size of the largest rectangles is 4.
        There are two largest rectangles (shaded).

                
Figure 2. The size of the largest rectangle is 3.
        There is one largest rectangle (shaded).

Input

The input consists of maps preceded by an integer m 
indicating the number of input maps.

m
map1

map2

map3

...

mapm

Two maps are separated by an empty line.

Each  mapk  is in the following format:

 p p p p p 
 p p p p p 
 p p p p p 
 p p p p p 
 p p p p p 

Each p is a character either '1' or '0'.
Two p's in the same line are separated by a space character.
Here, the character '1' shows a place suitable for reclamation
and '0' shows a sandy place.
Each map contains at least one '1'.

Output

The size of the largest
rectangle(s) for each input map should be shown each in a separate line.

Sample Input

3
1 1 0 1 0
0 1 1 1 1
1 0 1 0 1
0 1 1 1 0
0 1 1 0 0

0 1 0 1 1
0 1 0 1 0
0 0 1 0 0
0 0 1 1 0
1 0 1 0 0

1 1 1 1 0
0 1 1 1 0
0 1 1 0 1
0 1 1 1 0
0 0 0 0 1

Output for the Sample Input

4
3
8



Sample input:
3
1 1 0 1 0
0 1 1 1 1
1 0 1 0 1
0 1 1 1 0
0 1 1 0 0

0 1 0 1 1
0 1 0 1 0
0 0 1 0 0
0 0 1 1 0
1 0 1 0 0

1 1 1 1 0
0 1 1 1 0
0 1 1 0 1
0 1 1 1 0
0 0 0 0 1


Sample output:
4
3
8

Submission status: Wrong Answer

Solution code:
# AOJ 1114: Get a Rectangular Field
# Python3 2018.7.8 bal4u

a = [[] for i in range(5)]
s = [[0 for c in range(5)] for r in range(5)]
for k in range(int(input())):
	if k > 0: input()
	for r in range(5):
		a[r] = list(map(int, input().split()))
		s[r][0] = a[r][0]
		for c in range(1, 5): s[r][c] = s[r][c-1]+a[r][c]
	ans = 0;
	for r in range(5):
		for c in range(5):
			for c2 in range(4, c-1, -1):
				w2 = w = c2-c+1
				if w2 > s[r][c2]-s[r][c-1]: continue
				ans = max(ans, w2)
				for r2 in range(r+1, 5):
					if w > s[r2][c2]-s[r2][c-1]: break
					w2 += w
					ans = max(ans, w2)
	print(ans)

Submission status: Wrong Answer

Solution code:
max_size = 0

def get_max_rectangle(field):
    for i in range(len(field)):
        for j in range(len(field[0])):
            if field[i][j] == 1:
                max_rectangle_right(field, {'x0':j, 'y0':i, 'x1':j, 'y1':i})
                max_rectangle_bottom(field, {'x0':j, 'y0':i, 'x1':j, 'y1':i})
    

def check_expandable(field, rect, a0, a1, b, c):
    return rect[a1] - rect[a0] + 1 == len([i for i in range(rect[a0], rect[a1]+1) if field[rect[b]+c][i] == 1])

def check_fill_ones(field, rect):
    for i in range(rect['x0'], rect['x1']+1):
        for j in range(rect['y0'], rect['y1']+1):
            if field[j][i] == 0:
                return False
    return True

def max_rectangle_right(field, rect):
    #右拡張
    if rect['y1'] - rect['y0'] + 1 == len([i for i in range(rect['y0'], rect['y1']+1) if field[i][rect['x1']+1] == 1]):
        tmp_rect = rect
        tmp_rect['x1'] += 1
        max_rectangle_right(field, tmp_rect)

    #下拡張
    if rect['x1'] - rect['x0'] + 1 == len([i for i in range(rect['x0'], rect['x1']+1) if field[rect['y1']+1][i] == 1]):
        tmp_rect = rect
        tmp_rect['y1'] += 1
        max_rectangle_right(field, tmp_rect)

    global max_size
    if check_fill_ones(field, rect):
        max_size = max(max_size, (rect['x1']-rect['x0']+1) * (rect['y1']-rect['y0']+1))

def max_rectangle_bottom(field, rect):
    #下拡張
    if rect['x1'] - rect['x0'] + 1 == len([i for i in range(rect['x0'], rect['x1']+1) if field[rect['y1']+1][i] == 1]):
        tmp_rect = rect
        tmp_rect['y1'] += 1
        max_rectangle_bottom(field, tmp_rect)

    #右拡張
    if rect['y1'] - rect['y0'] + 1 == len([i for i in range(rect['y0'], rect['y1']+1) if field[i][rect['x1']+1] == 1]):
        tmp_rect = rect
        tmp_rect['x1'] += 1
        max_rectangle_bottom(field, tmp_rect)

    global max_size
    if check_fill_ones(field, rect):
        max_size = max(max_size, (rect['x1']-rect['x0']+1) * (rect['y1']-rect['y0']+1))

def input_field(y, x):
    field = []
    for i in range(y):
        field.append(map(int, raw_input().split()))
    return pack_field(field, y, x)

def pack_field(field, y, x):
    packed_field = []
    for i in range(y + 2):
        packed_field.append([])
        if i == 0 or i == y + 1:
            for j in range(x + 2):
                packed_field[i].append(0)
        else:
            packed_field[i].append(0)
            for j in range(x):
                packed_field[i].append(field[i-1][j])
            packed_field[i].append(0)
    return packed_field

maxs = []
num = int(raw_input())
first = True
for i in range(num):
    if not first:
        raw_input()

    max_size = 0
    field = input_field(5, 5)
    get_max_rectangle(field)
    maxs.append(max_size)
    first = False

for i in range(num):
    print(maxs[i])

Submission status: Accepted

Solution code:
# AOJ 1114: Get a Rectangular Field
# Python3 2018.7.8 bal4u

s = [[0 for c in range(6)] for r in range(6)]
for k in range(int(input())):
	if k > 0: input()
	for r in range(5):
		a = list(map(int, input().split()))
		for c in range(5): s[r+1][c+1] = s[r+1][c]+a[c]
	ans = 0;
	for r in range(1, 6):
		for c in range(1, 6):
			for c2 in range(5, c-1, -1):
				w2 = w = c2-c+1
				if w2 > s[r][c2]-s[r][c-1]: continue
				ans = max(ans, w2)
				for r2 in range(r+1, 6):
					if w > s[r2][c2]-s[r2][c-1]: break
					w2 += w
					ans = max(ans, w2)
	print(ans)

Submission status: Accepted

Solution code:
max_size = 0

def get_max_rectangle(field):
    for i in range(len(field)):
        for j in range(len(field[0])):
            if field[i][j] == 1:
                max_rectangle_right(field, {'x0':j, 'y0':i, 'x1':j, 'y1':i})

def check_expandable(field, rect, a0, a1, b, c):
    return rect[a1] - rect[a0] + 1 == len([i for i in range(rect[a0], rect[a1]+1) if field[rect[b]+c][i] == 1])

def check_fill_ones(field, rect):
    for i in range(rect['x0'], rect['x1']+1):
        for j in range(rect['y0'], rect['y1']+1):
            if field[j][i] == 0:
                return False
    return True

def max_rectangle_right(field, rect):
    #右拡張
    if rect['y1'] - rect['y0'] + 1 == len([i for i in range(rect['y0'], rect['y1']+1) if field[i][rect['x1']+1] == 1]):
        tmp_rect = dict(rect)
        tmp_rect['x1'] += 1
        max_rectangle_right(field, tmp_rect)

    #下拡張
    if rect['x1'] - rect['x0'] + 1 == len([i for i in range(rect['x0'], rect['x1']+1) if field[rect['y1']+1][i] == 1]):
        tmp_rect = dict(rect)
        tmp_rect['y1'] += 1
        max_rectangle_right(field, tmp_rect)

    global max_size
    if check_fill_ones(field, rect):
        max_size = max(max_size, (rect['x1']-rect['x0']+1) * (rect['y1']-rect['y0']+1))

def input_field(y, x):
    field = []
    for i in range(y):
        field.append(map(int, raw_input().split()))
    return pack_field(field, y, x)

def pack_field(field, y, x):
    packed_field = []
    for i in range(y + 2):
        packed_field.append([])
        if i == 0 or i == y + 1:
            for j in range(x + 2):
                packed_field[i].append(0)
        else:
            packed_field[i].append(0)
            for j in range(x):
                packed_field[i].append(field[i-1][j])
            packed_field[i].append(0)
    return packed_field

maxs = []
num = int(raw_input())
first = True
for i in range(num):
    if not first:
        raw_input()

    max_size = 0
    field = input_field(5, 5)
    get_max_rectangle(field)
    maxs.append(max_size)
    first = False

for i in range(num):
    print(maxs[i])

Submission status: Accepted

Solution code:
t=input()
for p in range(t):
    H=W=5
    L=[["0"]+raw_input().split()+["0"] for i in range(H)]
    L.append(["0"]*(W+2))
    L.insert(0,["0"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    T=[[[0,0] for i in range(W+2)] for i in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if L[i][j]=="1":
                T[i][j][0]+=T[i][j-1][0]+1
                T[i][j][1]+=T[i-1][j][1]+1
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]=="1":
                if L[i-1][j]==L[i][j-1]=="0":
                    dp[i][j].add((1,1))
                    maxInt=max(maxInt,1)
                elif L[i-1][j]=="0":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                        maxInt=max(maxInt,k[0]+1)
                elif L[i][j-1]=="0":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                        maxInt=max(maxInt,k[1]+1)
                else:
                    h=T[i][j][1]
                    l=T[i][j][0]
                    for k in dp[i][j-1]:
                        m=min(k[1],h)
                        dp[i][j].add((k[0]+1,m))
                        maxInt=max(maxInt,(k[0]+1)*m)
                    for k in dp[i-1][j]:
                        m=min(k[0],l)
                        dp[i][j].add((m,k[1]+1))
                        maxInt=max(maxInt,m*(k[1]+1))
        dp[i-1]=[]
    print maxInt
    if p!=t-1:
        skip=raw_input()

Submission status: Accepted

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

import sys
if sys.version_info[0]>=3: raw_input=input

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
			if data[j][i]==1: 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:
			y,x=[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
'''
if __name__=='__main__':
	n=int(raw_input())
	try:
		for _i in range(n):
			data=[[int(e) for e in raw_input().split()] for i in range(5)]
			print(checkio(data))
			raw_input()
	except EOFError:
		pass

Submission status: Accepted

Solution code:
W = H = 5
m = input()
for r in range(m):
	M = [map(int,raw_input().split()) for i in range(H)]
	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] == 1:
				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
	if r != m-1: raw_input()

Submission status: Accepted

Solution code:
import sys
if sys.version_info[0]>=3: raw_input=input

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
			if data[j][i]==1: 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__':
	n=int(raw_input())
	try:
		for _i in range(n):
			data=[[int(e) for e in raw_input().split()] for i in range(5)]
			print(checkio(data))
			raw_input()
	except EOFError:
		pass