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())
sl=[input() for i in range(h)]
ll=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(j,-1,-1):
                if sl[i][k]=='.':
                    ll[i][j]+=1
                else:
                    break
rl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(j,w):
                if sl[i][k]=='.':
                    rl[i][j]+=1
                else:
                    break
ul=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(i,-1,-1):
                if sl[k][j]=='.':
                    ul[i][j]+=1
                else:
                    break
dl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            for k in range(i,h):
                if sl[k][j]=='.':
                    dl[i][j]+=1
                else:
                    break
ans=0
for i in range(h):
    for j in range(w):
            ans=max(ans,ll[i][j]+rl[i][j]+ul[i][j]+dl[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = [int(x) for x in input().split()]
S = ['#'*(W+2)]+['#'+input()+'#' for _ in range(H)]+['#'*(W+2)]
#%%
di_w = {}
di_h = {}
cnt_w = 0
cnt_h = 0
ans = 0
li = [[[-1 for _ in range(2)] for _ in range(W+2)]for _ in range(H+2)]

for h,s in enumerate(S):
    for w,c in enumerate(s):
        if(c=='#'):
            cnt_w += 1
            cnt_h += 1
        else:
            if(li[h-1][w][0]==-1):
                li[h][w][0] = cnt_h
                di_h[cnt_h] = 1
            else:
                li[h][w][0] = li[h-1][w][0]
                di_h[li[h][w][0]] += 1

            if(li[h][w-1][1]==-1):
                li[h][w][1] = cnt_w
                di_w[cnt_w] = 1
            else:
                li[h][w][1] = li[h][w-1][1]
                di_w[li[h][w][1]] += 1
        cnt_h+=1

for h,s in enumerate(S):
    for w,c in enumerate(s):
        if(c=='#'):
            pass
        else:
            ans = max(ans,di_h[li[h][w][0]]+di_w[li[h][w][1]]-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
L = [[0 for j in range(w + 2)] for i in range(h + 2)]
U = [[0 for j in range(w + 2)] for i in range(h + 2)]
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 = [[0 for j in range(w + 2)] for i in range(h + 2)]
D = [[0 for j in range(w + 2)] for i in range(h + 2)]
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 = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        ans = max(ans, L[i][j] + D[i][j] + R[i][j] + U[i][j] - 3)
print(ans)

Submission status: Time Limit Exceeded

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

M = []
for i in range(H):
  M.append([c == '.' for c in list(input().strip())])

max_size = 0
max_pos = None
for i in range(H):
  for j in range(W):
    if not M[i][j]:
      continue

    a = 1
    for x in range(j + 1, W):
      if not M[i][x]: break
      a += 1
    for x in range(j - 1, -1, -1):
      if not M[i][x]: break
      a += 1
    for y in range(i + 1, H):
      if not M[y][j]: break
      a += 1
    for y in range(i - 1, -1, -1):
      if not M[y][j]: break
      a += 1

    if a > max_size:
      max_size = a
      max_pos = (i, j)

print(max_size)
#print(max_size, max_pos)

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)]
ans = 0
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
            Grid1[i][j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            Grid1[i][x] = cou
ws = [0]*H
    
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):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)

Submission status: Time Limit Exceeded

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

light = [[None for i in range(W)] for j in range(H)]

for i in range(H):
    j = 0
    count = 0
    before = 0
    while j <= W-1:
        if grid[i][j] == ".":
            count += 1
        else:
            for k in range(before, j):
                light[i][k] = count
            light[i][j] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light[i][k] = count

light2 = [[None for i in range(W)] for j in range(H)]

for i in range(W):
    j = 0
    count = 0
    before = 0
    while j <= H-1:
        if grid[j][i] == ".":
            count += 1
        else:
            for k in range(before, j):
                light2[k][i] = count
            light2[j][i] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light2[k][i] = count

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

Submission status: Time Limit Exceeded

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

yoko = {}
tate = {}
tate_counter = [0 for i in range(W)]
for h in range(H):
    yoko_counter = 0
    for w in range(W):
        if S[h][w] == '#':
            for i in range(yoko_counter):
                yoko[(h, w - i - 1)] = yoko_counter
            for i in range(tate_counter[w]):
                tate[(h - i - 1, w)] = tate_counter[w]
            yoko_counter = 0
            tate_counter[w] = 0
            continue
        yoko_counter += 1
        tate_counter[w] += 1
    if yoko_counter > 0:
        for i in range(yoko_counter):
            yoko[(h, W - i - 1)] = yoko_counter
for w in range(W):
    if tate_counter[w] > 0:
        for i in range(tate_counter[w]):        
            tate[(H - i - 1, w)] = tate_counter[w]


max_score = 0
for h in range(H):
    for w in range(W):
        if (h,w) in yoko and (h,w) in tate:
            score = yoko[(h,w)] + tate[(h,w)] - 1
            if max_score < score:
                #print(h,w, score)
                max_score = score

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
yoko_map=[[0 for i in range(w)] for j in range(h)]
tate_map=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    p=0
    s_=s[i]
    s_=s_.split('#')
    for x in s_:
        num=len(x)
        for j in range(num):
            yoko_map[i][p]=num
            p+=1
        p+=1
for i in range(w):
    p=0
    s_=''.join([s__[i] for s__ in s])
    s_=s_.split('#')
    for x in s_:
        num=len(x)
        for j in range(num):
            tate_map[p][i]=num
            p+=1
        p+=1
m=0
for i in range(h):
    yoko_=yoko_map[i]
    tate_=tate_map[i]
    for j in range(w):
        m=max(m,tate_[j]+yoko_[j])
print(max(0,m-1))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
sList = [list(input()) for i in range(h)]
vNum = 0
hNumList = [0] * w
preSharpX = -1
preSharpYList = [-1] * w
sharpXList = [[] for _ in range(h)]
sharpYList = [[] for _ in range(w)]
nextSharpX = w
nextSharpYList = [[] for _ in range(w)]
answer = 0
for y in range(h):
  for x in range(w):
    if sList[y][x] == "#":
      sharpXList[y].append(x)
      sharpYList[x].append(y)
  sharpXList[y].append(w)
    
for x in range(w):
  sharpYList[x].append(h)
  
for x in range(w):
  nextSharpYList[x] = sharpYList[x].pop(0)
  
for y in range(h):
  preSharpX = -1
  nextSharpX = sharpXList[y].pop(0)
  for x in range(w):
    if  x == nextSharpX: # y == nextSharpYList[x]も同時に成立
      preSharpX = nextSharpX
      nextSharpX = sharpXList[y].pop(0)
      
      preSharpYList[x] = nextSharpYList[x]
      nextSharpYList[x] = sharpYList[x].pop(0)

    else:
      if answer < nextSharpX - preSharpX + nextSharpYList[x] - preSharpYList[x] - 3:
        answer = nextSharpX - preSharpX + nextSharpYList[x] - preSharpYList[x] - 3
        
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

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

a = [[] for i in range(h)]
#al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                #al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            #al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# これ愚直じゃダメなのかな
# 上下左右それぞれのテーブルを用意し、いまいるところより上/下/左/右にいくつあるかをセーブする（自分は含まない）

h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
top_table = [[0 for _ in range(h)] for _ in range(w)]  # 自分より上 あとで転置
bottom_table = [[0 for _ in range(h)] for _ in range(w)]  # 自分より下 あとで転置
left_table = [[0 for _ in range(w)] for _ in range(h)]  # 自分より左
right_table = [[0 for _ in range(w)] for _ in range(h)]  # 自分より右

for y in range(h):
    forward_right = [0 for _ in range(w)]
    forward_left = [0 for _ in range(w)]
    for x in range(w):
        if table[y][x] == "#":
            forward_left[x] = -1  # リセット
            continue
        elif table[y][x] == ".":
            # 番兵とか置いてないので...
            if x == 0:
                forward_left[x] = 0
            else:
                forward_left[x] = forward_left[x - 1] + 1
    for x in range(w - 1, -1, -1):
        if table[y][x] == "#":
            forward_right[x] = -1
            continue
        elif table[y][x] == ".":
            if x == w - 1:
                forward_right[x] = 0
            else:
                forward_right[x] = forward_right[x + 1] + 1

    left_table[y] = list(map(lambda x: 0 if x == -1 else x, forward_left))
    right_table[y] = list(map(lambda x: 0 if x == -1 else x, forward_right))

# print("左右")
# for y in range(h):
#     print(left_table[y], right_table[y])


for x in range(w):
    forward_top = [0 for _ in range(h)]
    forward_bottom = [0 for _ in range(h)]
    for y in range(h):
        if table[y][x] == "#":
            forward_top[y] = -1
            continue
        elif table[y][x] == ".":
            # 毎度おなじみ番兵とか置いてないので
            if y == 0:
                forward_top[y] = 0
            else:
                forward_top[y] = forward_top[y - 1] + 1
    for y in range(h - 1, -1, -1):
        if table[y][x] == "#":
            forward_bottom[y] = -1
            continue
        elif table[y][x] == ".":
            # 毎度おなじみ番兵とか置いてないので
            if y == h-1:
                forward_bottom[y] = 0
            else:
                forward_bottom[y] = forward_bottom[y + 1] + 1
    top_table[x] = list(map(lambda x: 0 if x == -1 else x, forward_top))
    bottom_table[x] = list(map(lambda x: 0 if x == -1 else x, forward_bottom))

# 転置
top_table = list(zip(*top_table))
bottom_table = list(zip(*bottom_table))

# print("上下")
# for y in range(h):
#     print(top_table[y], bottom_table[y])

# 探索
ans = 0
for y in range(h):
    for x in range(w):
        if table[y][x] == ".":
            # 最後に自分自身の場所を加える
            ans = max(ans, top_table[y][x] + bottom_table[y]
                      [x] + left_table[y][x] + right_table[y][x] + 1)

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


ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        else:
            if yo[y][x] != '@' and ta[y][x] != '@':
                T = ta[y][x]
                Y = yo[y][x]
            elif yo[y][x] != '@':
                Y = yo[y][x]
                T = tate(y, x)
            elif ta[y][x] != '@':
                T = ta[y][x]
                Y = yoko(y, x)
            else:
                Y = yoko(y, x)
                T = tate(y, x)
        ans = max(ans, T + Y)
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

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

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)

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_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:
import numpy as np

H, W = map(int, input().split())
s = np.zeros((H, W), np.int32)


def conv(c):
    if c == '#':
        return -1
    else:
        return 0


for i in range(H):
    l = input()
    for j in range(W):
        s[i][j] = conv(l[j])

s1 = np.zeros((H, W), np.int32)
for i in range(H):
    n = 0
    prev = 0
    for j in range(W):
        if s[i][j] == -1:
            if prev != j:
                s1[i][prev:j] = n
            n = 0
            prev = j+1
        else:
            n += 1
    if n != 0:
        if prev != W:
            s1[i][prev:W] = n

s2 = np.zeros((W, H), np.int32)
for i in range(W):
    n = 0
    prev = 0
    for j in range(H):
        if s[j][i] == -1:
            if prev != j:
                s2[i][prev:j] = n
            n = 0
            prev = j+1
        else:
            n += 1
    if n != 0:
        if prev != H:
            s2[i][prev:H] = n

s_sum = s1 + s2.T
ans = np.amax(s_sum) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
hc = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            hc[i][j] = hc[i][j - 1] + 1
for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j < w - 1:
                if hc[i][j] < hc[i][j + 1]:
                    hc[i][j] = hc[i][j + 1]
wc = [[0] * h for i in range(w)]
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            wc[i][j] = wc[i][j - 1] + 1
for i in range(w):
    for j in range(h - 1, -1, -1):
        if s[j][i] == ".":
            if j < h - 1:
                if wc[i][j] < wc[i][j + 1]:
                    wc[i][j] = wc[i][j + 1]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hc[i][j] + wc[j][i] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = []
for i in range(n):
    a = input()
    a.split()
    l.append(a)
def f(x,y):
    global l ,n,m
    ans = -3
    if l[x][y] == "#":
        return 0
    else :
        for i in range(x,n):
            if l[i][y] == ".":
                ans += 1
            else :
                break
        for i in range(x+1):
            if l[x-i][y] == ".":
                ans += 1
            else :
                break
        for i in range(y,m):
            if l[x][i] == ".":
                ans += 1
            else :
                break
        for i in range(y+1):
            if l[x][y-i] == ".":
                ans += 1
            else:
                break
        return ans
k = 1
for i in range(n):
    for j in range(m):
        if k == n + m - 1:
            break
        k = max(k,f(i,j))
print(k)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[[i=="." for i in input()+"#"] for _ in range(H)]+[[False]*(W+1)]

map_=[[0]*W for _ in range(H)]
for i in range(H):
    cnt=0
    q=[]
    for j in range(W+1):
        if S[i][j]==False and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]=cnt
            cnt=0
            q=[]
        elif S[i][j]:
            cnt+=1
            q.append([i,j])
for j in range(W):
    cnt=0
    q=[]
    for i in range(H+1):
        if S[i][j]==False and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]+=cnt
            cnt=0
            q=[]
        elif S[i][j]:
            cnt+=1
            q.append([i,j])
print(max([max(i) for i in map_])-1)

Submission status: Time Limit Exceeded

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

def cal(l):
    ll = l.copy()
    ll.append('#')
    vol = [-100 for j in range(len(ll))]
    i = 0
    while i <= len(ll)-1:
        cnt = 0
        while (ll[i] != '#' and i <= len(ll)-1):
            cnt += 1
            i += 1
            # print(i)

        for j in range(i-cnt,i):
            vol[j] = cnt

        i += 1
        # print(i)
    return vol[:-1]

ver = [] # 縦
hori = [] # 横
fmap = []

for h in range(H):
    # print(h,fmap)
    l = list(input())
    #print(l)
    hori.append(cal(l))
    fmap.append(l)

fmap = np.array(fmap)
fmap = fmap.T.tolist()
#print(fmap)

for w in range(W):
    ver.append(cal(fmap[w]))

ans = 0
#pprint(np.array(hori))
#pprint(np.array(ver).T)
for h in range(H):
    for w in range(W):
        s = hori[h][w]+ver[w][h]
        if s > ans:
            ans = s
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
List=[input() for i in range(H)]
A =[[1]*(W) for i in range(H)]
B =[[1]*(H) 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][k-j-1]=a
            A[i][k]=a
            a = 0
            k = k+1
    for j in range(a):
                A[i][k-j-1]=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][k-j-1]=a
            B[i][k] = 0
            a = 0
            k = k+1
    for j in range(a):
                B[i][k-j-1]= 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:
h, w = map(int, input().split())
S = []
for _ in range(h):
  s = list(input())
  S.append(s)

H = [[0 for _ in range(w)] for _ in range(h)]
W = [[0 for _ in range(w)] for _ in range(h)]
T = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
  cnt = 0
  for j in range(w):
    if S[i][j] == ".":
      cnt += 1
      H[i][j] = cnt
    else:
      cnt = 0
  for j in range(w-2, -1, -1):
    if S[i][j] == "." and S[i][j+1] == ".":
      H[i][j] = H[i][j+1]
for j in range(w):
  cnt = 0
  for i in range(h):
    if S[i][j] == ".":
      cnt += 1
      W[i][j] = cnt
    else:
      cnt = 0
  for i in range(h-2, -1, -1):
    if S[i][j] == "." and S[i+1][j] == ".":
      W[i][j] = W[i+1][j]
m = 0
for i in range(h):
  for j in range(w):
    m = max(H[i][j]+W[i][j]-1, m)
#print(H)
#print(W)
print(m)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[[i for i in input()]for j in range(h)]
l=[[-1] for i in range(h)]
L=[[-1] for i in range(w)]
for i in range(h):
    while s[i].count("#")>0:
        l[i].append(s[i].index("#"))
        s[i][s[i].index("#")]=1
    l[i].append(w)
for i in range(w):
    for j in range(h):
        if s[j][i]==1:
            L[i].append(j)
    L[i].append(h)
        
A=[]
for i in range(h):
    for j in range(w):
        a=0
        if s[i][j]==".":
            for k in range(len(l[i])-1):
                if l[i][k]<=j<=l[i][k+1]:
                    a+=l[i][k+1]-l[i][k]-1
            for m in range(len(L[j])-1):
                if L[j][m]<=i<=L[j][m+1]:
                    a+=L[j][m+1]-L[j][m]-1
            A.append(a-1)
print(max(A))

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)]
#print(S)
ans = 0
ws = [0]*W
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        #print(i,j,S[i][j])
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    Grid1[i] = ws.copy()
ws = [0]*H
    
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):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

def show(s,H):
    for h in range(H):
        print(s[h])

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

s_str = [['.'] * W for i in range(H)]
s = [[1] * W for i in range(H)]
for i in range(H):
    s_str[i] = list(input())

for h in range(H):
    for w in range(W):
        if s_str[h][w] == '#':
            s[h][w] = -1

#show(s,H)

a0 = [[0] * W for i in range(H)]
a1 = [[0] * W for i in range(H)]
a2 = [[0] * W for i in range(H)]
a3 = [[0] * W for i in range(H)]

#0:左
#1:右
#2:上
#3:下


for h in range(H):
    for w in range(W):
        if s[h][w] > 0:

            if w > 0:
                a0[h][w] = a0[h][w-1] + max(0,s[h][w-1])

            if h > 0:
                a2[h][w] = a2[h-1][w] + max(0,s[h-1][w])

        ih = H-1-h
        iw = W-1-w
        if s[ih][iw] > 0:

            if iw < (W - 1):
                a1[ih][iw] = a1[ih][iw+1] + max(0,s[ih][iw+1])

            if ih < (H - 1):
                a3[ih][iw] = a3[ih+1][iw] + max(0,s[ih+1][iw])

            #show(a1,H)


ans = [[-1] * W for i in range(H)]

for h in range(H):
    for w in range(W):
        if s[h][w] > 0:
            ans[h][w] = a0[h][w] + a1[h][w] + a2[h][w] + a3[h][w]
#print('---')
#show(ans,H)
print(np.max(ans) + 1)

Submission status: Time Limit Exceeded

Solution code:
*D, = open(0)
h, w = map(int, D[0].split())
s = [it.rstrip() for it in D[1:]]

import numpy as np
s_row = np.zeros((h,w), dtype=np.int)
for j in range(h):
    isCount = False
#     print(j)
    for i in range(w):
        if s[j][i]=='.':
            if not isCount:
#                 print('start', i)
                start = i
                cnt = 1
                isCount = True
            else:
                cnt += 1
#                 print('cnt', cnt)
        elif s[j][i]=='#':
            if isCount:
                s_row[j, start:i] = cnt
                isCount = False
                
    if isCount:
        s_row[j, start:i+1] = cnt
        isCount = False

s_col = np.zeros((h,w), dtype=np.int)
for i in range(w):
    isCount = False
#     print(j)
    for j in range(h):
        if s[j][i]=='.':
            if not isCount:
#                 print('start', i)
                start = j
                cnt = 1
                isCount = True
            else:
                cnt += 1
#                 print('cnt', cnt)
        elif s[j][i]=='#':
            if isCount:
                s_col[start:j, i] = cnt
                isCount = False
                
    if isCount:
        s_col[start:j+1, i] = cnt
        isCount = False
print(np.sum([s_row, s_col], axis=0).max()-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

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

masu = np.ones(shape=(h, w), dtype=int)
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '#':
            masu[i, j] = -1

kabe = -np.ones(shape=(1, w), dtype=int)
masu = np.vstack([kabe, masu])
masu = np.vstack([masu, kabe])
kabe = -np.ones(shape=(h+2, 1), dtype=int)
masu = np.hstack([kabe, masu])
masu = np.hstack([masu, kabe])

ans = 0
temp = 0
madaikeru = True
hmasu = copy.deepcopy(masu)
for i in range(1, h+1):
    temp = 0
    kokokara = 1
    for j in range(1, w+2):
        if masu[i, j] == 1:
            temp += 1
        else:
            hmasu[i, kokokara:j] = temp
            temp = 0
            kokokara = j+1

wmasu = copy.deepcopy(masu)
for j in range(1, w+1):
    temp = 0
    kokokara = 1
    for i in range(1, h+2):
        if masu[i, j] == 1:
            temp += 1
        else:
            wmasu[kokokara:i, j] = temp
            temp = 0
            kokokara = i+1

maxmasu = hmasu + wmasu
print(maxmasu.max()-1)