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

def make(L, R, U, D):
    i = 0
    while i < h:
        j = 0
        while j < w:

#    for i in range(h):
#        for j in range(w):
            if s[i][j] == '#':
                L[i][j] == 0
            elif s[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j-1] + 1

            ri = i
            rj = w-j-1
            if s[ri][rj] == '#':
                R[ri][rj] == 0
            elif s[ri][rj] == '.':
                if rj == w-1:
                    R[ri][rj] = 1
                else:
                    R[ri][rj] = R[ri][rj+1] + 1
        

            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
            
            j += 1
        i += 1

'''
    for j in range(w):
        for i in range(h):
            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
'''


def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

make(L, R, U, D)

ans = 0
#print(L)
#print(R)
#print(U)
#print(D)

i = 0
while i < h:
    j = 0
    while j < w:
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
        j += 1
    i += 1

'''
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:
h, w = map(int, input().split())
s = [list(input()) for _ 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)]

def make(L, R, U, D):
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                L[i][j] == 0
            elif s[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j-1] + 1

            ri = i
            rj = w-j-1
            if s[ri][rj] == '#':
                R[ri][rj] == 0
            elif s[ri][rj] == '.':
                if rj == w-1:
                    R[ri][rj] = 1
                else:
                    R[ri][rj] = R[ri][rj+1] + 1
        

            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
    
'''
    for j in range(w):
        for i in range(h):
            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
'''


def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

make(L, R, U, D)

ans = 0
#print(L)
#print(R)
#print(U)
#print(D)

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:
h, w = map(int, input().split())
s = [list(input()) for _ 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)]

def make(L, R, U, D):
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                L[i][j] == 0
            elif s[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j-1] + 1

            ri = i
            rj = w-j-1
            if s[ri][rj] == '#':
                R[ri][rj] == 0
            elif s[ri][rj] == '.':
                if rj == w-1:
                    R[ri][rj] = 1
                else:
                    R[ri][rj] = R[ri][rj+1] + 1
    

    for j in range(w):
        for i in range(h):
            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1



def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

make(L, R, U, D)

ans = 0
#print(L)
#print(R)
#print(U)
#print(D)

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:
H,W = map(int,input().split())
S = [input() for i in range(H)]

rs = [[0]*W for i in range(H)]
ls = [[0]*W for i in range(H)]
ds = [[0]*W for i in range(H)]
us = [[0]*W for i in range(H)]

for i in range(H):
    tmp = 0
    for j in range(W):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            rs[i][j] = tmp
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            ls[i][j] = tmp

for j in range(W):
    tmp = 0
    for i in range(H):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            ds[i][j] = tmp
    tmp = 0
    for i in reversed(range(H)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            us[i][j] = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        tmp = rs[i][j] + ls[i][j] + ds[i][j] + us[i][j] - 3
        ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

### TESTCASE
test = ""
#test = \
"""
4 6
#..#..
.....#
....#.
#.#...
ans 8
"""

"""
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
ans 13
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN

h, w = map(int, input2().split())
s = [["#"] * (w+1)]
s += [list("#" + input2()) for _ in range(h)]

ws = [[0] * (w+1) for _ in range(h+1)]
hs = [[0] * (w+1) for _ in range(h+1)]

for hi in range(1, h+1):
    for wi in range(1, w+1):
        if s[hi][wi] == ".":
            ws[hi][wi] = ws[hi][wi-1] + 1
            hs[hi][wi] = hs[hi-1][wi] + 1

for hi in range(1, h+1):
    for wi in range(w-1, 0, -1):
        if ws[hi][wi]:
            ws[hi][wi] = max(ws[hi][wi+1], ws[hi][wi])
            
for wi in range(1, w+1):
    for hi in range(h-1, 0, -1):
        if hs[hi][wi]:
            hs[hi][wi] = max(hs[hi+1][wi], hs[hi][wi])           

print(max([ws[hi][wi] + hs[hi][wi] 
for hi in range(1, h+1) 
for wi in range(1, w+1)]) - 1)

Submission status: Time Limit Exceeded

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

import numpy as np

### TESTCASE
test = ""
#test = \
"""
4 6
#..#..
.....#
....#.
#.#...
ans 8
"""

"""
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
ans 13
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN

h, w = map(int, input2().split())
s = [["#"] * (w+1)]
s += [list("#" + input2()) for _ in range(h)]

ws = [[0] * (w+1) for _ in range(h+1)]  # Pythonの恐ろしい仕様！
hs = [[0] * (w+1) for _ in range(h+1)]

for hi in range(1, h+1):
    for wi in range(1, w+1):
        if s[hi][wi] == ".":
            ws[hi][wi] = ws[hi][wi-1] + 1
            hs[hi][wi] = hs[hi-1][wi] + 1

for hi in range(1, h+1):
    for wi in range(w-1, 0, -1):
        if ws[hi][wi]:
            ws[hi][wi] = max(ws[hi][wi+1], ws[hi][wi])
            
for wi in range(1, w+1):
    for hi in range(h-1, 0, -1):
        if hs[hi][wi]:
            hs[hi][wi] = max(hs[hi+1][wi], hs[hi][wi])           
            
ws = np.array(ws)
hs = np.array(hs)

print(np.max(ws + hs) - 1)

Submission status: Time Limit Exceeded

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

def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        else:
            ans = max(ans, right(i, j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {(i,j):[0,0] for i in range(H) for j in range(W)}
for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            cnt = 0
        else:
            C[(i,j)][0] = cnt+1
            cnt += 1
    for i in range(H-2,-1,-1):
        C[(i,j)][0] = max(C[(i,j)][0],C[(i+1,j)][0])
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            cnt = 0
        else:
            C[(i,j)][1] = cnt+1
            cnt += 1
    for j in range(W-2,-1,-1):
        C[(i,j)][1] = max(C[(i,j)][1],C[(i,j+1)][1])
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(C[(i,j)]))
print(cmax-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {(i,j):[0,0] for i in range(H) for j in range(W)}
for j in range(W):
    cnt = 0
    cur = 0
    for i in range(H):
        if S[i][j]=="#":
            for i1 in range(cur,i):
                C[(i1,j)][0] = cnt
            cnt = 0
            cur = i+1
        else:
            cnt += 1
    for i1 in range(cur,H):
        C[(i1,j)][0] = cnt
for i in range(H):
    cnt = 0
    cur = 0
    for j in range(W):
        if S[i][j]=="#":
            for j1 in range(cur,j):
                C[(i,j1)][1] = cnt
            cnt = 0
            cur = j+1
        else:
            cnt += 1
    for j1 in range(cur,W):
        C[(i,j1)][1] = cnt
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(C[(i,j)]))
print(cmax-1)

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int,input().split())
    S = [list(str(input())) for _ in range(N)]
    
    up = [[0 for _ in range(M)] for _ in range(N)]
    down = [[0 for _ in range(M)] for _ in range(N)]
    left = [[0 for _ in range(M)] for _ in range(N)]
    right = [[0 for _ in range(M)] for _ in range(N)]
    
    for i in range(M):
        if S[0][i] == ".":
            up[0][i] = 1
        for j in range(N-1):
            if S[j+1][i] == "#":
                up[j+1][i] = 0
            else:
                up[j+1][i] = up[j][i] + 1

    for i in range(M):
        if S[-1][i] == ".":
            down[-1][i] = 1
        for j in range(N-1):
            if S[-2-j][i] == "#":
                down[-2-j][i] = 0
            else:
                down[-2-j][i] = down[-1-j][i] + 1

    for i in range(N):
        if S[i][0] == ".":
            left[i][0] = 1
        for j in range(M-1):
            if S[i][j+1] == "#":
                left[i][j+1] = 0
            else:
                left[i][j+1] = left[i][j] + 1
    
    for i in range(N):
        if S[i][-1] == ".":
            right[i][-1] = 1
        for j in range(M-1):
            if S[i][-2-j] == "#":
                right[i][-2-j] = 0
            else:
                right[i][-2-j] = right[i][-1-j] + 1
    
    ans = 0
    for i in range(N):
        for j in range(M):
            if S[i][j] == ".":
                num = up[i][j]+down[i][j]+left[i][j]+right[i][j]-3
                ans = max(ans,num)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

maze = []
for _ in range(H):
  maze.append(list(input()))

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 maze[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 maze[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 maze[i][j] == ".":
      if i == H - 1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j] + 1
        
for j in range(W):
  for i in range(H):
    if maze[i][j] == ".":
      if i == 0:
        D[i][j] = 1
      else:
        D[i][j] = D[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:
H, W=map(int, input().split())
S=[input() for _ in range(H)]

tate=[[0]*W for _ in range(H)]
yoko=[[0]*W for _ in range(H)]

for i in range(W):
  j=0
  while j<H:
    x=0
    while j+x<H and S[j+x][i]=='.':
      x+=1
    if x==0:
      tate[j][i]=0
      j+=1
    else:
      for t in range(x):
        tate[j+t][i]=x
      j+=x

for i in range(H):
  j=0
  while j<W:
    x=0
    while j+x<W and S[i][j+x]=='.':
      x+=1
    if x==0:
      yoko[i][j]=0
      j+=1
    else:
      for t in range(x):
        yoko[i][j+t]=x
      j+=x
      
print(max([max([tate[i][j]+yoko[i][j]-1 for j in range(W)]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
GRID = [input() for _ in range(h)]

HORIZONTAL = [[0] * w for _ in range(h)]
for i in range(h):
    COUNTS = []
    count = 0
    for j in range(w):
        if GRID[i][j] == ".":
            count += 1
        else:
            COUNTS.append(count)
            count = 0
    COUNTS.append(count)
    k = 0
    for j in range(w):
        if GRID[i][j] == ".":
            HORIZONTAL[i][j] = COUNTS[k]
        else:
            k += 1

VERTICAL = [[0] * w for _ in range(h)]
for j in range(w):
    COUNTS = []
    count = 0
    for i in range(h):
        if GRID[i][j] == ".":
            count += 1
        else:
            COUNTS.append(count)
            count = 0
    COUNTS.append(count)
    k = 0
    for i in range(h):
        if GRID[i][j] == ".":
            VERTICAL[i][j] = COUNTS[k]
        else:
            k += 1

LIGHTED = []
for i in range(h):
    for j in range(w):
        LIGHTED.append(HORIZONTAL[i][j] + VERTICAL[i][j] - 1)

ans = max(LIGHTED)
print(ans)

Submission status: Time Limit Exceeded

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

light = [[[0, 0, 0, 0] for _ in range(W + 1)] for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = light[h][w]
            light[h + 1][w][1] = here[1] + 1
            light[h][w + 1][3] = here[3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = light[h][w]
            light[h - 1][w][0] = here[0] + 1
            light[h][w - 1][2] = here[2] + 1
            ans = max(ans, sum(here) + 1)

print(ans)

Submission status: Time Limit Exceeded

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

light = [[[0, 0, 0, 0] for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = light[h][w]
            if h + 1 < H and grid[h + 1][w] == '.':
                light[h + 1][w][1] = here[1] + 1
            if w + 1 < W and grid[h][w + 1] == '.':
                light[h][w + 1][3] = here[3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = light[h][w]
            if h - 1 >= 0 and grid[h - 1][w] == '.':
                light[h - 1][w][0] = here[0] + 1
            if w - 1 >= 0 and grid[h][w - 1] == '.':
                light[h][w - 1][2] = here[2] + 1
            ans = max(ans, sum(here) + 1)

print(ans)

Submission status: Time Limit Exceeded

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

light = [[[0, 0, 0, 0] for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = light[h][w]
            if h + 1 < H and grid[h + 1][w] == '.':
                light[h + 1][w][1] = here[1] + 1
            if w + 1 < W and grid[h][w + 1] == '.':
                light[h][w + 1][3] = here[3] + 1

for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = light[h][w]
            if h - 1 >= 0 and grid[h - 1][w] == '.':
                light[h - 1][w][0] = here[0] + 1
            if w - 1 >= 0 and grid[h][w - 1] == '.':
                light[h][w - 1][2] = here[2] + 1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, sum(light[h][w]) + 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
g = [input() for i in range(H)]
 
c = [[0 for w in range(W)] for h in range(H)]
 
hs = [0 for i in range(W)]
 
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
 
#print(c)
 
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])
 
print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
 
縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''

Submission status: Time Limit Exceeded

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

c = [[0 for w in range(W)] for h in range(H)]

hs = [0 for i in range(W)]

for h in range(H):
    ws = 0

    for w in range(W):
        if g[h][w] == '#':

            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1

            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1

    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
grid = [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 w in range(W):
    for h in range(H):
        if grid[h][w] == '#':
            L[h][w] = 0
        elif w == 0:
            L[h][w] = 1
        else:
            L[h][w] = L[h][w-1] + 1

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

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

for w in range(W):
    for h in range(H-1,-1,-1):
        if grid[h][w] == '#':
            D[h][w] = 0
        elif h == H-1:
            D[h][w] = 1
        else:
            D[h][w] = D[h+1][w] + 1
ans = 0
for w in range(W):
    for h in range(H):
        lighted = D[h][w] + U[h][w] + L[h][w] + R[h][w] - 3
        ans = max(ans,lighted)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
# dir: 0 -> start
# dir: 1 -> right
# dir: 2 -> down
# dir: 3 -> left
# dir: 4 -> up
import sys
sys.setrecursionlimit(10**9)
grid = [list(input()) for _ in range(H)]


def dfs(grid,y,x,dir):
    global num_l
    if not (0 <= x < W and 0 <= y < H):
        return
    if grid[y][x] == '#':
        return
    num_l += 1
    if dir == 0:
        dfs(grid, y, x+1, 1)
        dfs(grid, y+1, x, 2)
        dfs(grid, y, x-1, 3)
        dfs(grid, y-1, x, 4)
    elif dir == 1:
        dfs(grid, y, x + 1, 1)
    elif dir == 2:
        dfs(grid, y+1, x, 2)
    elif dir == 3:
        dfs(grid, y, x-1, 3)
    elif dir == 4:
        dfs(grid, y-1, x, 4)

ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            num_l = 0
            dfs(grid, h, w, 0)
            ans = max(ans,num_l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline #for input speed

H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
import sys
input = sys.stdin.readline
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    d2.append(sc(s))

for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    d3.append(sc(s))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
def sc(s):
    b = None
    nc = 0
    kk = []
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                ei = i
                kk.append((si, ei))
        b = c
    return kk
d = []
d2 = [[0] * W for _ in range(H)]
d3 = [[0] * W for _ in range(H)]
for h in range(H):
    s = input().strip() + "#"
    d.append(s)
    r = sc(s)
    for ss, tt in r:
        for i in range(ss, tt):
            d2[h][i] = tt - ss
for i in range(W):
    s = ""
    for j in range(H):
        s += d[j][i]
    s += "#"
    r = sc(s)
    for ss, tt in r:
        for k in range(ss, tt):
            d3[k][i] = tt - ss
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[i][j]-1)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if s[i][j]=='#':
        continue

      _ans=0
      for a in range(i)[::-1]:
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(i+1,h):
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(j)[::-1]:
        if s[i][a]=='.':
          _ans+=1
        else:
          break
      for a in range(j,w):
        if s[i][a]=='.':
          _ans+=1
        else:
          break

      ans=max(ans,_ans)
  return ans

# main()
print(main())