Problem:


A Garden with Ponds

  Mr. Gardiner is a modern garden designer who is excellent at utilizing the terrain features.
  His design method is unique: he first decides the location of ponds and design them with the terrain features intact.

  According to his unique design procedure, all of his ponds are rectangular with simple aspect ratios.
  First, Mr. Gardiner draws a regular grid on the map of the garden site so that the land is divided into cells of unit square, and annotates every cell with its elevation.
  In his design method, a pond occupies a rectangular area consisting of a number of cells.
  Each of its outermost cells has to be higher than all of its inner cells.
  For instance, in the following grid map, in which numbers are elevations of cells, a pond can occupy the shaded area, where the outermost cells are shaded darker and the inner cells are shaded lighter.
  You can easily see that the elevations of the outermost cells are at least three and those of the inner ones are at most two.

  A rectangular area on which a pond is built must have at least one inner cell.
  Therefore, both its width and depth are at least three.

  When you pour water at an inner cell of a pond, the water can be kept in the pond until its level reaches that of the lowest outermost cells.
  If you continue pouring, the water inevitably spills over.  
  Mr. Gardiner considers the larger capacity the pond has, the better it is.
  Here, the capacity of a pond is the maximum amount of water it can keep.
  For instance, when a pond is built on the shaded area in the above map, its capacity is (3 &#8722; 1) + (3 &#8722; 0) + (3 &#8722; 2) = 6, where 3 is the lowest elevation of the outermost cells and 1, 0, 2 are the elevations of the inner cells.
  Your mission is to write a computer program that, given a grid map describing the elevation of each unit square cell, calculates the largest possible capacity of a pond built in the site.

  Note that neither of the following rectangular areas can be a pond.
  In the left one, the cell at the bottom right corner is not higher than the inner cell.
  In the right one, the central cell is as high as the outermost cells.

  

Input

The input consists of at most 100 datasets, each in the following format.

d w
e1, 1 ... e1, w
...
ed, 1 ... ed, w

The first line contains d and w, representing the depth and the width, respectively, of the garden site described in the map. 
They are positive integers between 3 and 10, inclusive.
Each of the following d lines contains w integers between 0 and 9, inclusive, separated by a space.
The x-th integer in the y-th line of the d lines is the elevation of the unit square cell with coordinates (x, y).

The end of the input is indicated by a line containing two zeros separated by a space.

Output

  For each dataset, output a single line containing the largest possible capacity of a pond that can be built in the garden site described in the dataset.
  If no ponds can be built, output a single line containing a zero.

Sample Input

3 3
2 3 2
2 1 2
2 3 1
3 5
3 3 4 3 3
3 1 0 2 3
3 3 4 3 2
7 7
1 1 1 1 1 0 0
1 0 0 0 1 0 0
1 0 1 1 1 1 1
1 0 1 0 1 0 1
1 1 1 1 1 0 1
0 0 1 0 0 0 1
0 0 1 1 1 1 1
6 6
1 1 1 1 2 2
1 0 0 2 0 2
1 0 0 2 0 2
3 3 3 9 9 9
3 0 0 9 0 9
3 3 3 9 9 9
0 0

Output for the Sample Input

0
3
1
9



Sample input:
3 3
2 3 2
2 1 2
2 3 1
3 5
3 3 4 3 3
3 1 0 2 3
3 3 4 3 2
7 7
1 1 1 1 1 0 0
1 0 0 0 1 0 0
1 0 1 1 1 1 1
1 0 1 0 1 0 1
1 1 1 1 1 0 1
0 0 1 0 0 0 1
0 0 1 1 1 1 1
6 6
1 1 1 1 2 2
1 0 0 2 0 2
1 0 0 2 0 2
3 3 3 9 9 9
3 0 0 9 0 9
3 3 3 9 9 9
0 0


Sample output:
0
3
1
9

Submission status: Wrong Answer

Solution code:
def area(x_s,x_e,y_s,y_e):
	return int((x_e-x_s-1)*(y_e-y_s-1))

def minimum_border(A,x_s,x_e,y_s,y_e):
	min=A[x_s][y_s]
	for i in range(x_s,x_e+1):
		for j in range(y_s,y_e+1):
			if A[i][j]<min:
				min=A[i][j]
	return min

def maximum_inter(A,x_s,x_e,y_s,y_e):
	max=A[x_s+1][y_s+1]
	for i in range(x_s+1,x_e):
		for j in range(y_s+1,y_e):
			if A[i][j]>max:
				max=A[i][j]
	return max

A=[[0 for i in range(10)]for j in range(10)]
ans=[]

while True:
	n,m=map(int,input().split())

	if n==m==0:
		break
	for i in range(n):
		tmp=[]
		tmp=list(map(int,input().split()))
		tmp.reverse()
		for j in range(m):
			A[i][j]=tmp.pop()

	flag=0
	max_s=0
	for y_s in range(m-2):
		for y_e in range(m-3,m):
			for x_s in range(n-2):
				for x_e in range(n-3,n):
					if y_e-y_s<2 or x_e-x_s<2:
						pass
					else:
						#print(area(x_s,x_e,y_s,y_e))
						if minimum_border(A,x_s,x_e,y_s,y_e)>maximum_inter(A,x_s,x_e,y_s,y_e):
							if flag==0:	
								print("=====")
								max_s=area(x_s,x_e,y_s,y_e)
							else:
								if area(x_s,x_e,y_s,y_e)>max_s:
									max_s=area(x_s,x_e,y_s,y_e)
							ans.append(max_s)

ans.reverse()
for i in range(len(ans)):
	print(ans.pop())

Submission status: Accepted

Solution code:
# coding: utf-8

def func(lx, rx, ly, ry, e):
    ret = 0
    soto_min = 0xdeadbeef

    for i in range(lx, rx+1):
        for j in range(ly, ry+1):
            if i == lx or i == rx or j == ly or j == ry:
                soto_min = min(soto_min, e[j][i])

    for i in range(lx, rx+1):
        for j in range(ly, ry+1):
            if i == lx or i == rx or j == ly or j == ry:
                continue

            if e[j][i] >= soto_min:
                return 0

            ret += (soto_min - e[j][i])

    return ret


while True:
    d, w = map(int, raw_input().split())

    if d == 0 and w == 0:
        break

    e = [map(int, raw_input().split()) for _ in range(d)]

    ans = 0

    for lx in range(w-2):
        for rx in range(lx+2, w):
            for ly in range(d-2):
                for ry in range(ly+2, d):
                    ans = max(ans, func(lx, rx, ly, ry, e))

    print ans

Submission status: Accepted

Solution code:
while True:
  d, w = map(int, input().split())
  if d == 0:break
  mp = [list(map(int, input().split())) for _ in range(d)]
  def solve():
    ans = 0
    for left in range(w - 1):
      for right in range(w - 1, left + 1, -1):
        for top in range(d - 1):
          for under in range(d - 1, top + 1, -1):
            frame_height = 10
            frame_height = min(frame_height, min(mp[top][left:right + 1]))
            frame_height = min(frame_height, min(mp[under][left:right + 1]))
            frame_height = min(frame_height, min(mp[i][left] for i in range(top, under)))
            frame_height = min(frame_height, min(mp[i][right] for i in range(top, under)))
            pond_height = 0
            pond_height = max(pond_height, max(max(mp[i][left + 1:right]) for i in range(top + 1, under)))
            if pond_height < frame_height:
              temp = frame_height * (under - top - 1) * (right - left - 1) - \
                    sum(sum(mp[i][left + 1:right]) for i in range(top + 1, under))
              ans = max(temp, ans)
    print(ans)
  
  solve()

Submission status: Accepted

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

    e = [list(map(int, input().split())) for i in range(d)]
    V = 0
    for i_l in range(d - 2):
        for i_r in range(min(i_l + 2, d), d):
            for j_l in range(w - 2):
                for j_r in range(min(j_l + 2, w), w):
                    min_out = 10 ** 10
                    max_in = 0
                    tmp = 0
                    for i in range(i_l, i_r + 1):
                        for j in range(j_l, j_r + 1):
                            if i == i_l or i == i_r or j == j_l or j == j_r:
                                #print(i, j)
                                min_out = min(min_out, e[i][j])
                            else:
                                max_in = max(max_in, e[i][j])

                    for i in range(i_l, i_r + 1):
                        for j in range(j_l, j_r + 1):
                            if min_out > max_in:
                                if i == i_l or i == i_r or j == j_r or j == j_l:
                                    1
                                else:
                                    #print(i_l, i_r, j_l, j_r, i, j, min_out, max_in, e[i][j])
                                    tmp += min_out - e[i][j]


                    #print(tmp)
                    V = max(tmp, V)

    print(V)

Submission status: Accepted

Solution code:
while 1:
    D,W=list(map(int,input().split()))
    if (D,W)==(0,0):
        break
    garden = [list(map(int,input().split())) for _ in range(D)]
    ans=0
    for wi in range(W):
        for wj in range(wi+2,W):
            for di in range(D):
                for dj in range(di+2,D):
                    edge_min = float("inf")
                    water_sum=0
                    count=0
                    in_max=0
                    for w in range(wi,wj+1):
                        for d in range(di,dj+1):
                            if w in (wi,wj) or d in (di,dj) :
                                edge_min= min(garden[d][w] , edge_min)
                                ###print(edge_min,garden[d][w],"eee",min(edge_min,garden[d][w]))
                            else:
                                water_sum+=garden[d][w]
                                in_max=max(in_max,garden[d][w])
                                count+=1
                    if edge_min>in_max:                    
                        ans=max(ans,edge_min*count - water_sum)
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    d, w = map(int, input().split())
    if d == w == 0:
        break
    E = [0]*d
    for i in range(d):
        *E[i], = map(int, input().split())
    ans = 0
    for x2 in range(d):
        for y2 in range(w):
            for x1 in range(x2-1):
                for y1 in range(y2-1):
                    co = 10**18
                    for x in range(x1, x2+1):
                        co = min(co, E[x][y1], E[x][y2])
                    for y in range(y1, y2+1):
                        co = min(co, E[x1][y], E[x2][y])
                    ci = cnt = 0
                    for x in range(x1+1, x2):
                        for y in range(y1+1, y2):
                            ci = max(ci, E[x][y])
                            cnt += E[x][y]
                    if ci < co:
                        ans = max(ans, (x2-x1-1)*(y2-y1-1)*co - cnt)
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    d, w = map(int, input().split())
    if d == w == 0:
        break
    E = [list(map(int, input().split())) for i in range(d)]
    ans = 0
    for x2 in range(d):
        for y2 in range(w):
            for x1 in range(x2-1):
                for y1 in range(y2-1):
                    co = 10**18
                    for x in range(x1, x2+1):
                        co = min(co, E[x][y1], E[x][y2])
                    for y in range(y1, y2+1):
                        co = min(co, E[x1][y], E[x2][y])
                    ci = cnt = 0
                    for x in range(x1+1, x2):
                        for y in range(y1+1, y2):
                            ci = max(ci, E[x][y])
                            cnt += E[x][y]
                    if ci < co:
                        ans = max(ans, (x2-x1-1)*(y2-y1-1)*co - cnt)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools

def rdp_connect() -> bool:
    global h, w, e
    h, w = map(int, input().split())
    if h == 0 and w == 0:
        return False
    e = [list(map(int, input().split())) for _ in range(h)]
    return True

def rdp_scan(x1: int, y1: int, x2: int, y2: int) -> int:
    edges = []
    edges.extend([e[j][x1] for j in range(y1, y2 + 1)])
    edges.extend([e[j][x2] for j in range(y1, y2 + 1)])
    edges.extend([e[y1][i] for i in range(x1 + 1, x2)])
    edges.extend([e[y2][i] for i in range(x1 + 1, x2)])
    inner = [e[j][i] for j, i in itertools.product(range(y1 + 1, y2), range(x1 + 1, x2))]
    edges_min = min(edges)
    if edges_min - max(inner) <= 0:
        return 0
    return sum(map(lambda e: edges_min - e, inner))

if __name__ == '__main__':
    while rdp_connect():
        best = 0
        for y1, x1 in itertools.product(range(h), range(w)):
            for y2, x2 in itertools.product(range(y1 + 2, h), range(x1 + 2, w)):
                best = max(best, rdp_scan(x1, y1, x2, y2))
        print(best)

Submission status: Accepted

Solution code:
while True:
    d, w = map(int, input().split())
    if d == 0:
        break
    area = []
    for _ in range(d):
        area.append(list(map(int, input().split())))
    v = 0
    for dp in range(1, d - 1):
        for wp in range(1, w - 1):
            for i in range(1, d - dp):
                for j in range(1, w - wp):
                    mawari = min(area[i - 1][j - 1:j + wp + 1] + area[i + dp][j - 1:j + wp + 1])
                    naka = 0
                    for ii in range(dp):
                        mawari = min(mawari, area[i + ii][j - 1], area[i + ii][j + wp])
                        naka = max([naka] + area[i + ii][j:j + wp])
                    if mawari > naka:
                        vn = 0
                        for ii in range(dp):
                            for jj in range(wp):
                                vn += mawari - area[i + ii][j + jj]
                        v = max(vn, v)
    print(v)

Submission status: Accepted

Solution code:
while True:
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    E = [list(map(int, input().split())) for i in range(n)]
    ans=0
    for x in range(n-2):
        for y in range(m-2):
            for w in range(3,n-x+1):
                
                for h in range(3,m-y+1):
                    N=0
                    A=E[x][y]
                    B=0
                    for i in range(w):
                        for j in range(h):
                            if i==0 or j==0 or j==h-1 or i==w-1:
                                A=min(A,E[x+i][y+j])
                            else:
                                B=max(B,E[x+i][y+j])

                    if A>B:
                        for i in range(w):
                            for j in range(h):
                                if i!=0 and j!=0 and j!=h-1 and i!=w-1:
                                    N=N+A-E[x+i][y+j]
                                    
                    ans=max(ans,N)

    print(ans)

Submission status: Accepted

Solution code:
while True:
    d, w = map(int, input().split())
    if d == 0:
        break
    area = []
    for _ in range(d):
        area.append(list(map(int, input().split())))
    a = 0
    for dp in range(1, d - 1):
        for wp in range(1, w - 1):
            for i in range(1, d - dp):
                for j in range(1, w - wp):
                    mawari = min(area[i - 1][j - 1:j + wp + 1] + area[i + dp][j - 1:j + wp + 1])
                    naka = 0
                    for ii in range(dp):
                        mawari = min(mawari, area[i + ii][j - 1], area[i + ii][j + wp])
                        naka = max([naka] + area[i + ii][j:j + wp])
                    if mawari > naka:
                        vn = 0
                        for ii in range(dp):
                            for jj in range(wp):
                                vn += mawari - area[i + ii][j + jj]
                        a = max(vn, a)
    print(a)

Submission status: Accepted

Solution code:
def solve(d,w,f):
    ans = 0
#    print("aaa")
    for i in range(d-2):
        for j in range(i+2,d):
            for k in range(w-2):
                for l in range(k+2,w):
                    minOut = 10
                    for m in range(i,j+1):
                        if minOut > f[m][k]:
                            minOut = f[m][k]
                        if minOut > f[m][l]:
                            minOut = f[m][l]
                            
                    for m in range(k,l+1):
                        if minOut > f[i][m]:
                            minOut = f[i][m]
                        if minOut > f[j][m]:
                            minOut = f[j][m]
                    total = 0
                    for m in range(i+1,j):
                        for n in range(k+1,l):
                            total += minOut-f[m][n]
                            if minOut <= f[m][n]:
                                total -= 10**5
    #                print(total,i,j,k,l)
                    if ans < total:
                        ans = total
    return ans


while True:
    d,w = [int(i) for i in input().split()]
    if d==0:
        break
    f = []
    for i in range(d):
        f.append([int(i) for i in input().split()])
    print(solve(d,w,f))

Submission status: Accepted

Solution code:
while(True):
	h, w = map(int, input().split())
	if (h+w) == 0:break
	e = list(list(int(i) for i in input().split()) for i in range(h))
	e_T = list(zip(*e))
	ans = 0
	for i in range(h-2):
		for j in range(w-2):
			for k in range(i+2,h):
				for l in range(j+2,w):
					flag = False
					count = 0
					wall = min(min(e[i][j:l+1]), min(e[k][j:l+1]), min(e_T[j][i:k+1]), min(e_T[l][i:k+1]))
					#print(wall)
					for m in range(i+1,k):
						for n in range(j+1,l):
							if wall > e[m][n]:
								count += wall - e[m][n]
							else:
								flag = True
								break
						if flag:break
					
					if ans < count and not flag:
						ans = count				
	print(ans)

Submission status: Accepted

Solution code:
from itertools import product
while True:
    d, w = map(int, input().split())  # 高さdと幅w
    if d == 0:
        break
    gridgraph = [list(map(int, input().split())) for _ in range(d)]
    ans = 0
    for si, sj in product(range(1, d-1), range(1, w-1)):
        for ti, tj in product(range(si, d-1), range(sj, w-1)):
            # これで内部の池の範囲が指定できた
            # 内部の最大値を考えたい
            max_in_area = 0
            for i, j in product(range(si, ti+1), range(sj, tj+1)):
                max_in_area = max(max_in_area, gridgraph[i][j])

            # 周囲の最小値を考えたい
            huti_min = 100
            # 右方向を考えたい
            for i, j in product([si-1, ti+1], range(sj-1, tj+2)):  # rangeの仕様に注意
                huti_min = min(huti_min, gridgraph[i][j])

            # 下方向を考えたい
            for i, j in product(range(si-1, ti+2), [sj-1, tj+1]):  # rangeの仕様に注意
                huti_min = min(huti_min, gridgraph[i][j])

            if max_in_area >= huti_min:
                continue

            tmp = 0
            for i, j in product(range(si, ti+1), range(sj, tj+1)):
                tmp += huti_min - gridgraph[i][j]
            ans = max(ans, tmp)

    print(ans)

Submission status: Accepted

Solution code:
while True:
	d,w = map(int,input().split())
	if d+w == 0:break
	pond = [list(map(int,input().split())) for _ in range(d)]
	ans = 0
	for left in range(w-1):
		for right in range(w-1,left+1,-1):
			for top in range(d-1):
				for under in range(d-1,top+1,-1):
					outh = 10
					outh = min(outh,min(pond[top][left:right+1]))
					outh = min(outh,min(pond[under][left:right+1]))
					zpond = list(zip(*pond))
					outh = min(outh,min(zpond[left][top:under]))
					outh = min(outh,min(zpond[right][top:under]))
					pondh = 0
					for i in range(top+1, under):
						pondh = max(pondh,max(pond[i][left+1:right]))
					if pondh < outh:
						cap = outh*(under-top-1) * (right-left-1) - sum(sum(pond[i][left+1:right]) for i in range(top+1,under))
						ans = max(cap,ans)
	print(ans)

Submission status: Accepted

Solution code:
def f(l,r,u,d):
    global e,no
    res = 0
    hori = 10
    for i in range(u,d+1):
        if i==u or i==d:
            hori = min(hori,min(e[i][l:r+1]))
        else:
            hori = min(hori,e[i][l],e[i][r])
    if hori==no:
        return 0
    for i in range(u+1,d):
        for j in range(l+1,r):
            if hori<=e[i][j]:
                return 0
            res += abs(hori-e[i][j])
    return res
while True:
    D,W = map(int,input().split())
    if D+W==0:
        break
    e = [list(map(int,input().split())) for _ in range(D)]
    for i in range(D):
        no = min(e[0]) if i==0 else min(no,min(e[i]))
    #l,r,u,d
    ans = 0
    for l in range(W-2):
        for r in range(l+2,W):
            for u in range(D-2):
                for d in range(u+2,D):
                    ans = max(ans,f(l,r,u,d))
    print(ans)

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2,gcd
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():

    ans=[]
    
    while 1:
        d,w = MAP()

        if d==0 and w == 0:
            break
        else:
            lis=[]

            e=[LIST() for _ in range(d) ]

            #print(d,w)

            for x in combinations(range(d),2):
                for y in combinations(range(w),2):
                    if x[1]-x[0]!=1 and y[1]-y[0]!=1:

                        waku_min=9
                        naka_max=0
                        a=0
                        for p in range(x[0],x[1]+1):
                            for q in range(y[0],y[1]+1):
                                if p == x[0] or p == x[1] or q == y[0] or q == y[1] :
                                    waku_min=min(waku_min,e[p][q])
                                else:
                                    naka_max=max(naka_max,e[p][q])

                        if waku_min > naka_max:
                            #print('tate:',x)
                            #print('yoko:',y)
                            #print(waku_min,naka_max)
                            for p in range(x[0]+1,x[1]):
                                for q in range(y[0]+1,y[1]):
                                    a += waku_min-e[p][q]

                            lis.append(a)

            if not lis:
                ans.append(0)
            else:
                ans.append(max(lis))

        #print('lis:' ,lis)

    for x in ans:
        print(x)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations, product

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def MAP(): return map(int, input().split())

ans = []
while 1:
	d, w = MAP()
	if d == 0 and w == 0:
		break
	e = [LIST() for _ in range(d)]
	sum_max = 0
	for i in combinations(range(d), 2):
		if abs(i[0]-i[1]) == 1:
			continue
		for j in combinations(range(w), 2):
			if abs(j[0]-j[1]) == 1:
				continue
			# 堀の最小値を見つける
			min_ = 10
			for k in range(i[0], i[1]+1):
				if k == i[0] or k == i[1]:
					for l in range(j[0], j[1]+1):
						min_ = min(min_, e[k][l])
				else:
					min_ = min(min_, e[k][j[0]])
					min_ = min(min_, e[k][j[1]])
			# 内側を調べる．内側にmin_以上の値があればだめ．
			sum_ = 0
			for k in range(i[0]+1, i[1]):
				for l in range(j[0]+1, j[1]):
					# print(k, l, e[k][l])
					if e[k][l] >= min_:
						sum_ = 0
						break
					else:
						sum_ += (min_-e[k][l])
				if e[k][l] >= min_:
					break
			sum_max = max(sum_max, sum_)

	ans.append(sum_max)
for x in ans:
	print(x)

Submission status: Accepted

Solution code:
while True:
    d,w = map(int,input().split())

    if d == 0:
        break

    e = list(list(map(int,input().split()))for i in range(d))
    ans = 0
    for sx in range(w-2):
        for sy in range(d-2):
            for tx in range(sx+2,w):
                for ty in range(sy+2,d):
                    #外周の最大値
                    max_out = float('inf')
                    for i in range(sx,tx+1):
                        max_out = min(e[sy][i],e[ty][i],max_out)
                    for i in range(sy,ty+1):
                        max_out = min(e[i][sx],e[i][tx],max_out)
                    v = 0
                    for j in range(sx+1,tx):
                        for i in range(sy+1,ty):
                            v += max_out-e[i][j]
                            if max_out - e[i][j] <= 0:
                                v = -float('inf')
                    ans = max(v,ans)
    print(ans)

Submission status: Accepted

Solution code:
def check(ry, rx, x, y, f):
    tmpmin = float("inf")
    for yi in range(ry):
        tmpmin = min(tmpmin, f[yi + y][x])
    for xi in range(rx):
        tmpmin = min(tmpmin, f[y][xi + x])
    for yi in range(ry):
        tmpmin = min(tmpmin, f[yi + y][x + rx - 1])
    for xi in range(rx):
        tmpmin = min(tmpmin, f[ry - 1 + y][x + xi])
    res = 0

    for yi in range(y + 1, y + ry - 1):
        for xi in range(x + 1, x + rx - 1):
            res += tmpmin-f[yi][xi]
            if f[yi][xi] >= tmpmin:
                return 0
    return res

def main(d, w):
    field = [list(map(int, input().split())) for i in range(d)]
    res = 0
    for ry in range(3,d+1):
        for rx in range(3,w+1):
            for y in range(d - ry + 1):
                for x in range(w - rx + 1):
                    res = max(res, check(ry, rx, x, y, field))
    print(res)

while 1:
    d, w = map(int, input().split())
    if d == w == 0:
        break
    main(d, w)

Submission status: Accepted

Solution code:
#2005_c
"""
n = int(input())
k = list("mcxi")
for i in range(n):
    d = {"m":0,"c":0,"x":0,"i":0}
    a,b  = input().split()
    a = list(a)
    b = list(b)
    a.insert(0,1)
    b.insert(0,1)
    for j in range(1,len(a)):
        if a[j] in k:
            if a[j-1] in k:
                d[a[j]] += 1
            else:
                d[a[j]] += int(a[j-1])
    for j in range(1,len(b))[::-1]:
        if b[j] in k:
            if b[j-1] in k:
                d[b[j]] += 1
            else:
                d[b[j]] += int(b[j-1])
            if d[b[j]] >= 10:
                l = b[j]
                while d[l] >= 10:
                    d[l] -= 10
                    l = k[k.index(l)-1]
                    d[l] += 1
    for j in k:
        if d[j]:
            if d[j] == 1:
                print(j,end = "")
            else:
                print(str(d[j])+j,end = "")
    print()
"""
#2017_c
while 1:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    s = [list(map(int, input().split())) for i in range(h)]

    ans = 0
    for u in range(h):
        for d in range(u+2,h):
            for l in range(w):
                for r in range(l+2,w):
                    m = float("inf")
                    for i in range(u,d+1):
                        m = min(m,s[i][l],s[i][r])
                    for i in range(l,r+1):
                        m = min(m,s[u][i],s[d][i])
                    f = 1
                    su = 0
                    for i in range(u+1,d):
                        for j in range(l+1,r):
                            su += (m-s[i][j])
                            if s[i][j] >= m:
                                f = 0
                                break
                        if not f:
                            break
                    if f:
                        ans = max(ans,su)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
while True:
    d, w = map(int, input().split())
    if d == 0:
        exit()

    ans = 0
    e = [list(map(int, input().split())) for _ in range(d)]
    for si, sj in product(range(1, d - 1), range(1, w - 1)):
        for ti, tj in product(range(si + 1, d), range(sj + 1, w)):
            mx = 0
            for i, j in product(range(si, ti), range(sj, tj)):
                mx = max(mx, e[i][j])
            mn = 100
            for i, j in product([si - 1, ti], range(sj - 1, tj + 1)):
                mn = min(mn, e[i][j])
            for i, j in product(range(si - 1, ti + 1), [sj - 1, tj]):
                mn = min(mn, e[i][j])
            if mx >= mn:
                continue

            tmp = 0
            for i, j in product(range(si, ti), range(sj, tj)):
                tmp += mn - e[i][j]
            ans = max(ans, tmp)
    print(ans)

Submission status: Accepted

Solution code:
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def calcVolume(L, R, T, B, min_wall):
    '''
    池の体積を計算
    '''
    ret = 0
    for w in range(L, R+1):
        for h in range(B, T+1):
            ret += (min_wall-garden[h][w])
    return ret


def pondsVolume(L, R, T, B):
    '''
    池の体積をreturn
    池を作れないなら-1
    '''
    # 池の中で一番高い所
    max_in_pond = 0
    for w in range(L, R+1):
        for h in range(B, T+1):
            max_in_pond = max(max_in_pond, garden[h][w])
    # 周りの壁の一番低い所
    min_wall = float('inf')
    for w in range(L-1, R+2):
        min_wall = min(min_wall, garden[B-1][w], garden[T+1][w])
    for h in range(B-1, T+2):
        min_wall = min(min_wall, garden[h][L-1], garden[h][R+1])

    if min_wall <= max_in_pond:
        return -1
    else:
        return calcVolume(L, R, T, B, min_wall)


while True:
    d, w = map(int, input().split())
    if d == 0:
        break
    garden = [list(map(int, input().split())) for _ in range(d)]
    ans = 0
    wallMin = 0
    # 池の範囲を全探索
    for L in range(1, w-1):
        for B in range(1, d-1):
            for R in range(L, w-1):
                for T in range(B, d-1):
                    ans = max(ans, pondsVolume(L, R, T, B))
    print(ans)

Submission status: Accepted

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

        garden = []
        for i in range(d):
            garden.append(list(map(int, input().split())))

        pondmax = 0
        for tly in range(len(garden)):
            for tlx in range(len(garden[0])):
                for bry in range(tly + 2, len(garden)):
                    for brx in range(tlx + 2, len(garden[0])):
                        # sampling
                        l_gray = []
                        d_gray = []
                        for spy in range(tly, bry + 1):
                            for spx in range(tlx, brx + 1):
                                if spy == tly or spy == bry or spx == tlx or spx == brx:
                                    d_gray.append(garden[spy][spx])
                                else: l_gray.append(garden[spy][spx])
                        if min(d_gray) > max(l_gray):
                            pond = 0
                            for depth in l_gray:
                                pond += min(d_gray) - depth
                            if pond > pondmax: pondmax = pond

        print(pondmax)
                        
main()