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 = ['#' * (w + 2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w + 2)]


yoko = [[0 for i in range(w+2)] for j in range(h+2)]
tate = [[0 for i in range(w+2)] for j in range(h+2)]

for y in range(h+2):
    flag = 0
    for x in range(w+2):
        if s[y][x] == '#':
            for xx in range(flag, x):
                yoko[y][xx] = x - flag
            flag = x + 1
for x in range(w+2):
    flag = 0
    for y in range(h+2):
        if s[y][x] == '#':
            for yy in range(flag, y):
                tate[yy][x] = y - flag
            flag = y + 1

ans = -1
for y in range(h+2):
    for x in range(w+2):
        ans = max(ans, yoko[y][x] + tate[y][x] - 1)
print(ans)

Submission status: Time Limit Exceeded

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

N, M, = map(int, input().split())
MAP = [list(input().strip()) for _ in range(N)]
ANS = [None] * N

for i in range(N):
    ANS[i] = [[0, 0] for _ in range(M)]

for i in range(N):
    for j in range(M):
        t = MAP[i][j]
        
        if t == ".":
            if j != 0:
                ANS[i][j][0] += 1 + ANS[i][j - 1][0]
            else:
                ANS[i][j][0] = 1

    for j in reversed(range(M)):
        t = ANS[i][j][0]
        
        if t > 1:
            if j != 0 and ANS[i][j - 1][0] != 0:
                ANS[i][j - 1][0] = ANS[i][j][0]
                
for j in range(M):
    for i in range(N):
        t = MAP[i][j]
        
        if t == ".":
            if i != 0:
                ANS[i][j][1] += 1 + ANS[i - 1][j][1]
            else:
                ANS[i][j][1] = 1
                
    for i in reversed(range(N)):
        t = ANS[i][j][1]
        
        if t > 1:
            if i != 0 and ANS[i - 1][j][1] != 0:
                ANS[i - 1][j][1] = ANS[i][j][1]

ans = 0
for i in range(N):
    for j in range(M):
        ans = max(ans, sum(ANS[i][j]) - 1)
        
print(ans)

Submission status: Time Limit Exceeded

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


    U = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]

    #L,U
    for i in range(H):
        for j in range(W):
            if S[i][j] != "#":
                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

    #R,D
    for i in reversed(range(H)):
        for j in reversed(range(W)):
            if S[i][j] != "#":
                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 S[i][j] == "#":
                continue

            tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
            ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]

#L,U
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            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

#R,D
for i in reversed(range(H)):
    for j in reversed(range(W)):
        if S[i][j] != "#":
            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 S[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:
import sys
input = sys.stdin.readline
 
 
def main():
    H, W = map(int, input().split())

    S = []
    for _ in range(H):
        S.append(list(input()[:-1]))
    
    U = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j]=='#':
                continue
            if i==0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

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

    R = [[0]*W for _ in range(H)]
    for j in reversed(range(W)):
        for i in range(H):
            if S[i][j]=='#':
                continue
            if j==W-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
    print(ans)

 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip()+"#")

    u = [[0]*W for _ in range(H)]
    d = [[0]*W for _ in range(H)]
    l = [[0]*W for _ in range(H)]
    r = [[0]*W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                u[y][x] = l[y][x] = 0
            else:
                u[y][x] = 1 if y == 0 else u[y-1][x] + 1
                l[y][x] = 1 if x == 0 else l[y][x-1] + 1
    for y in range(H-1,-1,-1):
        for x in range(W-1,-1,-1):
            if S[y][x] == "#":
                d[y][x] = r[y][x] = 0
            else:
                d[y][x] = 1 if y == H-1 else d[y+1][x] + 1
                r[y][x] = 1 if x == W-1 else r[y][x+1] + 1

    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, u[y][x] + d[y][x] + l[y][x] + r[y][x] - 3)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    H,W = map(int, input().split())
    
    S = []
    for _ in range(H):
        S.append(input().strip()+"#") # 末尾に壁を足すと後が楽になる
    S.append("#"*W) # 同上

    # グリッド y,x を含む横方向の "." の最大長
    grid_x = [[0]*(W+1) for _ in range(H)]
    for y in range(H):
        l = r = 0
        for x in range(W+1):
            if S[y][x] == "#":
                r = x
                for i in range(l,r):
                    grid_x[y][i] = r-l
                grid_x[y][x] = 0
                l = x+1

    # グリッド y,x を含む縦方向の "." の最大長
    grid_y = [[0]*W for _ in range(H+1)]
    for x in range(W):
        u = d = 0
        for y in range(H+1):
            if S[y][x] == "#":
                d = y
                for i in range(u,d):
                    grid_y[i][x] = d-u
                grid_y[y][x] = 0
                u = y+1

    ans = 0
    for y in range(H):
        for x in range(W):
            ans = max(ans, grid_x[y][x]+grid_y[y][x]-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC129D - Lamp
def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  # left and upper sides of S
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  # right and under sides
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = max(
        L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W)
    )
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import re


def solve(H: int, W: int, S: "List[str]"):

    
    L = [[0] * W for i in range(H)]
    R = [[0] * W for i in range(H)]
    U = [[0] * W for i in range(H)]
    D = [[0] * W for i in range(H)]
    
    for i in range(H):
        for j in range(W):
            # 左
            if(S[i][j] =='#'):
                L[i][j] = 0
            elif(j == 0):
                L[i][j] = 1
            elif(j >= 1):
                L[i][j] = L[i][j-1] + 1

            # 上
            if(S[i][j] =='#'):
                U[i][j] = 0
            elif(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] =='#'):
                R[i][j] = 0
            elif(j == W-1):
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1

            # 下
            if(S[i][j] =='#'):
                D[i][j] = 0
            elif(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)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, S: "List[str]"):
    from collections import deque

    q = deque()
    ans = 0
    for x in range(H):
        for y in range(W):
            if(S[x][y] == '.'):

                t = 1
                
                # 上
                s = 1
                while(0 <= x-s < H and 0 <= y < W and S[x-s][y] == '.'):
                    t += 1
                    s += 1

                # 下
                s = 1
                while(0 <= x+s < H and 0 <= y < W and S[x+s][y] == '.'):
                    t += 1
                    s += 1

                # 左
                s = 1
                while(0 <= x < H and 0 <= y-s < W and S[x][y-s] == '.'):
                    t += 1
                    s += 1

                # 右
                s = 1
                while(0 <= x < H and 0 <= y+s < W and S[x][y+s] == '.'):
                    t += 1
                    s += 1

                ans = max(ans, t)

    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
g=["#"*(w+1)]+["#"+input()+"#"for _ in range(h)]+["#"*(w+1)]
def check(i,j):
  global g
  a=1
  k=1
  while g[i-k][j]!="#":k+=1;a+=1
  k=1
  while g[i+k][j]!="#":k+=1;a+=1
  k=1
  while g[i][j-k]!="#":k+=1;a+=1
  k=1
  while g[i][j+k]!="#":k+=1;a+=1
  return a
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if g[i][j]!="#":ans=max(ans,check(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
field=[0]+["#"+input()+"#" for i in range(h)]+[0]
field[0],field[-1]="#"*(w+2),"#"*(w+2)
l,r,u,d=[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[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 field[i][j]=="#":continue
    l[i][j]=l[i][j-1]+1
    u[i][j]=u[i-1][j]+1
for i in range(1,h+1)[::-1]:
  for j in range(1,w+1)[::-1]:
    if field[i][j]=="#":continue
    r[i][j]=r[i][j+1]+1
    d[i][j]=d[i+1][j]+1
ans=0
for i in range(h+2):
  for j in range(w+2):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if c>ans:ans=c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int,input().split())
S = []
for _ in range(H):
    S.append(input())
S = np.array(S)

h_val = 0
for i in range(H):
    max_count = 0
    count = 0
    for j in range(W):
        if S[i][j] == '.':
            count += 1
        else:
            if max_count < count:
                max_count = count
            count = 0
    if max_count < count:
        max_count = count

    if h_val < max_count:
        h_val = max_count


w_val = 0
for i in range(W):
    max_count = 0
    count = 0
    for j in range(H):
        if S[j][i] == '.':
            count += 1
        else:
            if max_count < count:
                max_count = count
            count = 0
    if max_count < count:
        max_count = count
    if w_val < max_count:
        w_val = max_count

print(h_val+w_val-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
raw = []
for _ in range(h):
  raw.append(input())
ans = [[0 for _ in range(w)] for _ in range(h)]
#print(raw)
#print(ans)
for x in range(h):
  tmp = 0
  for y in range(w):
    if raw[x][y] == '.':
      tmp += 1
    else:
      for j in range(tmp):
        ans[x][y-j-1] += tmp
      tmp = 0
  for j in range(tmp):
    ans[x][y-j] += tmp
for y in range(w):
  tmp = 0
  for x in range(h):
    if raw[x][y] == '.':
      tmp += 1
    else:
      for i in range(tmp):
        ans[x-i-1][y] += tmp
      tmp = 0
  for i in range(tmp):
    ans[x-i-1][y] += tmp
can = []
for x in range(h):
  can.append(max(ans[x]))
print(max(can)-1)

Submission status: Time Limit Exceeded

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

cnt = [[0]*W for _ in range(H)] # ans[行][列],Sと同じsize
#print(ans)

# 行についてみる
for i in range(H):
    done = [0]*W # 0で初期化
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif done[j]: # 0ならばFalse,それ以外はTrue。done[j] == 1ならばcontinue
            continue
        length = 0
        while j + length < W:
            if S[i][j+length] == '#':
                break
            length += 1
        for k in range(length):
            cnt[i][j+k] += length
            done[j+k] = 1 # 一度見たところは1にしておく

# 列についてみる
for j in range(W):
    done = [0]*H # 0で初期化
    for i in range(H):
        if S[i][j] == '#':
            continue
        elif done[i]: # 0ならばFalse,それ以外はTrue。done[i] == 1ならばcontinue
            continue
        length = 0
        while i + length < H:
            if S[i+length][j] == '#':
                break
            length += 1
        for k in range(length):
            cnt[i+k][j] += length
            done[i+k] = 1 # 一度見たところは1にしておく

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, cnt[i][j]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h, w = li()
grid = [lc() for _ in range(h)]

# 左側の照らせるマス
left = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            left[row][col] = cur
        else:
            cur = 0

# 右側の照らせるマス
right = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w):
        if grid[row][col] == ".":
            cur += 1
            right[row][col] = cur
        else:
            cur = 0

# 上側の照らせるマス
up = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            up[row][col] = cur
        else:
            cur = 0

# 下側の照らせるマス
down = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h):
        if grid[row][col] == ".":
            cur += 1
            down[row][col] = cur
        else:
            cur = 0

# 最大値
ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, left[row][col] + right[row][col] + up[row][col] + down[row][col])

print(ans-3)

Submission status: Time Limit Exceeded

Solution code:
t,*grid = open(0)
h,w = map(int,t.split())
L,R,U,D = eval("[0]*((w+2)*(h+2)),"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]==".":
			L[(y+1)*(w+2)+x+1] = L[(y+1)*(w+2)+x]+1
		if grid[y][w-x-1]==".":
			R[(y+1)*(w+2)+w-x] = R[(y+1)*(w+2)+w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]==".":
			U[(y+1)*(w+2)+x+1] = U[y*(w+2)+x+1]+1
		if grid[h-y-1][x]==".":
			D[(h-y)*(w+2)+x+1] = D[(h-y+1)*(w+2)+x+1]+1
print(max(l+r+u+d-3 for l,r,u,d in zip(L,R,U,D)))

Submission status: Time Limit Exceeded

Solution code:
t,*l=open(0)
h,w=map(int,t.split())
grid = [[c=="."for c in C]for C in l]
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		L[y+1][x+1] = (L[y+1][x]+1)*grid[y][x]
		R[y+1][w-x] = (R[y+1][w-x+1]+1)*grid[y][w-x-1]
for x in range(w):
	for y in range(h):
		U[y+1][x+1] = (U[y][x+1]+1)*grid[y][x]
		D[h-y][x+1] = (D[h-y+1][x+1]+1)*grid[h-y-1][x]
print(max(L[y][x] + R[y][x] + U[y][x] + D[y][x] -3 for y in range(1,h+1) for x in range(1,w+1)))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
grid = [[c=="."for c in input()]for _ in range(h)]
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]:
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]:
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]:
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]:
			D[h-y][x+1] = D[h-y+1][x+1]+1
a = 0
for y in range(1,h+1):
	for x in range(1,w+1):
		a = max(a, L[y][x] + R[y][x] + U[y][x] + D[y][x] -3)
print(a)

Submission status: Time Limit Exceeded

Solution code:
t,*grid = open(0)
h,w = map(int,t.split())
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]==".":
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]==".":
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]==".":
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]==".":
			D[h-y][x+1] = D[h-y+1][x+1]+1
a = 0
for y in range(1,h+1):
	for x in range(1,w+1):
		a = max(a, L[y][x] + R[y][x] + U[y][x] + D[y][x] -3)
print(a)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "#": continue
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "#": break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "#": continue
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "#": break
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = [0]*H
    A = [[0] * W for i in range(H)]
    for i in range(H):
        grid[i] = input().rstrip()

    for i in range(H):
        L = grid[i]
        AL = A[i]
        prev = 0
        AL[0] = 0 if L[0] == '#' else 1
        for j in range(1, W):
            if L[j] == '#':
                AL[j] = 0
            else:
                AL[j] = AL[j-1] + 1
        for j in range(W-1)[::-1]:
            if L[j+1] == '#' or L[j] == '#':
                continue
            else:
                AL[j] = AL[j+1]

    V = [[0] * W for i in range(H)]
    for i in range(W):
       
        V[0][i] = 0 if grid[0][i] == '#' else 1
        for j in range(1, H):
            if grid[j][i] == '#':
                continue
            V[j][i] = V[j-1][i] + 1
        for j in range(H-1)[::-1]:
            if grid[j+1][i] == '#' or grid[j][i] == '#':
                continue
            else:
                V[j][i] = V[j+1][i]
    m = 0
    for i in range(H):
        for j in range(W):
            m = max(m, A[i][j] + V[i][j] - 1)
        #print(*[max(0, A[i][j] + V[i][j] - 1) for j in range(W)])
    print(m)
main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input() for _ in range(H)]
L,R,D,U = [[[0]*W for _ in range(H)] for i in range(4)]
 
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            L[h][w] = L[h][w-1]+1
            U[h][w] = U[h-1][w]+1
        if S[h][W-1-w] == '.':
            R[h][-w-1] = R[h][-w]+1
        if S[H-1-h][w] == '.':
            D[-h-1][w] = D[-h][w]+1
 
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(ans,L[h][w]+U[h][w]+R[h][w]+D[h][w]-3)
 
print(ans)

Submission status: Time Limit Exceeded

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

S = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]

for h in range(H):
    done = [False] * W
    for w in range(W):
        if S[h][w] == '#': continue
        if done[w]: continue

        tmp = w
        cnt = 0
        while tmp < W:
            if S[h][tmp] == '#': break
            cnt += 1
            tmp += 1

        for i in range(w, tmp):
            memo[h][i] += cnt
            done[i] = True

for w in range(W):
    done = [False] * H
    for h in range(H):
        if S[h][w] == '#': continue
        if done[h]: continue

        tmp = h
        cnt = 0
        while tmp < H:
            if S[tmp][w] == '#': break
            cnt += 1
            tmp += 1

        for i in range(h, tmp):
            memo[i][w] += cnt
            done[i] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, memo[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())

grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = list(input())

L = np.array([[0] * W for h in range(H)])
U = np.array([[0] * W for h in range(H)])
R = np.array([[0] * W for h in range(H)])
D = np.array([[0] * W for h in range(H)])

for h in range(H):
    for w in range(W):

        if grid[h][w] != '#':
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w - 1] + 1
            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h - 1][w] + 1

        if grid[H - h - 1][W - w - 1] != '#':
            if w == 0:
                R[H - h - 1][W - w - 1] = 1
            else:
                R[H - h - 1][W - w - 1] = R[H - h - 1][W - w] + 1
            if h == 0:
                D[H - h - 1][W - w - 1] = 1
            else:
                D[H - h - 1][W - w - 1] = D[H - h][W - w - 1] + 1

print(max((L + R + U + D - 3).ravel()))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = list(input())

L = [[0] * W for h in range(H)]
U = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            L[h][w] = 0
            U[h][w] = 0
        else:
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w - 1] + 1
            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h - 1][w] + 1

        if grid[H - h - 1][W - w - 1] == '#':
            R[H - h - 1][W - w - 1] = 0
            D[H - h - 1][W - w - 1] = 0
        else:
            if w == 0:
                R[H - h - 1][W - w - 1] = 1
            else:
                R[H - h - 1][W - w - 1] = R[H - h - 1][W - w] + 1
            if h == 0:
                D[H - h - 1][W - w - 1] = 1
            else:
                D[H - h - 1][W - w - 1] = D[H - h][W - w - 1] + 1
            


import numpy as np
print(max((np.array(L) + np.array(R) + np.array(U) + np.array(D) - 3).ravel()))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = list(input())

L = [[0] * W for h in range(H)]
U = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            L[h][w] = 0
            U[h][w] = 0
        else:
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w - 1] + 1

            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h - 1][w] + 1

    for w in range(W - 1, -1, -1):
        if grid[h][w] == '#':
            R[h][w] = 0
        else:
            if w == W - 1:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w + 1] + 1

for h in range(H - 1, -1, -1):
    for w in range(W):
        if grid[h][w] == '#':
            D[h][w] = 0
        else:
            if h == H - 1:
                D[h][w] = 1
            else:
                D[h][w] = D[h + 1][w] + 1

import numpy as np
print(max((np.array(L) + np.array(R) + np.array(U) + np.array(D) - 3).ravel()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())

grid = [[] for h in range(H)]
for h in range(H):
    grid[h] = [-1 if _ == '#' else 0 for _ in input()]
    grid[h] = [-1] + grid[h] + [-1]
    #print(grid[h])
    count = 0
    for w in range(W + 1):
        if grid[h][w] == -1 and grid[h][w + 1] == 0:
            count = 1
            tmp = w + 1
        elif grid[h][w] == 0 and grid[h][w + 1] == 0:
            count += 1
        elif grid[h][w] == 0 and grid[h][w + 1] == -1:
            grid[h][tmp: w + 1] = [count] * (w + 1 - tmp)
            count = 0
    #print(grid)
#print(grid)
pad_grid = [[-1] * (W + 2)] + grid + [[-1] * (W + 2)]
#pad_grid
#print(pad_grid)
t_grid = np.transpose(pad_grid)

for h in range(1, W + 1):
    for w in range(H + 1):
        if t_grid[h][w] == -1 and t_grid[h][w + 1] != 0:
            count = 1
            tmp = w + 1
        elif t_grid[h][w] != -1 and t_grid[h][w + 1] != -1:
            count += 1
        elif t_grid[h][w] != -1 and t_grid[h][w + 1] == -1:
            t_grid[h][tmp: w + 1] += count - 1
            count = 0
    #print(t_grid)
print(max(t_grid.ravel()))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
S = [(input()+'#') for i in range(h)]+['#'*(w+1)]
Rows = []
Columns = []
for i in range(h):
    Row = []
    row = 0
    for j in range(w+1):
        if S[i][j] == '.':
            row += 1
        else:
            if row > 0:
                Row += [row]
            row = 0
            Row += [row]
    Rows += [Row]
for j in range(w):
    Column = []
    column = 0
    for i in range(h+1):
        if S[i][j] == '.':
            column += 1
        else:
            if column > 0:
                Column += [column]
            column = 0
            Column += [column]
    Columns += [Column]
mRows = []
mColumns = []
for i in range(h):
  mRow= []
  for j in range(len(Rows[i])):
    mRow += [Rows[i][j]]*max(1,Rows[i][j])
  mRows += [mRow]
for i in range(w):
  mColumn= []
  for j in range(len(Columns[i])):
    mColumn += [Columns[i][j]]*max(1,Columns[i][j])
  mColumns += [mColumn]
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,mRows[i][j]+mColumns[j][i]-1)
print(ans)