Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
l=[[0]*w for _ in range(h)]
r=[[0]*w for _ in range(h)]
u=[[0]*w for _ in range(h)]
d=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        if j==0:
            l[i][j]=1
        else:
            l[i][j]=l[i][j-1]+1
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==0:
            u[i][j]=1
        else:
            u[i][j]=u[i-1][j]+1
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=="#":
            continue
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==h-1:
            d[i][j]=1
        else:
            d[i][j]=d[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))

# i行j列に置いたとき上下左右の方向それぞれに光の軌跡が何マス伸びるか(自マスを含む)
trailLeft = np.zeros((H, W), dtype=int)
trailRight = np.zeros((H, W), dtype=int)
trailUp = np.zeros((H, W), dtype=int)
trailDown = np.zeros((H, W), dtype=int)

for i in range(H):  # 各行について下に見ていく
    for j in range(W):  # その行の各列について右に見ていく
        if S[i][j] == '#':
            pass  # そのマスに置いたとき照らすのは0マス(置けないので)
        else:
            if i == 0 and j == 0:  # 左上
                trailLeft[i][j] = 1
                trailUp[i][j] = 1
            elif i == 0:  # 最上行
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = 1
            elif j == 0:  # 最左列
                trailLeft[i][j] = 1
                trailUp[i][j] = trailUp[i - 1][j] + 1
            else:
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = trailUp[i - 1][j] + 1

        k = H - i - 1  # H-1 to 0
        l = W - j - 1  # W-1 to 0
        # 左上に見ていく
        if S[k][l] == "#":
            pass
        else:
            if k == H - 1 and l == W - 1:  # 右下
                trailRight[k][l] = 1
                trailDown[k][l] = 1
            elif k == H - 1:  # 最下行
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = 1
            elif l == W - 1:  # 最右列
                trailRight[k][l] = 1
                trailDown[k][l] = trailDown[k + 1][l] + 1
            else:
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = trailDown[k + 1][l] + 1

print(np.max(trailLeft + trailRight + trailUp + trailDown - 3))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
H, W = map(int, input().split())
S = [line.strip("\n") for line in sys.stdin]

# i行j列に置いたとき上下左右の方向それぞれに光の軌跡が何マス伸びるか(自マスを含む)
trailLeft = np.zeros((H, W), dtype=int)
trailRight = np.zeros((H, W), dtype=int)
trailUp = np.zeros((H, W), dtype=int)
trailDown = np.zeros((H, W), dtype=int)

for i in range(H):  # 各行について下に見ていく
    for j in range(W):  # その行の各列について右に見ていく
        if S[i][j] == '#':
            pass  # そのマスに置いたとき照らすのは0マス(置けないので)
        else:
            if i == 0 and j == 0:  # 左上
                trailLeft[i][j] = 1
                trailUp[i][j] = 1
            elif i == 0:  # 最上行
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = 1
            elif j == 0:  # 最左列
                trailLeft[i][j] = 1
                trailUp[i][j] = trailUp[i - 1][j] + 1
            else:
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = trailUp[i - 1][j] + 1

        k = H - i - 1  # H-1 to 0
        l = W - j - 1  # W-1 to 0
        # 左上に見ていく
        if S[k][l] == "#":
            pass
        else:
            if k == H - 1 and l == W - 1:  # 右下
                trailRight[k][l] = 1
                trailDown[k][l] = 1
            elif k == H - 1:  # 最下行
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = 1
            elif l == W - 1:  # 最右列
                trailRight[k][l] = 1
                trailDown[k][l] = trailDown[k + 1][l] + 1
            else:
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = trailDown[k + 1][l] + 1

print(np.max(trailLeft + trailRight + trailUp + trailDown - 3))

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W = map(int, input().split())
S = [line.strip("\n") for line in sys.stdin]

# i行j列に置いたとき上下左右の方向それぞれに光の軌跡が何マス伸びるか(自マスを含む)
trailLeft = [[0] * W for _ in range(H)]
trailRight = [[0] * W for _ in range(H)]
trailUp = [[0] * W for _ in range(H)]
trailDown = [[0] * W for _ in range(H)]

for i in range(H):  # 各行について下に見ていく
    for j in range(W):  # その行の各列について右に見ていく
        if S[i][j] == '#':
            pass  # そのマスに置いたとき照らすのは0マス(置けないので)
        else:
            if i == 0 and j == 0:  # 左上
                trailLeft[i][j] = 1
                trailUp[i][j] = 1
            elif i == 0:  # 最上行
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = 1
            elif j == 0:  # 最左列
                trailLeft[i][j] = 1
                trailUp[i][j] = trailUp[i - 1][j] + 1
            else:
                trailLeft[i][j] = trailLeft[i][j - 1] + 1
                trailUp[i][j] = trailUp[i - 1][j] + 1

        k = H - i - 1  # H-1 to 0
        l = W - j - 1  # W-1 to 0
        # 左上に見ていく
        if S[k][l] == "#":
            pass
        else:
            if k == H - 1 and l == W - 1:  # 右下
                trailRight[k][l] = 1
                trailDown[k][l] = 1
            elif k == H - 1:  # 最下行
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = 1
            elif l == W - 1:  # 最右列
                trailRight[k][l] = 1
                trailDown[k][l] = trailDown[k + 1][l] + 1
            else:
                trailRight[k][l] = trailRight[k][l + 1] + 1
                trailDown[k][l] = trailDown[k + 1][l] + 1

ans = 0
for i in range(H):  # 各行について下に見ていく
    for j in range(W):  # その行の各列について右に見ていく
        ans = max(ans, trailLeft[i][j] + trailRight[i][j] + trailUp[i][j] + trailDown[i][j] - 3)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[] for i in range(H)]
for i in range(H):
  num=0
  a=input()
  for j in range(W):
    jj=a[j]
    if jj=="#":
      for k in range(num):
        A[i].append(num)
      A[i].append(0)
      num=0
    elif j==W-1:
      num+=1
      for k in range(num):
        A[i].append(num)
    else:
      num+=1
#print(A)

B=[[] for i in range(W)]
for i in range(W):
  num=0
  for j in range(H):
    jj=A[j][i]
    if jj==0:
      for k in range(num):
        B[i].append(num)
      B[i].append(0)
      num=0
    elif j==H-1:
      num+=1
      for k in range(num):
        B[i].append(num)
    else:
      num+=1
    #print(j,num,B)
#print(B)
ans=0
for i in range(H):
  for j in range(W):
    if A[i][j]+B[j][i]-1>ans:
      ans=A[i][j]+B[j][i]-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i, j in product(range(h),range(w)):
    l = S[i][j]
    r = S[i][w-1-j]
    u = S[i][j]
    d = S[h-1-i][j]
    if l == ".": L[i][j] = L[i][max(0, j-1)]+1
    if r == ".": R[i][w-1-j] = R[i][min(w-1, w-j)]+1
    if u == ".": U[i][j] = U[max(0, i-1)][j]+1
    if d == ".": D[h-1-i][j] = D[min(h-1, h-i)][j]+1
A = [L[i][j]+R[i][j]+U[i][j]+D[i][j]-3 for i, j in product(range(h), range(w))]
print(max(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W = map(int, input().split())
S = [line.strip("\n") for line in sys.stdin]
transposeS = ["" for _ in range(W)]

rowRunLength = [[0] * W for _ in range(H)]
columnRunLength = [[0] * H for _ in range(W)]


for rowNum, elem in enumerate(S):
    previousObstacleIndex = -1
    lightCount = 0
    for colNum, char in enumerate(elem):
        if char == "#":
            rowRunLength[rowNum][colNum] = 0
            for i in range(previousObstacleIndex + 1, colNum):
                rowRunLength[rowNum][i] = lightCount
            previousObstacleIndex = colNum
            lightCount = 0
        else:
            lightCount += 1
    else:
        for i in range(previousObstacleIndex + 1, W):
            rowRunLength[rowNum][i] = lightCount

for i in range(W):
    for j in range(H):
        transposeS[i] += S[j][i]

for rowNum, elem in enumerate(transposeS):
    previousObstacleIndex = -1
    lightCount = 0
    for colNum, char in enumerate(elem):
        if char == "#":
            columnRunLength[rowNum][colNum] = 0
            for i in range(previousObstacleIndex + 1, colNum):
                columnRunLength[rowNum][i] = lightCount
            previousObstacleIndex = colNum
            lightCount = 0
        else:
            lightCount += 1
    else:
        for i in range(previousObstacleIndex + 1, H):
            columnRunLength[rowNum][i] = lightCount

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, rowRunLength[i][j] + columnRunLength[j][i] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W = map(int, input().split())
S = [line.strip("\n") for line in sys.stdin]
transposeS = ["" for _ in range(W)]

rowRunLength = [[None] * W for _ in range(H)]
columnRunLength = [[None] * H for _ in range(W)]


for idx, elem in enumerate(S):
    previousObstacleIndex = -1

    while previousObstacleIndex != W:
        obstacleIndex = elem.find("#", previousObstacleIndex + 1)
        if obstacleIndex == -1:
            obstacleIndex = W
        else:
            rowRunLength[idx][obstacleIndex] = 0
        for lightenedIndex in range(previousObstacleIndex + 1, obstacleIndex):
            rowRunLength[idx][lightenedIndex] = obstacleIndex - previousObstacleIndex - 1
        previousObstacleIndex = obstacleIndex

for i in range(W):
    for j in range(H):
        transposeS[i] += S[j][i]

for idx, elem in enumerate(transposeS):
    previousObstacleIndex = -1

    while previousObstacleIndex != H:
        obstacleIndex = elem.find("#", previousObstacleIndex + 1)
        if obstacleIndex == -1:
            obstacleIndex = H
        else:
            columnRunLength[idx][obstacleIndex] = 0
        for lightenedIndex in range(previousObstacleIndex + 1, obstacleIndex):
            columnRunLength[idx][lightenedIndex] = obstacleIndex - previousObstacleIndex - 1
        previousObstacleIndex = obstacleIndex

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, rowRunLength[i][j] + columnRunLength[j][i] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def yokocheck(grid,y,height,width,yokoans):
    i = 0
    while i < width:
        if grid[y][i] == '.':
            startpos = i
            count = 1
            i+=1
            while i<width and grid[y][i] == '.':
                i += 1
                count += 1
            for a in range(count):
                yokoans[ y * width + startpos + a ] += count
        i += 1

def tatecheck(grid,x,height,width,tateans):
    i = 0
    while i < height:
        if grid[i][x] == '.':
            startpos = i
            count = 1
            i += 1
            while i<height and grid[i][x] == '.':
                i += 1
                count += 1
            for a in range(count):
                tateans[ (startpos + a) * width + x] += count
        i += 1

H,W = map(int,input().split())
yoko = [0] *(H * W)
grid =[]
for _ in range(H):
    grid.append(input())

for y in range(H):
    yokocheck(grid,y,H,W,yoko)

for x in range(W):
    tatecheck(grid,x,H,W,yoko)


maxnum = 0
for n in range(H*W):
    if yoko[n] > maxnum:
        maxnum = yoko[n]
#自身のポイントは2回カウントされるので-1調整
print( maxnum -1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
for _ in range(h):
    k = list(input())
    s.append(k)
l_list = [[0 for _ in range(w)] for _ in range(h)]
r_list = [[0 for _ in range(w)] for _ in range(h)]
u_list = [[0 for _ in range(w)] for _ in range(h)]
d_list = [[0 for _ in range(w)] for _ in range(h)]
for hh in range(h):
    for ww in range(w):
        if ww == 0:
            if s[hh][ww] == ".":
                l_list[hh][ww] = 1
            if s[hh][w - ww - 1] == ".":
                r_list[hh][w - ww - 1] = 1
        else:
            if s[hh][ww] == ".":
                l_list[hh][ww] = 1 + l_list[hh][ww - 1]
            if s[hh][w - ww - 1] == ".":
                r_list[hh][w - ww - 1] = 1 + r_list[hh][w - ww]
                
for ww in range(w):
    for hh in range(h):
        if hh == 0:
            if s[hh][ww] == ".":
                u_list[hh][ww] = 1
            if s[h - hh - 1][ww] == ".":
                d_list[h - hh - 1][ww] = 1
        else:
            if s[hh][ww] == ".":
                u_list[hh][ww] = 1 + u_list[hh - 1][ww]
            if s[h - hh - 1][ww] == ".":
                d_list[h - hh - 1][ww] = 1 + d_list[h - hh][ww]
ans = 0
for ww in range(w):
    for hh in range(h):
        ans = max(ans, r_list[hh][ww] + l_list[hh][ww] + u_list[hh][ww] + d_list[hh][ww] - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = input()

result = 0
wid = 0
for i in range(H):
        for j in range(W):
            cache = 1
            if S[i][j] == '.':
                if wid == 0:
                    for l in range(j-1,-1,-1):
                        if S[i][l] == '#':
                            break
                        wid += 1
                    for r in range(j+1,W):
                        if S[i][r] == '#':
                            break
                        wid += 1
                cache += wid
                for u in range(i-1, -1, -1):
                    if S[u][j] == '#':
                        break
                    cache += 1
                for d in range(i+1,H):
                    if S[d][j] == '#':
                        break
                    cache += 1
            if result < cache:
                result = cache
            if result == H+W:
                break
            else:
                wid = 0
print(result)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = input()

result = 0
for i in range(H):
        for j in range(W):
            cache = 1
            if S[i][j] == '.':
                for l in range(j-1,-1,-1):
                    if S[i][l] == '#':
                        break
                    cache += 1
                for r in range(j+1,W):
                    if S[i][r] == '#':
                        break
                    cache += 1
                for u in range(i-1, -1, -1):
                    if S[u][j] == '#':
                        break
                    cache += 1
                for d in range(i+1,H):
                    if S[d][j] == '#':
                        break
                    cache += 1
            if result < cache:
                result = cache
            if result == H+W:
                break
print(result)

Submission status: Time Limit Exceeded

Solution code:
#129
H,W=map(int,input().split())
s=[]
c_a=0
for i in range(H):
    s.append(list(input()))

for i in range(H):
    for j in range(W):
        c=0
        
        if s[i][j]!="#":
            c=W+H-1
            if j!=W-1:
                for n in range(1,W-j):
                    if s[i][j+n]=="#":
                        c-=W-j-n
                        break
            if j!=0:
                for n in range(1,j+1):
                    if s[i][j-n]=="#":
                        c-=j-n+1
                        break
            if i!=H-1:
                for m in range(1,H-i):
                    if s[i+m][j]=="#":
                        c-=H-i-m
                        break
            if i!=0:
                for m in range(1,i+1):
                    if s[i-m][j]=="#":
                        c-=i-m+1
                        break
        if c>c_a:
            c_a=c
print(c_a)

Submission status: Time Limit Exceeded

Solution code:
#129
H,W=map(int,input().split())
s=[]
c_a=0
for i in range(H):
    s.append(list(input()))

for i in range(H):
    for j in range(W):
        c=0
        if s[i][j]!="#":
            c=W+H-1
            if j!=W-1:
                for n in range(1,W-j):
                    if s[i][j+n]=="#":
                        c-=W-j-n
                        break
            if j!=0:
                for n in range(1,j+1):
                    if s[i][j-n]=="#":
                        c-=j-n+1
                        break
            if i!=H-1:
                for m in range(1,H-i):
                    if s[i+m][j]=="#":
                        c-=H-i-m
                        break
            if i!=0:
                for m in range(1,i+1):
                    if s[i-m][j]=="#":
                        c-=i-m+1
                        break
        if c>c_a:
            c_a=c
print(c_a)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]


R = copy.deepcopy(S)
for h in range(H):
    s = 0
    for w in range(W):
        if R[h][w] == 1:
            s += 1
            R[h][w] = s
        else:
            s = 0
    l = 0
    for w in range(W-1, -1, -1):
        if R[h][w] > 0:
            l = max(l, R[h][w])
            R[h][w] = l
        else:
            l = 0

L = copy.deepcopy(S)
for w in range(W):
    s = 0
    for h in range(H):
        if L[h][w] == 1:
            s += 1
            L[h][w] = s
        else:
            s = 0
    l = 0
    for h in range(H-1, -1, -1):
        if L[h][w] > 0:
            l = max(l, L[h][w])
            L[h][w] = l
        else:
            l = 0
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, L[h][w]+R[h][w]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())

grid = [input() for i in range(h)]

L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j in range(h)]
D = [[0 for i in range(w)] for j in range(h)]
U = [[0 for i in range(w)] for j in range(h)]

#左上から
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

#右下から
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if grid[i][j] == "#":
            R[i][j] = 0
            D[i][j] = 0
        else:
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
                
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1


ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            continue
        tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC129 D
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H)]
U = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        elif L[i][j - 1] == 0:
            L[i][j] = 1            
        else:
            L[i][j] = L[i][j - 1] + 1
 
for i in range(H):
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif j == W - 1:
            R[i][j] = 1
        elif L[i][j + 1] == 0:
            R[i][j] = 1            
        else:
            R[i][j] = R[i][j + 1] + 1
            
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            continue
        elif i == 0:
            D[i][j] = 1
        elif L[i - 1][j] == 0:
            D[i][j] = 1            
        else:
            D[i][j] = D[i - 1][j] + 1
            
for j in range(W):
    for i in range(H - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif i == H - 1:
            U[i][j] = 1
        elif L[i + 1][j] == 0:
            U[i][j] = 1            
        else:
            U[i][j] = U[i + 1][j] + 1
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, (L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC129 D
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H)]
U = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        elif L[i][j - 1] == 0:
            L[i][j] = 1            
        else:
            L[i][j] = L[i][j - 1] + 1

for i in range(H):
    for j in range(W - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif j == W - 1:
            R[i][j] = 1
        elif L[i][j + 1] == 0:
            R[i][j] = 1            
        else:
            R[i][j] = R[i][j + 1] + 1
            
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            continue
        elif i == 0:
            D[i][j] = 1
        elif L[i - 1][j] == 0:
            D[i][j] = 1            
        else:
            D[i][j] = D[i - 1][j] + 1
            
for j in range(W):
    for i in range(H - 1, -1, -1):
        if S[i][j] == '#':
            continue
        elif i == H - 1:
            U[i][j] = 1
        elif L[i + 1][j] == 0:
            U[i][j] = 1            
        else:
            U[i][j] = U[i + 1][j] + 1
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, (L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s=[]
for i in range(h):
    s.append(list(input()))

l=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            if x == 0:
                l[y][x]=1
            else:
                l[y][x]=l[y][x-1]+1
        
        if s[y][w-x-1] == '.':
            if x == 0:
                r[y][w-x-1]=1
            else:
                r[y][w-x-1]=r[y][w-x]+1

        if s[y][x] == '.':
            if y == 0:
                u[y][x]=1
            else:
                u[y][x]=u[y-1][x]+1
        
        if s[h-y-1][x] == '.':
            if y == 0:
                d[h-y-1][x]=1
            else:
                d[h-y-1][x]=d[h-y][x]+1

ans=0
for y in range(h):
    for x in range(w):
        val=l[y][x]+r[y][x]+u[y][x]+d[y][x]-3
        ans=max(ans, val)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s=[]
for i in range(h):
    s.append(list(input()))

l=[[0 for i in range(w)] for j in range(h)]
r=[[0 for i in range(w)] for j in range(h)]
u=[[0 for i in range(w)] for j in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            if x == 0:
                l[y][x]=1
            else:
                l[y][x]=l[y][x-1]+1
        
        if s[y][w-x-1] == '.':
            if x == 0:
                r[y][w-x-1]=1
            else:
                r[y][w-x-1]=r[y][w-x]+1

for x in range(w):
    for y in range(h):
        if s[y][x] == '.':
            if y == 0:
                u[y][x]=1
            else:
                u[y][x]=u[y-1][x]+1
        
        if s[h-y-1][x] == '.':
            if y == 0:
                d[h-y-1][x]=1
            else:
                d[h-y-1][x]=d[h-y][x]+1

ans=0
for y in range(h):
    for x in range(w):
        val=l[y][x]+r[y][x]+u[y][x]+d[y][x]-3
        ans=max(ans, val)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
h,w=map(int,input().split())
a = []
for i in range(h):
  l = input()
  l = list(l)
  a.append(l)

L = []
R = []
for i in range(h):
  l = []
  r = []
  k = 0
  m = 0
  for j in range(w):
    if a[i][w-j-1] == ".":
      k += 1
    else:
      k = 0
    if a[i][j] == ".":
      m += 1
    else:
      m = 0
    r.insert(0,k)
    l.append(m)
  R.append(r)
  L.append(l)

D = []
U = []
for i in range(h):
  D.append([])
  U.append([])
for i in range(w):
  k = 0
  m = 0
  for j in range(h):
    if a[j][i] == ".":
      k += 1
    else:
      k = 0
    if a[h-j-1][i] == ".":
      m += 1
    else:
      m = 0
    U[j].append(k)
    D[h-j-1].append(m)
A = numpy.array(L)+numpy.array(R)+numpy.array(U)+numpy.array(D)
print(max(numpy.amax(A-3),0))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

M = [[[0, 0] for i in range(W)] for j in range(H)]
V = [[[False, False] for i in range(W)] for j in range(H)]

def search(grid, w, h, direction):
    cnt = 0

    if direction == 'W':
        for _ in range(W):
            if w + cnt + 1 == W:
                break
            elif grid[h][w + cnt + 1] == '#':
                break

            cnt += 1

    if direction == 'H':
        for _ in range(H):
            if h + cnt + 1 == H:
                break
            elif grid[h + cnt + 1][w] == '#':
                break

            cnt += 1

    return cnt


for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            continue
        else:
            if not V[h][w][1]:
                cnt = search(grid, w, h, 'W')

                for i in range(cnt + 1):
                    V[h][w + i][1] = True
                    M[h][w + i][1] = cnt

for w in range(W):
    for h in range(H):
        if grid[h][w] == '#':
            continue
        else:
            if not V[h][w][0]:
                cnt = search(grid, w, h, 'H')

                for i in range(cnt + 1):
                    V[h + i][w][0] = True
                    M[h + i][w][0] = cnt

m = -1
for h in range(H):
    for w in range(W):
        if M[h][w][0] + M[h][w][1] > m:
            m = M[h][w][0] + M[h][w][1] + 1

print(m)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]


left = [[0]*W for _ in range(H)]
right = [[0]*W for _ in range(H)]
top = [[0]*W for _ in range(H)]
bottom = [[0]*W for _ in range(H)]

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            top[i][j] = cnt
            
for j in range(W):
    cnt = 0
    for i in reversed(range(H)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            bottom[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt
            
for i in range(H):
    cnt = 0
    for j in reversed(range(W)):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt
                        
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,left[i][j]+right[i][j]+top[i][j]+bottom[i][j]-3)
        
print(ans)