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 = [int(i) for i in input().split()]

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

light = [[0 for i in range(w)] for j in range(h)]

for j in range(h):
    point = 0
    for i in range(w):
        if s[j][i] == ".":
            point += 1
            light[j][i] += point
        else:
            point = 0

    point = 0
    for i in range(w):
        if s[j][-1-i] == ".":
            point += 1
            light[j][-1-i] += point
        else:
            point = 0

for j in range(w):
    point = 0
    for i in range(h):
        if s[i][j] == ".":
            point += 1
            light[i][j] += point
        else:
            point = 0

    point = 0
    for i in range(h):
        if s[-1-i][j] == ".":
            point += 1
            light[-1-i][j] += point
        else:
            point = 0

ans = 0
for i in range(h):
    ans = max(ans, max(light[i]))
print(ans-3)

Submission status: Time Limit Exceeded

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

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
G = [input() for k in range(H)]
yoko = [[0 for k in range(W)] for k in range(H)]
tate = [[0 for k in range(W)] for k in range(H)]


for h in range(H):
    t = 0
    s = 0
    for w in range(W):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,w):
                    yoko[h][k] = t
            s = w+1
            t = 0
    if t > 0:
        for k in range(s,W):
            yoko[h][k] = t


for w in range(W):
    t = 0
    s = 0
    for h in range(H):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,h):
                    tate[k][w] = t
            s = h+1
            t = 0
    if t > 0:
        for k in range(s,H):
            tate[k][w] = t

ans = 0
for w in range(W):
    for h in range(H):
        ans = max(ans,tate[h][w]+yoko[h][w]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

H, W = map(int, input().split())
state = np.array([list(input()) for _ in range(H)])


def light(row, col, state):
    lighted_count = 0
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col1 += 1
        if col1 >= W:
            break
        next = state[row, col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        lighted_count += 1
        col2 -= 1
        if col2 < 0:
            break
        next = state[row, col2]

    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row1 += 1
        if row1 >= H:
            break
        next = state[row1, col]

    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        lighted_count += 1
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2, col]

    lighted_count -= 3
    return lighted_count



def blank_fun(state):
    blank_list = []
    for i, item in np.ndenumerate(state):
        if item == '.':
            blank_list.append(i)
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    blank_count_now = light(row, col, state)

    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
    for i in range(h):
        for j in range(1,w):
            t=-1*(j+1)
            if l[i][t]==".":
                x[i][t]=max(x[i][t],x[i][t+1])

    for i in range(w):
        for j in range(h):
            if j==0 and l[j][i]==".":
                y[j][i]=1
            elif l[j][i]==".":
                y[j][i]=y[j-1][i]+1
    for i in range(w):
        for j in range(1,h):
            t=-1*(j+1)
            if l[t][i]==".":
                y[t][i]=max(y[t][i],y[t+1][i])
    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(['#'] + list(input()) + ['#'])
grid.append(['#'] * (w+2))

l = [[0] * (w+2) for _ in range(h+2)]
r = [[0] * (w+2) for _ in range(h+2)]
u = [[0] * (w+2) for _ in range(h+2)]
d = [[0] * (w+2) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == '#':
            continue
        else:
            l[i][j] = l[i][j-1]+1
            u[i][j] = u[i-1][j]+1

for i in range(h+1,0,-1):
    for j in range(w+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            r[i][j] = r[i][j+1]+1
            d[i][j] = d[i+1][j]+1

ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        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:
H,W = map(int, input().split())
S = [list(input()) for _ in range(H)]

w_score = [[0]*W for _ in range(H)]
h_score = [[0]*W for _ in range(H)]

begin = -1
streak = 1
for hi in range(H):
    for wi in range(W):
        if begin == -1 and S[hi][wi]=='.':
            begin = wi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if wi ==W-1 or(begin != -1 and S[hi][wi]=='#'):
            if wi == W-1 and S[hi][wi]=='.':
                w_score[hi][wi]=streak
            for i in range(W)[begin:wi]:
                w_score[hi][i] = streak
            streak = 1
            begin = -1

# for s in w_score:
#     print(s)
# print('-'*10)

begin = -1
streak = 1
for wi in range(W):
    for hi in range(H):
        if begin == -1 and S[hi][wi]=='.':
            begin = hi
        elif begin != -1 and S[hi][wi] == '.':
            streak += 1
        if hi ==H-1 or(begin != -1 and S[hi][wi]=='#'):
            if hi == H-1 and S[hi][wi]=='.':
                h_score[hi][wi]= streak
            for i in range(H)[begin:hi]:
                h_score[i][wi] = streak
            streak = 1
            begin = -1

# for s in h_score:
#     print(s)
# print('-'*10)

ans = 0
score = [[0]*W for _ in range(H)]
for hi in range(H):
    for wi in range(W):
        w =w_score[hi][wi] 
        h= h_score[hi][wi] 
        score_ = w+h
        score_ += -1 if w>0 and h>0 else 0
        ans = max(ans,score_)
        score[hi][wi] = score_
        
# for s in score:
#     print(s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[i][x] = cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[i][x] = cou    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[x][i] += cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[x][i] += cou

print(max(max(Grid1[i]) for i in range(H))-1)

Submission status: Time Limit Exceeded

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

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

light = [[[0, 0, 0, 0] for i in range(w)] for j in range(h)]

for j in range(h):
    point = 0
    for i in range(w):
        if s[j][i] == ".":
            point += 1
            light[j][i][0] += point
        else:
            point = 0

    point = 0
    for i in range(w):
        if s[j][-1-i] == ".":
            point += 1
            light[j][-1-i][1] += point
        else:
            point = 0

for j in range(w):
    point = 0
    for i in range(h):
        if s[i][j] == ".":
            point += 1
            light[i][j][2] += point
        else:
            point = 0

    point = 0
    for i in range(h):
        if s[-1-i][j] == ".":
            point += 1
            light[-1-i][j][3] += point
        else:
            point = 0

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, sum(light[i][j]) -3)

print(ans)

Submission status: Time Limit Exceeded

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

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i][j] == '#':
            continue
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
L = np.zeros([h + 2, w + 2], dtype=int)
U = np.zeros([h + 2, w + 2], dtype=int)
R = np.zeros([h + 2, w + 2], dtype=int)
D = np.zeros([h + 2, w + 2], dtype=int)
for i in range(h):
    for j in range(w):
        if x[i][j] == '.':
            L[i + 1, j + 1] = L[i + 1, j] + 1
            U[i + 1, j + 1] = U[i, j + 1] + 1
        if x[h - i - 1][w - j - 1] == '.':
            R[h - i, w - j] = R[h - i, w - j + 1] + 1
            D[h - i, w - j] = D[h - i + 1, w - j] + 1
ans = (L + R + D + U).max() - 3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
G_jouge = []
G_sayu = []
for h in range(H):
    G_migi = []
    G_hidari = []
    r = 0
    l = 0
    for w in range(W):
        if S[h][w] == '.':
            G_migi.append(r)
            r += 1
        else:
            r = 0
            G_migi.append(r)
        if S[h][W-1-w] == '.':
            G_hidari.append(l)
            l += 1
        else:
            l = 0
            G_hidari.append(l)
    G_sayu.append([G_hidari[W-1-i]+G_migi[i] for i in range(W)])
for w in range(W):
    G_migi = []
    G_hidari = []
    r = 0
    l = 0
    for h in range(H):
        if S[h][w] == '.':
            G_migi.append(r)
            r += 1
        else:
            r = 0
            G_migi.append(r)
        if S[H-1-h][w] == '.':
            G_hidari.append(l)
            l += 1
        else:
            l = 0
            G_hidari.append(l)
    G_jouge.append([G_hidari[H-1-i]+G_migi[i] for i in range(H)])

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,G_sayu[h][w]+G_jouge[w][h])
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
T=[["#"]*(w+2)]
T.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
T.append(["#"]*(w+2))
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(1,h+1):
  for j in range(1,w+1):
    if T[i][j]==".":
      if j==1:
        L[i-1][j-1]=1
      else:
        L[i-1][j-1]=L[i-1][j-2]+1
      if i==1:
        U[i-1][j-1]=1
      else:
        U[i-1][j-1]=U[i-2][j-1]+1
    if T[h+1-i][w+1-j]==".":
      if j==1:
        R[h-i][w-j]=1
      else:
        R[h-i][w-j]=R[h-i][w-j+1]+1
      if i==1:
        D[h-i][w-j]=1
      else:
        D[h-i][w-j]=D[h-i+1][w-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:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
yo = [['@'] * W for _ in range(H)]
ta = [['@'] * W for _ in range(H)]


def yoko(y, x):
    ret1 = 0
    xx = x
    while xx + 1 <= W - 1 and S[y][xx + 1] != '#':
        ret1 += 1
        xx += 1
    xxx = x
    ret2 = 0
    while 0 <= xxx - 1 and S[y][xxx - 1] != '#':
        ret2 += 1
        xxx -= 1
    ret3 = ret1 + ret2
    for i in range(xxx, xx + 1):
        yo[y][i] = ret3
    return ret3


def tate(y, x):
    ret1 = 0
    yy = y
    while 0 <= yy - 1 and S[yy - 1][x] != '#':
        ret1 += 1
        yy -= 1
    yyy = y
    ret2 = 0
    while yyy + 1 <= H - 1 and S[yyy + 1][x] != '#':
        ret2 += 1
        yyy += 1
    ret3 = ret1 + ret2
    for i in range(yy, yyy + 1):
        ta[i][x] = ret3
    return ret3


for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if yo[y][x] == '@':
            yoko(y, x)
        if ta[y][x] == '@':
            tate(y, x)
        else:
            continue

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        else:
            ans = max(ans, ta[y][x] + yo[y][x] + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
MAP = [list('#' + input() + '#') for j in range(H)]
MAP.insert(0,['#' for i in range(W + 2)])
MAP.append(['#' for i in range(W + 2)])
MAP2 = copy.deepcopy(MAP)


def line(MAP):
    for i in range(1, H + 2):
        start = 1
        goal = 1
        count = 0
        for j in range(1, W + 2):
            if MAP[i][j] == '.':
                goal += 1
                count += 1
            else:
                for x in range(start, goal):
                    MAP[i][x] = count
                goal += 1
                start = goal
                count = 0
def column(MAP2):
    for j in range(1, W + 2):
        start = 1
        goal = 1
        count = 0
        for i in range(1, H + 2):
            if MAP2[i][j] == '.':
                goal += 1
                count += 1
            else:
                for x in range(start, goal):
                    MAP2[x][j] = count
                goal += 1
                start = goal
                count = 0
line(MAP)
column(MAP2)

ans = 0
for i, line in enumerate(MAP):
    for j, dot in enumerate(line):
        if dot != '#':
            ans = max(ans, MAP[i][j] + MAP2[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

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

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

max_=0
for i in range(h):
  for j in range(w):
    if li[i][j]=='.':
      count=1
      for k in range(j+1,w):
        if li[i][k]=='.':
          count+=1
        else:
          break
      for k in range(j-1,-1,-1):
        if li[i][k]=='.':
          count+=1
        else:
          break
      for k in range(i+1,h):
        if li[k][j]=='.':
          count+=1
        else:
          break
      for k in range(i-1,-1,-1):
        if li[k][j]=='.':
          count+=1
        else:
          break
      max_=max(max_,count)
print(max_)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
 
S=[input() for i in range(H)]
color1 = -1
color_list1 = [[-1 for j in range(W)] for i in range(H)]
color_num1 = [0 for i in range(H*W)]
flag=True
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            flag=True
        else:
            if j==0:
                flag=True
            if flag:
                color1+=1
                color_list1[i][j]=color1
                color_num1[color1]+=1
                flag=False
            else:
                color_list1[i][j]=color1
                color_num1[color1]+=1
 
color2 = -1
color_list2 = [[-1 for j in range(W)] for i in range(H)]
color_num2 = [0 for i in range(H*W)]
flag=True
for j in range(W):
    for i in range(H):
        if S[i][j]=="#":
            flag=True
        else:
            if i==0:
                flag=True
            if flag:
                color2+=1
                color_list2[i][j]=color2
                color_num2[color2]+=1
                flag=False
            else:
                color_list2[i][j]=color2
                color_num2[color2]+=1
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            ans=max(color_num1[color_list1[i][j]]+color_num2[color_list2[i][j]]-1,ans)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(['#'] + list(input()) + ['#'])
grid.append(['#'] * (w+2))

l = [[0] * (w+2) for _ in range(h+2)]
r = [[0] * (w+2) for _ in range(h+2)]
u = [[0] * (w+2) for _ in range(h+2)]
d = [[0] * (w+2) for _ in range(h+2)]

#for i in range(h+2):
#    print(grid[i])

for i in range(1,h+1):
    for j in range(1,w+1):
        if grid[i][j] == '#':
            continue
        else:
            l[i][j] = l[i][j-1]+1

for i in range(1,h+1):
    for j in range(w+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            r[i][j] = r[i][j+1]+1

for j in range(1,w+1):
    for i in range(1,h+1):
        if grid[i][j] == '#':
            continue
        else:
            u[i][j] = u[i-1][j]+1

for j in range(1,w+1):
    for i in range(h+1,0,-1):
        if grid[i][j] == '#':
            continue
        else:
            d[i][j] = d[i+1][j]+1

ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        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:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
yo = [['@'] * W for _ in range(H)]
ta = [['@'] * W for _ in range(H)]


def yoko(y, x):
    ret1 = 0
    xx = x
    while xx + 1 <= W - 1 and S[y][xx + 1] != '#':
        ret1 += 1
        xx += 1
    xxx = x
    ret2 = 0
    while 0 <= xxx - 1 and S[y][xxx - 1] != '#':
        ret2 += 1
        xxx -= 1
    ret3 = ret1 + ret2
    for i in range(xxx, xx + 1):
        yo[y][i] = ret3
    return ret3


def tate(y, x):
    ret1 = 0
    yy = y
    while 0 <= yy - 1 and S[yy - 1][x] != '#':
        ret1 += 1
        yy -= 1
    yyy = y
    ret2 = 0
    while yyy + 1 <= H - 1 and S[yyy + 1][x] != '#':
        ret2 += 1
        yyy += 1
    ret3 = ret1 + ret2
    for i in range(yy, yyy + 1):
        ta[i][x] = ret3
    return ret3


for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if yo[y][x] == '@':
            yoko(y, x)
        if ta[y][x] == '@':
            tate(y, x)
        else:
            continue

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        else:
            ans = max(ans, ta[y][x] + yo[y][x] + 1)
print(ans)

Submission status: Time Limit Exceeded

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


def solve(H: int, W: int, S: "List[str]"):
    L = [[0 for _ in range(W)] for _ in range (H)]
    R = [[0 for _ in range(W)] for _ in range (H)]
    D = [[0 for _ in range(W)] for _ in range (H)]
    U = [[0 for _ in range(W)] for _ 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] = L[i][j-1] + 1
            else:
                L[i][j] = 1

        for j in reversed(range(W)):
            if S[i][j] == "#":
                R[i][j] = 0
            elif j < W-1:
                R[i][j] = R[i][j+1] + 1
            else:
                R[i][j] = 1

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

        for i in reversed(range(H)):
            if S[i][j] == "#":
                D[i][j] = 0
            elif i < H-1:
                D[i][j] = D[i+1][j] + 1
            else:
                D[i][j] = 1

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

    print(res)





# 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:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###
 
H, W = mi()
S = []
#周りを囲う
S.append('#'*(W+2))
for _ in range(H):
  S.append(''.join(('#',input(),'#')))
S.append('#'*(W+2))
 
#まずは行を走査
#各行各セルの横向きに繋がったマスを入れる配列を作る
hnum = [[0]*(W+2) for _ in range(H+2)] #添字を揃えるためにダミーを入れる
 
for i in range(1, H+2): #1～H以外はダミーだが、H+1も走査しないと障害物にぶつからず、処理されない。iはその時の行番号を示す
  noww = 0 #今見ている列の番号
  tmphnum = 0 #現状繋がっているセルの数を入れていく
  tmphnumstartidx = -1 #繋がり始めたセルの列番号。最初は「未発見」の意を表す-1を入れておく
  for cell in S[i]: #行の各セルを走査
    if cell=='#': #hnumは元々0が入っているので今回いじらなくていい
      #ただし、連結が途切れた場合の処理が必要
      if tmphnumstartidx != -1:
        #連結部分のhnumに、tmphnumを代入する
        for j in range(tmphnumstartidx, noww): #1つ前まで全て
          hnum[i][j] = tmphnum
        tmphnumstartidx = -1 #フラグを兼ねているので、-1にリセット
        tmphnum = 0 #連結セル数も、途切れたので0にリセット
    else: #セルが'.'だった場合
      #繋がるセルの中で一番左端なら、繋がり始めの処理をする
      if tmphnumstartidx == -1:
        tmphnum = 1
        tmphnumstartidx = noww
      else: #左のセルに連結したなら
        tmphnum += 1 #連結セルが1個増えた
    #なんにせよ、noww+=1して次のセル番号に変える
    noww += 1
 
#今度は列を走査して、ansを最大値で更新していく
ans = 0
#列は文字列になっていないので、計算は遅いかもしれないが、直接S[][]で読んでいくことにする
 
#今度はiが列番号を表しているので注意！！
for i in range(1, W+2): #1～W以外はダミーだが、W+1も処理しないと障害物にぶつからず処理されないから困る。iはその時の列番号を示す
  tmpwnum = 0 #現状繋がっているセルの数を入れていく
  tmpwnumstartidx = -1 #繋がり始めたセルの行番号。最初は「未発見」の意を表す-1を入れておく
  #今度はjが行番号を表しているので注意！！
  for j in range(1, H+2): #列の各セルを走査
    cell = S[j][i] #わかりやすくするためcellに代入
    if cell=='#': #hnumは元々0が入っているので今回いじらなくていい
      #ただし、連結が途切れた場合の処理が必要
      #ちなみに、#の場合が答えになるはずはないので、答えの判定はしなくていい
      if tmpwnumstartidx != -1:
        #連結が途切れた場合の処理、つまり一つ前のセルまでの答え判定
        #pは、遡って見ているセルの行番号を示す
        for p in range(tmpwnumstartidx, j): #1つ前まで全て
          ans = max(tmpwnum + hnum[p][i] - 1, ans)
        tmpwnumstartidx = -1 #フラグを兼ねているので、-1にリセット
        tmpwnum = 0 #連結セル数も、途切れたので0にリセット
    else: #セルが'.'だった場合
      #繋がるセルの中で一番上なら、繋がり始めの処理をする
      if tmpwnumstartidx == -1:
        tmpwnum = 1
        tmpwnumstartidx = j
      else: #左のセルに連結したなら
        tmpwnum += 1 #連結セルが1個増えた
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[[0, 0] for w in range(W + 2)] for h in range(H + 2)]
ans = 0
for i in range(H):
  S[i] = input()
  for j in range(W):
    if S[i][j] == '.':
      if L[i + 1][j][0] == 0:
        k = j
        while k < W and S[i][k] == '.':
          L[i + 1][j + 1][0] += 1
          k += 1
      else:
        L[i + 1][j + 1][0] = L[i + 1][j][0]
for j in range(W):
  for i in range(H):
    if S[i][j] == '.':
      if L[i][j + 1][1] == 0:
        k = i
        while k < H and S[k][j] == '.':
          L[i + 1][j + 1][1] += 1
          k += 1
        ans = max(sum(L[i + 1][j + 1]) - 1, ans)
      else:
        L[i + 1][j + 1][1] = L[i][j + 1][1]
        ans = max(sum(L[i + 1][j + 1]) - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

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

s = [[j for j in list(str(input()))] for i in range(h)]

board = [[[0 for _ in range(4)] for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == ".":
            cnt_continue += 1
        else:
            cnt_continue = 0
        board[i][j][0] = cnt_continue

for i in range(h):
    cnt_continue = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            cnt_continue += 1
        else:
            cnt_continue = 0
        board[i][j][1] = cnt_continue

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == ".":
            cnt_continue += 1
        else:
            cnt_continue = 0
        board[j][i][2] = cnt_continue

for i in range(w):
    cnt_continue = 0
    for j in reversed(range(h)):
        if s[j][i] == ".":
            cnt_continue += 1
        else:
            cnt_continue = 0
        board[j][i][3] = cnt_continue

ans = 0

for i in range(h):
    for j in range(w):
        v = sum(board[i][j]) - 3
        ans = max(ans, v)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
if sys.version[0] == '2':
    input, range = raw_input, xrange
import numpy as np
H, W = map(int, input().split())
B = [input() for _ in range(H)]
board = np.zeros((H, W), dtype=int)
for r, row in enumerate(B):
    for c, col in enumerate(row):
        board[r][c] = 1 if col == "." else 0
cnt = np.zeros((H, W), dtype=int)
cnt[:, :] = 1

for _ in range(4):
    R, C = cnt.shape
    for c in range(C):
        now = 0
        for r in range(R):
            if board[r][c]:
                cnt[r][c] += now
                now += 1
            else:
                now = 0
    board = np.rot90(board, k=-1)
    cnt = np.rot90(cnt, k=-1)
print(np.max(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
L = np.zeros([h + 2, w + 2], dtype=int)
U = np.zeros([h + 2, w + 2], dtype=int)
for i in range(h):
    for j in range(w):
        if x[i][j] == '.':
            L[i + 1, j + 1] = L[i + 1, j] + 1
            U[i + 1, j + 1] = U[i, j + 1] + 1
R = np.zeros([h + 2, w + 2], dtype=int)
D = np.zeros([h + 2, w + 2], dtype=int)
for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if x[i][j] == '.':
            R[i + 1, j + 1] = R[i + 1, j + 2] + 1
            D[i + 1, j + 1] = D[i + 2, j + 1] + 1
ans = np.amax(L + R + D + U) - 3
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    table1 = [[0]*W for _ in range(H)]
    for h in range(H):
        for i, c in enumerate(S[h]):
            if c == "#":
                table1[h][i] = 0
            else:
                if i == 0:
                    table1[h][i] = 1
                else:
                    table1[h][i] = table1[h][i-1]+1
    # for h in range(H):
    #     print(table1[h])
    # print()
    for h in range(H):
        buf = 0
        for w in range(W-1, -1, -1):
            if table1[h][w] != 0:
                if buf == 0:
                    buf = table1[h][w]
                table1[h][w] = buf
            else:
                buf = 0
    # for h in range(H):
    #     print(table1[h])
    table2 = [[0]*W for _ in range(H)]
    for w in range(W):
        for h in range(H):
            c = S[h][w]
            if c == "#":
                table2[h][w] = 0
            else:
                if h == 0:
                    table2[h][w] = 1
                else:
                    table2[h][w] = table2[h-1][w]+1
    # for h in range(H):
    #     print(table2[h])
    for w in range(W):
        buf = 0
        for h in range(H-1, -1, -1):
            if table2[h][w] != 0:
                if buf == 0:
                    buf = table2[h][w]
                table2[h][w] = buf
            else:
                buf = 0
    # print()
    # for h in range(H):
        # print(table2[h])

    m = -INF
    for h in range(H):
        for w in range(W):
            buf = table1[h][w] + table2[h][w]
            if buf > m:
                m = buf
                # print(h, w)
    print(m-1)

    return


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()