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:
import sys
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = [0 for _ in range(H)]
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i] |= 1 << j
    ans = 1
    tate = 0
    yoko = 0
    for i in range(H):
        yoko = 0
        for j in range(W):
            if (S[i] >> j) & 1:
                yoko = 0
                continue
            if yoko == 0:
                for k in range(j+1, W):
                    if (S[i] >> k) & 1:
                        break
                    yoko += 1
            tate = 0
            for k in range(i+1, H):
                if (S[k] >> j) & 1:
                    break
                tate += 1
            for k in range(i-1, -1, -1):
                if (S[k] >> j) & 1:
                    break
                tate += 1
            ans = max(ans, tate + yoko + 1)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np

#debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    H, W = map(int, input().split())
    s_arr = np.zeros(shape=(H, W))
    for h in range(H):
        s_row = input()
        for w in range(W):
            if s_row[w] == ".":
                s_arr[h, w] = 0
            else:
                s_arr[h, w] = 1

    memo = [[(-1, -1) for w in range(W)] for h in range(H)]

    def count_light(arr, pos):
        start = 0
        end = 0
        active = False
        for i, s in enumerate(arr):
            if i == pos:
                active = True
            if s == 1:
                if active == True:
                    return (start, end)
                else:
                    start = i + 1
                    end = i + 1
            else:
                end = i
        return start, end

    def count_hw_light(h, w):
        if s_arr[h][w] == 1:
            return 0

        m = memo[h][w] # (3, 2) / (-1, -1) / ( -1, 2) / (3, -1)
        dprint(h, w, m)
        count = 0
        counth = m[0]
        countw = m[1]
        if counth == -1:
            arr = s_arr[:, w]
            start, end = count_light(arr, h)
            count += (end - start) + 1
            dprint("h", arr, h, end, start)
            for i in range(start, end+1):
                memo[i][w] = ((end - start) + 1, countw)
        else:
            count += counth

        if countw == -1:
            arr = s_arr[h, :]
            start, end = count_light(arr, w)
            count += (end - start) + 1
            dprint("w", arr, w, end, start)
            for i in range(start, end+1):
                memo[h][i] = (counth, (end - start) + 1)
        else:
            count += countw

        dprint(h, w, memo[h][w], counth, countw, count)
        dprint(memo)
        return count

    mx_ans = 0
    for h in range(H):
        for w in range(W):
            ans = count_hw_light(h, w) -1 # 重複カウント消し
            if ans >= mx_ans:
                mx_ans = ans

    print(mx_ans)

    dprint(s_arr)
    dprint(memo)

solve()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
mp=[]
h_wall=[]
for i in range(h):
    h_wall_l=[]
    l=input()
    mp.append(l)
    for a in range(len(l)):
        if l[a]=='#':
            h_wall_l.append(a)
    h_wall.append(h_wall_l)
v_wall=[]
for i in range(w):
    vl=''
    for j in range(h):
      vl+=mp[j][i]
    v_wall_vl=[]
    for a in range(len(vl)):
        if vl[a]=='#':
            v_wall_vl.append(a)
    v_wall.append(v_wall_vl)
h_mp=[]
for i in h_wall:
    if len(i)!=0:
        hll=[]
        first=i[0]
        for j in range(first):
            hll.append(first)
        hll.append(-1)
        if len(i)>=2:
            for j in range(len(i)-1):
                mid=i[j+1]-i[j]-1
                for z in range(mid):
                    hll.append(mid)
                hll.append(-1)
        if len(hll)<w:
            diff = w-len(hll)
            for z in range(diff):
                hll.append(diff)
    else:
        hll=[w for zz in range(w)]
    h_mp.append(hll)
v_mp = []
for i in v_wall:
    if len(i)!=0:
        vll=[]
        first=i[0]
        for j in range(first):
            vll.append(first)
        vll.append(-1)
        if len(i)>=2:
            for j in range(len(i)-1):
                mid=i[j+1]-i[j]-1
                for z in range(mid):
                    vll.append(mid)
                vll.append(-1)
        if len(vll)<h:
            diff = h-len(vll)
            for z in range(diff):
                vll.append(diff)
    else:
        vll=[h for zz in range(h)]
    v_mp.append(vll)
# for i in v_mp:
#     print(i)
# print("---")

v_mp = [list(x) for x in zip(*v_mp)]
# for i in h_mp:
#     print(i)
# print("---")
# for i in v_mp:
#     print(i)

maxx=0

for i in range(h):
    for j in range(w):
        hhh = h_mp[i][j]
        vvv = v_mp[i][j]
        if hhh != -1 and vvv != -1:
            temp = hhh+vvv-1
            if temp >= maxx:
                maxx=temp
print(maxx)

Submission status: Time Limit Exceeded

Solution code:
H, W = tuple(map(int, input().split()))
s = []
ans = 0

for i in range(H):
    s.append(input())

def checkLamp(h, w):
    count = 0
    if (s[h][w] == "#"):
        return -1
    if (h > 0):
        for u in reversed(range(h)):
            if (s[u][w] == "."):
                count += 1
            else:
                break
    if (h < H-1):
        for d in range(h+1,H):
            if (s[d][w] == "."):
                count += 1
            else:
                break
    if (w > 0):
        for l in reversed(range(w)):
            if (s[h][l] == "."):
                count += 1
            else:
                break
    if (w < W-1):
        for r in range(w+1, W):
            if (s[h][r] == "."):
                count += 1
            else:
                break
    return count

for h in range(H):
    for w in range(W):
        ans = max(ans, checkLamp(h, w))

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
import numpy as np
R,C = map(int,input().split())
S = []
for i in range(R):
    S.append(list(input()))

ue = np.zeros((R,C),dtype='int16')
sita = np.zeros((R,C),dtype='int16')
migi = np.zeros((R,C),dtype='int16')
hidari = np.zeros((R,C),dtype='int16')
for i in range(C):
    tmp1 = 0
    tmp2 = 0
    for j in range(R):
        j2 = R-1-j
        tmp1 += 1
        tmp2 += 1
        if S[j][i] == '#': tmp1 = 0
        if S[j2][i] == '#': tmp2 = 0
        ue[j][i] = tmp1
        sita[j2][i] = tmp2
for i in range(R):
    tmp1 = 0
    tmp2 = 0
    for j in range(C):
        j2 = C-1-j
        tmp1 += 1
        tmp2 += 1
        if S[i][j] == '#': tmp1 = 0
        if S[i][j2] == '#': tmp2 = 0
        hidari[i][j] = tmp1
        migi[i][j2] = tmp2

ans = 0
for i in range(R):
    for j in range(C):
        if S[i][j] != '#':
            tmp = ue[i][j]+sita[i][j]-1 + migi[i][j]+hidari[i][j]-1 -1
            if tmp > ans: ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
map_matrix=[]
calc_matrix=[]
for i in range(H):
  line=[True if s=="." else False for s in input()]
  map_matrix.append(line)
  calc_matrix.append([0]*W)

map_matrix_h=[]
for h in range(H):
  line=[i for i, x in enumerate(map_matrix[h]) if not x]
  map_matrix_h.append([-1]+line+[W])

#print(map_matrix_h)
score_matrix_h=[]
for i in range(H):
  h2list = map_matrix_h[i]  
  score = [W]*W
  for j in range(len(h2list)-1):
    hl=h2list[j]
    hr=h2list[j+1]    
    #print("{},{}".format(hl,hr))
    if hl==-1 and hr==W:
      score=[W]*W
    elif hl==-1:
      score[0:hr]=[hr]*hr
      score[hr]=0
    elif hr==W:
      score[hl]=0
      score[hl+1:]=[W-hl-1]*(W-hl-1)
    else:
      score[hl]=0
      score[hl+1:hr]=[hr-hl-1]*(hr-hl-1)
      score[hr]=0
  #print(score)
  score_matrix_h.append(score)

map_matrix_w=[]
map_matrix_tr=list(map(list, zip(*map_matrix)))
#print(map_matrix_tr)

for w in range(W):
  line=[i for i, x in enumerate(map_matrix_tr[w]) if not x]
  #map_matrix_w.append(line)
  map_matrix_w.append([-1]+line+[H])

#print(map_matrix_w)
score_matrix_w=[]
for i in range(W):
  w2list = map_matrix_w[i]  
  score = [H]*H
  for j in range(len(w2list)-1):
    wl=w2list[j]
    wr=w2list[j+1]    
    #print("{},{}".format(hl,hr))
    if wl==-1 and wr==H:
      score=[H]*H
    elif wl==-1:
      score[0:wr]=[wr]*wr
      score[wr]=0
    elif wr==H:
      score[wl]=0
      score[wl+1:]=[H-wl-1]*(H-wl-1)
    else:
      score[wl]=0
      score[wl+1:wr]=[wr-wl-1]*(wr-wl-1)
      score[wr]=0
  #print(score)
  score_matrix_w.append(score)

#print(score_matrix_w)

max_right = -1
for i in range(H):
  for j in range(W):
    right = score_matrix_h[i][j]+score_matrix_w[j][i]-1
    if right > max_right:
      max_right = right
      
print(max_right)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros([H,W])    # .の連続数を格納用

for i in range(H):
    S.append(input())
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ij[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ij[start:end+1, j] += cnt
            cnt = 0

ij = ij - 1  # 自分が2回足されるので、1引く
ans = int(ij.max())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    H, W = LI()
    hs = [[-1] for _ in range(H)]
    ws = [[-1] for _ in range(W)]
    for h in range(H):
        s = SI()
        for w, ss in enumerate(s):
            if ss == '#':
                hs[h].append(w)
                ws[w].append(h)
    for h in range(H):
        hs[h].append(W)
    for w in range(W):
        ws[w].append(H)
    ah = [[0] * W for _ in range(H)]
    aw = [[0] * H for _ in range(W)]
    for hh, h in enumerate(hs):
        for wi in range(len(h) - 1):
            l, u = h[wi] + 1, h[wi + 1]
            cnt = u - l
            for i in range(l, u):
                ah[hh][i] = cnt
    for ww, w in enumerate(ws):
        for hi in range(len(w) - 1):
            l, u = w[hi] + 1, w[hi + 1]
            cnt = u - l
            for i in range(l, u):
                aw[ww][i] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, aw[w][h] + ah[h][w] - 1)
    return ans

print(main())

Submission status: Time Limit Exceeded

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

P = [[0 if x == "#" else 1 for x in input()] for _ in range(H)]
C = [[-3*P[x][y] for y in range(W)] for x in range(H)]

for j in range(W):
    cntU = 0
    cntD = 0
    for i in range(H):
        if P[i][j] == 0:
            cntD = 0
        else:
            cntD += 1
        C[i][j] += cntD 

        if P[H-1-i][j] == 0:
            cntU = 0
        else:
            cntU += 1
        C[H-1-i][j] += cntU 

for i in range(H):
    cntR = 0
    cntL = 0
    for j in range(W):
        if P[i][j] == 0:
            cntR = 0
        else:
            cntR += 1
        C[i][j] += cntR 

        if P[i][W-1-j] == 0:
            cntL = 0
        else:
            cntL += 1
        C[i][W-1-j] += cntL 




print(max((x for ci in C for x in ci)))

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

for i in range(W):
    cou = 0
    hoge = []
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            hoge.append(cou)
            cou = 0
    hoge.append(cou)
    ws = []
    for j in hoge:
        ws = ws+[j]*j+[0]
    #print(ws,ws[:-1])
    for j in range(H):
        ans =max( Grid1[j][i] +ws[j], ans)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
S = [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)])


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

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

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

Submission status: Time Limit Exceeded

Solution code:

h, w = map(int, input().split())
s = [input() for i in range(h)]
hnum = [[0 for _ in range(w+1)] for _ in range(h+1)]
wnum = [[0 for _ in range(w+1)] for _ in range(h+1)]
#print(s)

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

    if t != 0:
        hnum[i][-1] = t
        t = 0

for i in range(h, 0, -1):
    for j in range(w, 0, -1):
        if hnum[i][j] != -1 and hnum[i][j-1] == 0 :
            hnum[i][j-1] =  hnum[i][j]


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

    if t != 0:
        wnum[-1][j] = t
        t = 0

for j in range(w, 0, -1):
    for i in range(h, 0, -1):
        if wnum[i][j] != -1 and wnum[i-1][j] == 0 :
            wnum[i-1][j] =  wnum[i][j]

res = 0
for i in range(h):
    for j in range(w):
        if res < hnum[i+1][j+1] + wnum[i+1][j+1]-1:
            res = hnum[i+1][j+1] + wnum[i+1][j+1]-1

print(res)

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

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 = 1
madaikeru = True
for i in range(1, h+1):
    for j in range(1, w+1):
        if masu[i, j] == 1:
            gyou = i
            while madaikeru:
                gyou -= 1
                if masu[gyou, j] == 1:
                    temp += 1
                else:
                    madaikeru = False
            gyou = i
            madaikeru = True
            while madaikeru:
                gyou += 1
                if masu[gyou, j] == 1:
                    temp += 1
                else:
                    madaikeru = False
            retu = j
            madaikeru = True
            while madaikeru:
                retu -= 1
                if masu[i, retu] == 1:
                    temp += 1
                else:
                    madaikeru = False
            retu = j
            madaikeru = True
            while madaikeru:
                retu += 1
                if masu[i, retu] == 1:
                    temp += 1
                else:
                    madaikeru = False
            madaikeru = True
            ans = max(ans, temp)
            temp = 1

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 = []
  for j in lis[i]:
    e = len(j)
    for n in range(len(j)):
      s.append(e)
    s.append(0)
  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 i in range(h)]

def search(y,x):
    cnt_u=0
    cnt_d=0
    cnt_l=0
    cnt_r=0

    for u in reversed(range(y)):
        if s[u][x]=="#":
            break
        else:
            cnt_u+=1
    for d in range(y+1,h):
        if s[d][x]=="#":
            break
        else:
            cnt_d+=1
    for l in reversed(range(x)):
        if s[y][l]=="#":
            break
        else:
            cnt_l+=1
    for r in range(x+1,w):
        if s[y][r]=="#":
            break
        else:
            cnt_r+=1

    return cnt_u+cnt_d+cnt_l+cnt_r+1


ans=[]

for i in range(h):
    for k in range(w):
        if s[i][k]==".":
            ans.append(search(i,k))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

q = deque([])

H,W = map(int,input().split())
L = []

for i in range(H) :
    S = input()
    for j in range(W) :
        if S[j] == "." :
            q.append((i,j))
    L.append(list(S))

ans = 0

while q :
    y,x = q.popleft()
    
    cnt = 1
    
    d = [1,-1]
    
    for dy in d :
        ny = y
        
        while True :
            ny += dy
            
            if (ny < 0) or (ny >= H) :
                break
            
            if L[ny][x] == "#" :
                break
            
            cnt += 1
    
    for dx in d :
        nx = x
        
        while True :
            nx += dx
            
            if (nx < 0) or (nx >= W) :
                break
            
            if L[y][nx] == "#" :
                break
            
            cnt += 1
    
    ans = max(ans,cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    h, w = map(int, input().split())
    S = list(input() + '#' for _ in range(h)) + ['#' * (w + 1)]
    H = [[0] * w for _ in range(h + 1)]
    W = [[0] * w for _ in range(h + 1)]
    for r in range(h):
        c = 0
        while c < w:
            if S[r][c] == '.':
                t = S[r][c:].find('#')
                for j in range(c, c + t):
                    W[r][j] = t
                c += t
            c += 1
    for c in range(w):
        r = 0
        while r < h:
            if S[r][c] == '.':
                t = r + 1
                cnt = 1
                while S[t][c] == '.':
                    t += 1
                    cnt += 1
                for i in range(r, t):
                    H[i][c] = cnt
                r = t
            r += 1
    ans = 0
    for r in range(h):
        for c in range(w):
            ans = max(ans, H[r][c] + W[r][c] - 1)
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"
 
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
# def LLS(): return [list(map(str, l.split())) for l in sys.stdin.readlines()]
# def LLS(): return list(input()) for l in sys.stdin.readlines()]

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


def main():
    H, W = list(map(int,input().split()))
    S=[]
    for i in range(H):
        S.append(list(input()) )
    # print(S)
    S=np.asarray(S)

    R=np.zeros([H,W],dtype=int)
    C=np.zeros([W,H],dtype=int)
    # R[0,2:3]=
    for h,ss in enumerate(S):
        tmp=0
        for w,s in enumerate(ss):
            if s==".":
                tmp+=1
            else:
                R[h,w-tmp:w]=tmp
                tmp=0
        if tmp>0:
            R[h,w-tmp+1:w+1]=tmp
            tmp=0


    for h,ss in enumerate(S.T):
        tmp=0
        for w,s in enumerate(ss):
            if s==".":
                tmp+=1
            else:
                C[h,w-tmp:w]=tmp
                tmp=0
        if tmp>0:
            C[h,w-tmp+1:w+1]=tmp
            tmp=0
    out=int((R+C.T).max()-1)
    if out>0:
        print(out)
    else:
        print("0")
            # print(s)
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
map1=[[0]*w for i in range(h)]
map2=[[0]*w for i in range(h)]
for i in range(h):
  count=0
  for j in range(w):
    if data[i][j]=="#":
      count=0
    else:
      count+=1
      map1[i][j]=count
  count=0
  for j in range(w):
    if map1[i][-1-j]==0:
      count=0
    else:
      count=max(map1[i][-1-j],count)
      map1[i][-1-j]=count
for i in range(w):
  count=0
  for j in range(h):
    if data[j][i]=="#":
      count=0
    else:
      count+=1
      map2[j][i]=count
  count=0
  for j in range(h):
    if map2[-j-1][i]==0:
      count=0
    else:
      count=max(map2[-j-1][i],count)
      map2[-j-1][i]=count
ans=0
for i in range(h):
  for j in range(w):
    tmp=map1[i][j]+map2[i][j]
    ans=max(ans,tmp)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(i, y) returns the tuple (i//y, i%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l
import sys
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(i, y):
    return (i * y) // gcd(i, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)
# set the inputs
    # open(0).read() is a convenient method:
    # ei) n, m, *i = map(int, open(0).read().split())
    #     min(i[::2]) - mai(i[1::2])
    # ei2) *i, = map(int, open(0).read().split())
    #     don't forget to add comma after *i if only one variable is used
    # R = lambda: map(int, input().split()) :it's fashionable, isn't it?
    # ei1) n, k = R()
    # ei2) v = list(R())
    # ei3) bc = [list(R()) for i in range(m)]

# R = lambda: list(map(int, input().split()))
# n = int().input()
# ab = [R() for i in range(n)]
# c = R()
# c = sorted(c, reverse = True)

R = lambda: list(map(int, input().split()))
h, w = R()
s = [input() for i in range(h)]

s_ = [list(x) for x in zip(*s)]

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

for j,str in enumerate(s):
    count = 0
    col = 0
    for i, eachstr in enumerate(str):
        if eachstr == "#":
            if i == 0:
                pass
            else:
                for k in range(col,i):
                    ho[j][k] = count
            col = i + 1
            count = 0
        else:
            count += 1
    else:
        if col < w:
            for k in range(col,i+1):
                ho[j][k] = count

for j,str in enumerate(s_):
    count = 0
    col = 0
    for i, eachstr in enumerate(str):
        if eachstr == "#":
            if i == 0:
                pass
            else:
                for k in range(col,i):
                    he[j][k] = count
            col = i + 1
            count = 0
        else:
            count += 1
    else:
        if col < w:
            for k in range(col,i+1):
                he[j][k] = count

he_ = [list(x) for x in zip(*he)]

ans = 0
for i,j in zip(ho,he_):
    for ss, tt in zip(i,j):
        ans = max(ans, ss+tt)
print(ans-1)

Submission status: Time Limit Exceeded

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

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

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


        current_sum = above + left + right + bottom -1
        if current_sum > max_s:
            max_s = current_sum
print(max_s)