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=[input() for ri in range(h)]
table=[0]*(h*w)
for i in range(h):
    p=0
    pre=0
    for j in range(w):
        if s[i][j]=="#":
            if p==0:continue
            for x in range(pre,j):
                table[w*i+x]+=p
            p=0
        else:
            if p==0:
                pre=j
            p+=1
    else:
        if p:
            for x in range(pre,w):table[w*i+x]+=p

for j in range(w):
    p=0
    pre=0
    for i in range(h):
        if s[i][j]=="#":
            if p==0:continue
            for x in range(pre,i):
                table[j+w*x]+=p
            p=0
        else:
            if p==0:pre=i
            p+=1
    else:
        if p:
            for x in range(pre,h):table[j+w*x]+=p
        p=0

print(max(table)-1)

Submission status: Time Limit Exceeded

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

teraseru_H = [[0 for i in range(0,W,1)]for j in range(0,H,1)]
teraseru_W = [[0 for i in range(0,W,1)]for j in range(0,H,1)]

left = -1
for i in range(0,H,1):
    left=-1
    for j in range(0,W,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,j,1):
                    teraseru_H[i][k] = j-left
                left=-1

        else:#"."
            if left==-1:
                left=j
    if left!=-1:
        for k in range(left,W,1):
            teraseru_H[i][k] = W-left
    left=-1

left = -1
for j in range(0,W,1):
    left=-1
    for i in range(0,H,1):
        if S[i][j]=="#":
            if left!=-1:
                for k in range(left,i,1):
                    teraseru_W[k][j] = i-left
                left=-1
        else:#"."
            if left==-1:
                left=i
    if left!=-1:
        for k in range(left,H,1):
            teraseru_W[k][j] = H-left
    left=-1

ans = 0

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

Submission status: Time Limit Exceeded

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

M=[]
for i in range(h):
    M.append(input())

L=[]
for j in range(h):
    Lj=[]
    for i in range(w):
        if M[j][i]=="#":
            Lj.append(0)
        elif i==0:
            Lj.append(1)
        else:
            Lj.append(Lj[i-1]+1)
    L.append(Lj)
R=[]
for j in range(h):
    Rj=[]
    for i in range(w):
        if M[j][w-1-i]=="#":
            Rj.append(0)
        elif i==0:
            Rj.append(1)
        else:
            Rj.append(Rj[i-1]+1)
    R.append(Rj)   
U=[]
for i in range(w):
    Ui=[]
    for j in range(h):
        if M[j][i]=="#":
            Ui.append(0)
        elif j==0:
            Ui.append(1)
        else:
            Ui.append(Ui[j-1]+1)
    U.append(Ui)
D=[]
for i in range(w):
    Di=[]
    for j in range(h):
        if M[h-1-j][i]=="#":
            Di.append(0)
        elif j==0:
            Di.append(1)
        else:
            Di.append(Di[j-1]+1)
    D.append(Di)

s=0
for i in range(w):
    for j in range(h):
        s=max(s,L[j][i]+R[j][w-1-i]+U[i][j]+D[i][h-1-j]-3)

print(s)

Submission status: Time Limit Exceeded

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

M=[]
for i in range(h):
    M.append(input())

L=[]
for j in range(h):
    Lj=[]
    for i in range(w):
        if M[j][i]=="#":
            Lj.append(0)
        elif i==0:
            Lj.append(1)
        else:
            Lj.append(Lj[i-1]+1)
    L.append(Lj)
R=[]
for j in range(h):
    Rj=[]
    for i in range(w):
        if M[j][w-1-i]=="#":
            Rj.append(0)
        elif i==0:
            Rj.append(1)
        else:
            Rj.append(Rj[i-1]+1)
    R.append(Rj[::-1])   
U=[]
for i in range(w):
    Ui=[]
    for j in range(h):
        if M[j][i]=="#":
            Ui.append(0)
        elif j==0:
            Ui.append(1)
        else:
            Ui.append(Ui[j-1]+1)
    U.append(Ui)
D=[]
for i in range(w):
    Di=[]
    for j in range(h):
        if M[h-1-j][i]=="#":
            Di.append(0)
        elif j==0:
            Di.append(1)
        else:
            Di.append(Di[j-1]+1)
    D.append(Di[::-1])

s=0
for i in range(w):
    for j in range(h):
        s=max(s,L[j][i]+R[j][i]+U[i][j]+D[i][j]-3)

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def dfs(i,j,dx,dy,kum):
    visited[i][j] = 1
    if grid[i][j]!="#" and visited[i][j]!=1:
        num[i][j]=max(num[i][j],dfs(i+dx,j+dy,dx,dy,kum+1))
    num[i][j] = max(num[i][j],kum)
    return kum
def main():
    h,w = map(int, input().split())
    grid = []
    for i in range(h):
        s = list(input().rstrip())
        grid.append(s)
    l = [[0]*w for _ in range(h)]
    r = [[0]*w for _ in range(h)]
    d = [[0]*w for _ in range(h)]
    u = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j]!="#":
                if j==0:
                    l[i][j]=1
                else:
                    l[i][j]=l[i][j-1]+1
            if grid[i][j]=="#":
                l[i][j]=0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if grid[i][j]!="#":
                if j==w-1:
                    r[i][j]=1
                else:
                    r[i][j]=r[i][j+1]+1
            if grid[i][j]=="#":
                r[i][j]=0
    for i in range(h):
        for j in range(w):
            if grid[i][j]!="#":
                if i==0:
                    d[i][j]=1
                else:
                    d[i][j]=d[i-1][j]+1
            if grid[i][j]=="#":
                d[i][j]=0
    for i in range(h-1,-1,-1):
        for j in range(w):
            if grid[i][j]!="#":
                if i==h-1:
                    u[i][j]=1
                else:
                    u[i][j]=u[i+1][j]+1
            if grid[i][j]=="#":
                u[i][j]=0
    tmp = 0

    for i in range(h):
        for j in range(w):
            tmp = max(tmp, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)



    print(tmp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
for i in range(h):
  t = input()
  s.append(t)
yokol = [[0 for i in range(w)] for j in range(h)]
yokor = [[0 for i in range(w)] for j in range(h)]
tateu = [[0 for i in range(w)] for j in range(h)]
tated = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
  cnt = 0
  for j in range(w):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      yokol[i][j] = cnt
  cnt = 0
  for j in reversed(range(w)):
    if s[i][j] == '#':
      cnt=0
    else:
      cnt += 1
      yokor[i][j] = cnt

for j in range(w):
  cnt = 0
  for i in range(h):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tateu[i][j] = cnt
  cnt = 0
  for i in reversed(range(h)):
    if s[i][j] == '#':
      cnt =0
    else:
      cnt += 1
      tated[i][j] = cnt

ans = 0
for i in range(h):
  for j in range(w):
    x = yokol[i][j] + yokor[i][j] + tateu[i][j] + tated[i][j] - 3
    ans = max(ans,x)
print (ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
M=[list(input()) for i in range(h)]
D=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
L=[[0]*w for i in range(h)]

for i in range(h):
    c=0
    for j in range(w):
        if M[i][j]=='.':
            c+=1
            R[i][j]=c
        else:
            c=0
for i in range(h):
    c=0
    for j in range(w):
        if M[i][w-1-j]=='.':
            c+=1
            L[i][w-1-j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[i][j]=='.':
            c+=1
            D[i][j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[h-1-i][j]=='.':
            c+=1
            U[h-1-i][j]=c
        else:
            c=0
r=0
for i in range(h):
    for j in range(w):
        r=max(r,R[i][j]+L[i][j]+D[i][j]+U[i][j]-3)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import groupby

h,w=map(int,input().split())
M=np.array([list(input()) for i in range(h)])
L=np.array([[0]*w for i in range(h)])

for i in range(w):
	c=0
	for k,g in groupby(M[:,i]):
		l=len(list(g))
		if k=='.':
			L[c:c+l,i]+=l
		c+=l

for i in range(h):
	c=0
	for k,g in groupby(M[i,:]):
		l=len(list(g))
		if k=='.':
			L[i,c:c+l]+=l
		c+=l

print(np.amax(L)-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import groupby

h,w=map(int,input().split())
M=np.array([list(input()) for i in range(h)])
C=np.array([[0]*w for i in range(h)])
R=np.array([[0]*w for i in range(h)])
L=np.array([[0]*w for i in range(h)])

for i in range(w):
	c=0
	for k,g in groupby(M[:,i]):
		l=len(list(g))
		if k=='#':
			C[c:c+l,i]=0
		else:
			C[c:c+l,i]=l
		c+=l

for i in range(h):
	c=0
	for k,g in groupby(M[i,:]):
		l=len(list(g))
		if k=='#':
			R[i,c:c+l]=0
		else:
			R[i,c:c+l]=l
		c+=l

r=0
for i in range(h):
	for j in range(w):
		r=max(r,C[i][j]+R[i][j]-1)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())

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

cnt = [[0] * w for i in range(h)]

for y in range(h):
    total = 0
    for x in range(w):
        if maze[y][x] == "#":
            total = 0
        elif maze[y][x] == ".":
            total += 1
            cnt[y][x] += total

for x in range(w):
    total = 0
    for y in range(h):
        if maze[y][x] == "#":
            total = 0
        
        elif maze[y][x] == ".":
            total += 1
            cnt[y][x] += total

for y in range(h):
    total = 0
    for x in range(w-1,-1,-1):
        if maze[y][x] == "#":
            total = 0
        elif maze[y][x] == ".":
            total += 1
            cnt[y][x] += total

for x in range(w):
    total = 0
    for y in range(h-1,-1,-1):
        if maze[y][x] == "#":
            total = 0
        
        elif maze[y][x] == ".":
            total += 1
            cnt[y][x] += total

cnt = np.array(cnt)

print(np.max(cnt)-3)

Submission status: Time Limit Exceeded

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

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):
    c = 0
    for j in range(w):
        if x[i][j] == '.':
            l[i][j] = c
            c += 1
        else: c=0


for i in range(h):
    c = 0
    for j in range(w):
        if x[i][w-1-j] == '.':
            r[i][w-1-j] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[j][i] == '.':
            u[j][i] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[h-1-j][i] == '.':
            d[h-1-j][i] = c
            c += 1
        else: c=0

ans = 0
for i in range(h):
    for j in range(w):
        c = l[i][j]+r[i][j]+u[i][j]+d[i][j]
        if x[i][j]=='.':c+=1
        ans = max(ans,c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
up = [[0 for i in range(w)] for j in range(h)]
down = [[0 for i in range(w)] for j in range(h)]
right = [[0 for i in range(w)] for j in range(h)]
left = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    # init up
    if grid[0][i] == ".":
        up[0][i] = 1
    else:
        up[0][i] = 0
    #init down
    if grid[-1][i] == ".":
        down[-1][i] = 1
    else:
        down[-1][i] = 0
for i in range(h):
    #init right
    if grid[i][-1] == ".":
        right[i][-1] = 1
    else:
        right[i][-1] = 0
    
    #init left
    if grid[i][0] == ".":
        left[i][0] = 1
    else:
        left[i][0] = 0
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == ".":
            left[i][j] = left[i][j-1] + 1
        else:
            left[i][j] = 0
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == ".":
            right[i][j] = right[i][j+1] + 1
        else:
            right[i][j] = 0

for i in range(1,h):
    for j in range(w):
        if grid[i][j] == ".":
            up[i][j] = up[i-1][j] + 1
        else:
            up[i][j] = 0
for i in range(h-2,-1,-1):
    for j in range(w):
        if grid[i][j] == ".":
            down[i][j] = down[i+1][j] + 1
        else:
            down[i][j] = 0
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, up[i][j] + down[i][j] + left[i][j] + right[i][j] - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    (H, W) = list(map(int, input().split(" ")))
    S = [list(input()) for i in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    U = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                continue
            L[i][j] = L[i][j-1]+1 if j > 0 else 1
    for i in range(H-1, -1, -1):
        for j in range(W-1, -1 ,-1):
            if S[i][j] == "#":
                continue
            R[i][j] = R[i][j+1]+1 if j < W-1 else 1
    for i in range(H-1, -1, -1):
        for j in range(W):
            if S[i][j] == "#":
                continue
            D[i][j] = D[i+1][j]+1 if i < H-1 else 1
    for i in range(H):
        for j in range(W-1, -1 ,-1):
            if S[i][j] == "#":
                continue
            U[i][j] = U[i-1][j]+1 if i > 0 else 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)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def count_lighted(index, h, w, H, W):
    hindex, windex = index

    count = -1
    prev_count = None
    for x, c in windex[h]:
        if w < x:
            count += c
            break
    for y, c in hindex[w]:
        if h < y:
            count += c
            break

    return count


def build_index(S, H, W):
    hindex = defaultdict(list)
    windex = defaultdict(list)

    hsubindex = defaultdict(int)
    for h in range(H):
        wcounter = 0
        for w in range(W):
            if S[h][w] == '#':
                windex[h].append((w, wcounter))
                hindex[w].append((h, hsubindex[w]))
                wcounter = 0
                hsubindex[w] = 0
            else:
                wcounter += 1
                hsubindex[w] += 1
        windex[h].append((W, wcounter))
    for w in range(W):
        hindex[w].append((H, hsubindex[w]))

    return hindex, windex

def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        s = list(input())
        S.append(s)

    index = build_index(S, H, W)

    max_value = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            count = count_lighted(index, h, w, H, W)
            max_value = max([count, max_value])

    print(max_value)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def count_lighted(index, h, w, H, W):
    hindex, windex = index

    count = -1
    prev_count = None
    for x, c in windex[h]:
        if w < x:
            count += c
            break
    for y, c in hindex[w]:
        if h < y:
            count += c
            break

    return count


def build_index(S, H, W):
    hindex = defaultdict(list)
    windex = defaultdict(list)
    for h in range(H):
        counter = 0
        for w in range(W):
            if S[h][w] == '#':
                windex[h].append((w, counter))
                counter = 0
            else:
                counter += 1
        windex[h].append((W, counter))
    for w in range(W):
        counter = 0
        for h in range(H):
            if S[h][w] == '#':
                hindex[w].append((h, counter))
                counter = 0
            else:
                counter += 1
        hindex[w].append((H, counter))

    return hindex, windex

def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        s = list(input())
        S.append(s)

    index = build_index(S, H, W)

    max_value = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            count = count_lighted(index, h, w, H, W)
            max_value = max([count, max_value])

    print(max_value)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def count_lighted(S, h, w, H, W):
    count = 1
    for y in range(h):
        y = h - y - 1
        if S[y][w] == '#':
            break
        count += 1
    for y in range(h+1, H):
        if S[y][w] == '#':
            break
        count += 1
    for x in range(w):
        x = w - x - 1
        if S[h][x] == '#':
            break
        count += 1
    for x in range(w+1, W):
        if S[h][x] == '#':
            break
        count += 1

    return count


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        s = list(input())
        S.append(s)

    max_value = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            count = count_lighted(S, h, w, H, W)
            max_value = max([count, max_value])

    print(max_value)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# そのマスを含めてLeft, Right, Up, Downにそれぞれ何マス分明かりを照らせるかを配列に記録
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

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

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[tuple(d for d in input()) for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
S = SLs(H)

YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
TENTI = [list(i) for i in zip(*S)]

TATE = []
for s in TENTI:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  TATE.append(yoko)

print(max(max(TATE[j][i]+YOKO[i][j] for j in range(W)) for i in range(H))-1)