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())
h+=2
w+=2
s=[]
l=[[0 for i in range(w)]for j in range(h)]
yl=[[]for j in range(h)]
tl=[[]for j in range(w)]
s.append(["#"]*w)
for i in range(h-2):
    a=input()
    s.append("#"+a+"#")
s.append(["#"]*w)

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            yl[i].append(j)
            tl[j].append(i)
ans=0
import bisect
for i in range(1,h-1):
    for j in range(1,w-1):
        if s[i][j]!="#":
            n=bisect.bisect(yl[i],j)
            m=bisect.bisect(tl[j],i)
            p=0
            p+=yl[i][n]-yl[i][n-1]+tl[j][m]-tl[j][m-1]-3
            
            ans=max(ans,p)
                
        
print(ans)

Submission status: Time Limit Exceeded

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

total = 0

# h, w, [yoko, tate]
table = []
for h in range(H):
    table.append([])
    for w in range(W):
        table[h].append([0, 0])

# 横を数える
for h in range(H):
    # 行き
    for w in range(W):
        if S[h][w] == "#":
            continue

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

    # # 帰り
    # for w in reversed(range(W)):
    #     if S[h][w] == "#":
    #         continue

    #     if w == W-1:
    #         pass
    #     else:
    #         table[h][w][0] = max(table[h][w][0], table[h][w+1][0])


# 縦を数える
for w in range(W):
    # 行き
    for h in range(H):
        if S[h][w] == "#":
            continue

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

    # # 帰り
    # for h in reversed(range(H)):
    #     if S[h][w] == "#":
    #         continue

    #     if h == H-1:
    #         pass
    #     else:
    #         table[h][w][1] = max(table[h][w][1], table[h+1][w][1])
    #     total = max(total, sum(table[h][w]) - 1)

for h in reversed(range(H)):
    for w in reversed(range(W)):
        if S[h][w] == "#":
            continue

        total = max(total, sum(table[h][w]) - 1)
        if w != 0 and S[h][w-1] == ".":
            table[h][w-1][0] = table[h][w][0]

        if h != 0 and S[h-1][w] == ".":
            table[h-1][w][1] = table[h][w][1]

print(total)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = []
for i in range(H):
    s = input()
    S.append([x for x in s])
 
S_t = list(map(list, zip(*S)))
 
S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]
S_hh = [[0]*(W+1) for i in range(H)]
S_ww = [[0]*(H+1) for i in range(W)]
 
for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)
            S_hh[y][x] = 1
            S_ww[x][y] = 1
        S_hh[y][x] += S_hh[y][x-1]
        S_ww[x][y] += S_ww[x][y-1]
 
ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = S_ww[x][y]
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = S_hh[y][x]
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)
 
print(ans)

Submission status: Time Limit Exceeded

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

yoko = []
for h in range(H):
  yoko.extend(S[h].split("#"))

ans = 0
for hw in zip(*S):
  hw = "".join(hw)
  t = len(max(hw.split("#")))
  ans = max(len(max(yoko))+t-1, ans)

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)]
xt = [[x[i][j] for i in range(h)] for j in range(w)]
xh = np.zeros([w, h], dtype=np.int)
for i, xi in enumerate(x):
    l = 0
    for j, xij in enumerate(xi):
        if xij == '#':
            xh[l:j, i] = j - l
            l = j + 1
    xh[l:, i] = w - l

ans = 0
for i, xi in enumerate(xt):
    l = 0
    for j, xij in enumerate(xi):
        if xij == '#':
            if j > l:
                ans = max(ans, max(xh[i, l:j]) + j - l - 1)
            l = j + 1
    if h > l:
        ans = max(ans, max(xh[i, l:]) + h - l - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

H, W = map(int, input().split())

VT, HT = [0]*H, [0]*H
for i in range(H):
    line = input().strip()
    VT[i] = list(line)
    HT[i] = list(line+'#')
VT = list(map(list, zip(*VT)))
for i in range(W):
    VT[i] += ['#']

ans = 0
for row in range(H):
    for col in range(W):
        if HT[row][col] == '#':
            continue
        if HT[row][col] == '.':
            cpos = HT[row].index('#', col)
            # while cpos < W and HT[row][cpos] != '#':
            #    cpos += 1
            for c in range(col, cpos):
                HT[row][c] = cpos-col
        if VT[col][row] == '.':
            rpos = VT[col].index('#', row)
            for r in range(row, rpos):
                VT[col][r] = rpos-row

        ans = max(ans, VT[col][row] + HT[row][col] - 1)

# print(HT)
# print(VT)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [list(map(str,input().split("#"))) for i in range(h)]
li = []
for i in range(h):
  s = [0 for i in range(w)]
  cou = 0
  for j in lis[i]:
    e = len(j)
    for n in range(len(j)):
      s[cou] = e
      cou += 1
    cou += 1
  li.append(s)
l = []
for i in range(w):
  s = [0 for i in range(h)]
  cou = 0
  nu = 0
  for j in range(h):
    if li[j][i] != 0:
      cou += 1
    else:
      cou = 0
    s[nu] = cou
    nu += 1
  for g in range(h-1):
    if s[-(2+g)] != 0 and s[-(2+g)] < s[-(1+g)]:
      s[-(2+g)] = s[-(1+g)]
  l.append(s)
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,li[i][j] + l[j][i]-1)
print(ans)

Submission status: Time Limit Exceeded

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

yoko = []
for h in range(H):
  yoko.extend(S[h].split("#"))

ans = 0
for hw in zip(*S):
  hw = "".join(hw)
  t = len(max(hw.split("#")))
  for y in yoko:
    ans = max(len(y)+t-1, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map( int, input().split())
P = [ input() for _ in range(H)]
T = [ [1]*W for _ in range(H)]
Y = [ [1]*W for _ in range(H) ]
S = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if P[i][j] == "#":
           S[i][j]  = 1
for i in range(H):
    now = 0
    cnt = 0
    for j in range(W):
        if S[i][j] == 0:
            cnt += 1
        else:
            for k in range(now, j):
                T[i][k] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, W):
                T[i][k] = cnt
            
for i in range(W):
    now = 0
    cnt = 0
    for j in range(H):
        if S[j][i] == 0:
            cnt += 1
        else:
            for k in range(now, j):
                Y[k][i] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, H):
                Y[k][i] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if ans < T[i][j] + Y[i][j]-1:
            ans = T[i][j] + Y[i][j]-1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

val = list(map(int, input().strip().split()))
width = val[1]
height = val[0]

walls = np.zeros((height, width))

for y in range(height):
    val = input().strip()
    for x in range(width):
        walls[y, x] = 1 if val[x] == '#' else 0

# left = np.zeros((height, width))
# right = np.zeros((height, width))
# up = np.zeros((height, width))
# down = np.zeros((height, width))
all = np.zeros((height, width))

# left
for y in range(height):
    cache = 0
    for x in range(width):
        if walls[y, x] == 1:
            cache = x + 1
            all[y, x] = 1000000
        else:
            all[y, x] += cache

# right
for y in range(height):
    cache = 0
    for x in range(width - 1, -1, -1):
        if walls[y, x] == 1:
            cache = width - x
        else:
            all[y, x] += cache

# up
for x in range(width):
    cache = 0
    for y in range(height):
        if walls[y, x] == 1:
            cache = y + 1
        else:
            all[y, x] += cache

# down
for x in range(width):
    cache = 0
    for y in range(height - 1, -1, -1):
        if walls[y, x] == 1:
            cache = height - y
        else:
            all[y, x] += cache


print(int(width + height - np.amin(all) - 1))

Submission status: Time Limit Exceeded

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

def f(H, W, S):
    hs = []
    vs = []
    sts = [0]*W

    for j, s in enumerate(S):
        st = 0
        
        for i, c in enumerate(s):
            if c == '#':
                if st < i:
                    hs.append((j, st, i))
                st = i+1

                if sts[i] < j:
                    vs.append((j-sts[i], i, sts[i], j))

                sts[i] = j+1

        if st < W:
            hs.append((j, st, W))
            
    for i in range(W):
        if sts[i] < H:
            vs.append((H-sts[i], i, sts[i], H))
	 
    vs = sorted(vs, reverse=True)
    m = 0

    for h in hs:
        sz1 = h[2] - h[1]

        for v in vs:
            sz2 = v[3] - v[2]
            if sz1 + sz2 - 1 <= m:
                break

            if h[0] >= v[2] and h[0] < v[3] and \
               v[1] >= h[1] and v[1] < h[2]:
    
                m = sz1 + sz2 - 1

    return m


def main():
    H,W = map(int, input().split())
    S = list(input() for i in range(H))
    print(f(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[] for i in range(H)]
B =[[] for i in range(W)]
for i in range(H):
    k = 0
    a = 0
    while k < W:
        if List[i][k]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                A[i].append(a)
            A[i].append(0)
            a = 0
            k = k+1
    for j in range(a):
                A[i].append(a)
for i in range(W):
    k = 0
    a = 0
    while k < H:
        if List[k][i]==".":
            a += 1
            k = k+1
        else:
            for j in range(a):
                B[i].append(a)
            B[i].append(0)
            a = 0
            k = k+1
    for j in range(a):
                B[i].append(a)
max = 0
for i in range(H):
    for j in range(W):
        if max < A[i][j] + B[j][i]:
            max = A[i][j] + B[j][i]
print(max-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
state = []
for i in range(H):
    row_list = list(input())
    state.append(row_list)


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 h in range(H):
        for w in range(W):
            if state[h][w] == '.':
                blank_list.append([h, w])
    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 search(s_y, s_x):
    count = 1
    for vec_x, vec_y in vecs:
        n_y = s_y + vec_y
        n_x = s_x + vec_x

        while judge(n_y, n_x):
            #is_visited[n_y][n_x] = True
            count += 1
            n_y += vec_y
            n_x += vec_x
    return count

def judge(y, x):
    return 0 <= y <= H -1 and 0 <= x <= W - 1 and not is_visited[y][x] and S_list[y][x] != '#'

H, W = map(int, input().split())
S_list = [None] * H
is_visited = [[False] * W for _ in range(H)]

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

vecs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

max_num = 0
for h in range(H):
    for w in range(W):
        if S_list[h][w] != '#':
            max_num = max(max_num, search(h, w))

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
S=[""]*H
A=np.zeros((H,W))
for i in range(H):
    S[i]=input()
for i in range(H):
    j=0
    j_from=0
    while j<W:
        if S[i][j]=="#":
            for k in range(j_from,j):
                A[i][k]=j-j_from
            A[i][j]=0
            j+=1
            j_from=j
        else:
            j+=1
    for k in range(j_from,j):
                A[i][k]=j-j_from
B=np.zeros((H,W))
for j in range(W):
    i=0
    i_from=0
    while i<H:
        if S[i][j]=="#":
            for k in range(i_from,i):
                B[k][j]=i-i_from
            B[i][j]=0
            i+=1
            i_from=i
        else:
            i+=1
    for k in range(i_from,i):
                B[k][j]=i-i_from
print(int(np.max(A+B-1)))

Submission status: Time Limit Exceeded

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

area = []

for _ in range(H):
    area.append(input())
    
def area_search(x, y):
    count = 0
    # up
    for place in range(y-1, -1, -1):
        if area[place][x] == ".":
            count += 1
        else:
            break
    
    # left
    for place in range(x-1, -1, -1):
        if area[y][place] == ".":
            count += 1
        else:
            break
            
    # down
    for place in range(y + 1, H, 1):
        if area[place][x] == ".":
            count += 1
        else:
            break
            
    # right
    for place in range(x + 1, W, 1):
        if area[y][place] == ".":
            count += 1
        else:
            break
            
    # place
    count += 1
    
    return count
  
candidate = []
for i in range(H):
    for j in range(W):
        if area[i][j] == '.':
            candidate.append(area_search(j, i))
print(max(candidate))

Submission status: Time Limit Exceeded

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

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

# def ok(i,j,houkou, count):
#     if i==h or j==w:
#         return count
#     elif s[i][j]=='#':
#         return count
#     elif houkou=='yoko':
#         return ok(i,j+1,houkou,count+1)
#     else:
#         return ok(i+1,j,houkou,count+1)

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

count=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#' or j+1==w:
            for k in range(count):
                yoko[i][j-k-1]=count
            count=0

# print(yoko)


for j in range(w):
    for i in range(h):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#' or i+1==h:
            for k in range(count):
                tate[i-k-1][j]=count
            count=0

# print(tate)

ans=0
for i in range(h):
    for j in range(w):
        if ans<yoko[i][j]+tate[i][j]-1:
            ans=yoko[i][j]+tate[i][j]-1
print(ans)

Submission status: Time Limit Exceeded

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

s = np.zeros((h, w))
for i in range(h):
    for j, c in enumerate(list(str(input()))):
        if c == ".":
            s[i][j] = 1

board_w = np.zeros((h, w))
board_h = np.zeros((w, h))

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == 1:
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == w - 1:
            for k in range(cnt_continue):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0

s = s.transpose()

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == 1:
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == h - 1:
            for k in range(cnt_continue):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0

board_h = board_h.transpose()
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j] + board_h[i][j])
        ans = max(ans, v)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for i in range(h)]
c=[[[0,0] for i in range(w)] for i in range(h)]
t=0
for H in range(h):
    for W in range(w):
        if(s[H][W]=="#"):
            for l in range(1,t+1):
                c[H][W-l][0]=t
            t=0
        else:
            t+=1
    for l in range(1,t+1):
        c[H][-l][0]=t
    t=0    
for W in range(w):
    for H in range(h):
        if(s[H][W]=="#"):
            for l in range(1,t+1):
                c[H-l][W][1]=t
            t=0
        else:
            t+=1
    for l in range(1,t+1):
        c[-l][W][1]=t
    t=0
ans=0
for i in c:
    for j in i:
        ans=max(sum(j),ans)
print(max(ans-1,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)


def search_y(i, j, matrix):
    """i, j について，y方向を埋める
    """
    to_plus = 0
    to_minus = 0
    while(True):
        to_plus += 1
        if (matrix[i + to_plus][j][0] == 0):
            continue
        else:
            to_plus -= 1
            break
    while(True):
        to_minus += 1
        if (matrix[i - to_minus][j][0] == 0):
            continue
        else:
            to_minus -= 1
            break
    sum_ = to_plus + to_minus + 1
    for i2 in range(0, to_plus + 1):
        matrix[i + i2][j][0] = sum_
    for i2 in range(0, to_minus + 1):
        matrix[i - i2][j][0] = sum_
    return matrix

def search_x(i, j, matrix):
    """i, j について，y方向を埋める
    """
    to_plus = 0
    to_minus = 0
    while(True):
        to_plus += 1
        if (matrix[i][j + to_plus][1] == 0):
            continue
        else:
            to_plus -= 1
            break
    while(True):
        to_minus += 1
        if (matrix[i][j - to_minus][1] == 0):
            continue
        else:
            to_minus -= 1
            break
    sum_ = to_plus + to_minus + 1
    for i2 in range(0, to_plus + 1):
        matrix[i][j + i2][1] = sum_
    for i2 in range(0, to_minus + 1):
        matrix[i][j - i2][1] = sum_
    return matrix

def main():
    H, W = map(int, input().split())
    matrix = []
    for i in range(0, H + 2):
        lines = []
        for j in range(0, W + 2):
            lines.append([-1, -1])
        matrix.append(lines)

    for i in range(1, H + 1):
        string = input()
        for j in range(1, W + 1):
            if string[j - 1] == "#":
                continue
            else:
                matrix[i][j] = [0, 0]
                
    max_sum = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if (matrix[i][j][0] == 0):
                # y方向を埋める
                matrix = search_y(i, j, matrix)
            if (matrix[i][j][1] == 0):
                # x方向を埋める
                matrix = search_x(i, j, matrix)
            max_sum = max(matrix[i][j][0] + matrix[i][j][1], max_sum)
    
    # for i in range(1, H + 1):
    #     for j in range(1, W + 1):
    #         # max_sum = max(matrix[i][j][0] + matrix[i][j][1], max_sum)
    print(max_sum - 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

yoko = np.zeros((H+2, W+2))
tate = np.zeros((H+2, W+2))
sumoflump = np.zeros((H, W))
ans = 0
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            yoko[i + 1][j + 1] = -1
            tate[i+1][j+1] = -1

for k in range(H + 2):
    yoko[k][0] = -1

    yoko[k][W + 1] = -1

    left = 0
    for m in range(W+2):
        if yoko[k][m] == -1:
            for p in range(left+1, m):
                yoko[k][p] = m - left - 1
            left = m

for q in range(W + 2):
    up = 0
    tate[0][q] = -1
    tate[H+1][q] = -1
    for r in range(H+2):
        if tate[r][q] == -1:
            for x in range(up+1, r):
                tate[x][q] = r - up - 1
            up = r
for y in range(H):
    for z in range(W):
        sumoflump[y][z] = yoko[y + 1][z + 1] + tate[y + 1][z + 1]-1
maxlist_1 = np.sort(sumoflump, axis=1)
maxlist_2 = np.sort(maxlist_1, axis=0)
ans = maxlist_2[0][0]

print("{}".format(int(maxlist_2[H-1][W-1])))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [list(map(str,input().split("#"))) for i in range(h)]
li = []
for i in range(h):
  s = [0 for i in range(w)]
  cou = 0
  for j in lis[i]:
    e = len(j)
    for n in range(len(j)):
      s[cou] = e
      cou += 1
    cou += 1
  li.append(s)
l = []
for i in range(w):
  s = []
  cou = 0
  for j in range(h):
    if li[j][i] != 0:
      cou += 1
    else:
      cou = 0
    s.append(cou)
  for g in range(h-1):
    if s[-(2+g)] != 0 and s[-(2+g)] < s[-(1+g)]:
      s[-(2+g)] = s[-(1+g)]
  l.append(s)
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,li[i][j] + l[j][i]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    row = S[h]
    for w in range(W):
        if w > 0 and row[w-1] != '#':
            count_matw[h][w] = count_matw[h][w-1]
            continue
        if '#' in row[w:]:
            obs_i = row[w:].index('#')
            count_matw[h][w] = obs_i
        else:
            count_matw[h][w] = W-w
for w in range(W):
    col = [row[w] for row in S]
    for h in range(H):
        if h > 0 and col[h-1] != '#':
            count_math[h][w] = count_math[h-1][w]
            continue
        if '#' in col[h:]:
            obs_i = col[h:].index('#')
            count_math[h][w] = obs_i
        else:
            count_math[h][w] = H-h
ans = 1
for h in range(H):
    for w in range(W):
        ans = max(ans, count_math[h][w] + count_matw[h][w])
print(ans-1)

Submission status: Time Limit Exceeded

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

S = [input() for i in range(H)]
ans = [[0 for i in range(W)]for j in range(H)]

for i in range(H):
    c = 0
    s = 0
    for j in range(W):
        if S[i][j] =='#':
            for k in range(s,j):
                ans[i][k] += c

            c = 0
            s = j + 1
        else:
            c += 1
    for k in range(s,j+1):
        ans[i][k] += c

for i in range(W):
    c = 0
    s = 0
    for j in range(H):
        if S[j][i] =='#':
            for k in range(s,j):
                ans[k][i] += c-1

            c = 0
            s = j + 1
        else:
            c += 1
    for k in range(s,j+1):
        ans[k][i] += c-1

print(max([max(ans_) for ans_ in ans]))

Submission status: Time Limit Exceeded

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

s=[input() for i in range(h)]
s=[[0 if x == "#" else 1 for x in x] for x in s]

max_s = 0
for y in range(h):
    for x in range(w):
        if s[y][x] == 0:
            continue
        above = 0
        left = 0
        right = 0
        bottom = 0
        for i in reversed(range(0,y)):
            if s[i][x] == 0:
                break
            else:
                above += 1
        for i in range(y, h):
            if s[i][x] == 0:
                break
            else:
                bottom += 1
        for i in reversed(range(0,x)):
            if s[y][i] == 0:
                break
            else:
                left += 1
        for i in range(x, w):
            if s[y][i] == 0:
                break
            else:
                right += 1
        current_sum = above + left + right + bottom -1
        if current_sum > max_s:
            max_s = current_sum
print(max_s)

Submission status: Time Limit Exceeded

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

# 横
A = np.array([[-10000] * W for i in range(H)])
B = np.array([[-10000] * W for i in range(H)])

S = np.array(S)
for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i, j] == '#':
            A[i, jj:j] = s
            s = 0
            jj = j + 1
        else:
            s += 1

S2 = S.T
B2 = B.T
for i in range(W):
    jj = 0
    s = 0
    for j in range(H+1):
        if j == H or S2[i, j] == '#':
            B2[i, jj:j] = s
            s = 0
            jj = j + 1
        else:
            s += 1

B = B2.T
X = A + B - 1
print(np.max(X))

Submission status: Time Limit Exceeded

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

MH = [[0] * W for _ in range(H)]
MW = [[0] * W for _ in range(H)]

ans = 0
for h in range(H):
  for w in range(W):
    if ('#' != S[h][w]):
      if ((0 < h) & ('#' != S[h-1][w])):
        mh = MH[h-1][w]
      else:
        mh = 0
        for h2 in range(h,H):
          if ('#' == S[h2][w]):
            break
          mh += 1
      MH[h][w] = mh
      if ((0 < w) & ('#' != S[h][w-1])):
        mw = MW[h][w-1]
      else:
        mw = 0
        for w2 in range(w,W):
          if ('#' == S[h][w2]):
            break
          mw += 1
      MW[h][w] = mw
      a = (mh + mw) - 1
      if (ans < a):
        ans = a
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

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

    dp_h = [[0 for _ in range(W)] for _ in range(H)]
    dp_w = [[0 for _ in range(W)] for _ in range(H)]

    n = 0
    for i in range(H):
        for j in range(W):
            cnt_x = 0
            for x in range(H):
                if S[x][j] == ".":
                    cnt_x += 1
                else:
                    if x > i:
                        break
                    else:
                        cnt_x = 0

            cnt_y = 0
            for y in range(W):
                if S[i][y]  == ".":
                    cnt_y += 1
                else:
                    if y > j:
                        break
                    else:
                        cnt_y = 0
            n = max(n, cnt_x + cnt_y)
    print(n-1)

main()

Submission status: Time Limit Exceeded

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

yoko = []
for h in range(H):
  for k in S[h].split("#"):
    yoko.append(len(k))

ans = 0
for hw in zip(*S):
  hw = "".join(hw)
  t = len(max(hw.split("#")))
  for y in yoko:
    ans = max(y+t-1, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

h, w = map(int, input().split())
s = [input() for _ in range(h)]
a = [[-1] * w for _ in range(h)]
for i in range(h):
    p = 0
    while p < w:
        j = p
        while j < w and s[i][j] == '.':
            j += 1
        for k in range(p, j):
            a[i][k] += j - p
        p = j + 1

for j in range(w):
    p = 0
    while p < h:
        i = p
        while i < h and s[i][j] == '.':
            i += 1
        for k in range(p, i):
            a[k][j] += i - p
        p = i + 1

print(max(chain.from_iterable(a)))