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())
G = []
l_w = [[0] * w for i in range(h)]
l_h = [[0] * w for i in range(h)]
for i in range(h):
    G.append(input())
for i in range(h):
    cnt = 0
    for j in range(w):
        if G[i][j] == ".":
            cnt += 1
            l_w[i][j] = cnt
        else:
            cnt = 0
    tmp = 0
    for j in range(w - 1, -1, -1):
        if l_w[i][j] > 0 and tmp == 0:
            tmp = l_w[i][j]
        elif l_w[i][j] > 0 and tmp > 0:
            l_w[i][j] = tmp
        elif l_w[i][j] == 0 and tmp > 0:
            tmp = 0
for i in range(w):
    cnt = 0
    for j in range(h):
        if G[j][i] == ".":
            cnt += 1
            l_h[j][i] = cnt
        else:
            cnt = 0
    tmp = 0
    for j in range(h - 1, -1, -1):
        if l_h[j][i] > 0 and tmp == 0:
            tmp = l_h[j][i]
        elif l_h[j][i] > 0 and tmp > 0:
            l_h[j][i] = tmp
        elif l_h[j][i] == 0 and tmp > 0:
            tmp = 0
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, l_w[i][j] + l_h[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
G = []
l_w = np.array([[0] * w for i in range(h)])
l_h = np.array([[0] * w for i in range(h)])
for i in range(h):
    G.append(input())
for i in range(h):
    cnt = 0
    for j in range(w):
        if G[i][j] == ".":
            cnt += 1
            l_w[i][j] = cnt
        else:
            cnt = 0
    tmp = 0
    for j in range(w - 1, -1, -1):
        if l_w[i][j] > 0 and tmp == 0:
            tmp = l_w[i][j]
        elif l_w[i][j] > 0 and tmp > 0:
            l_w[i][j] = tmp
        elif l_w[i][j] == 0 and tmp > 0:
            tmp = 0
for i in range(w):
    cnt = 0
    for j in range(h):
        if G[j][i] == ".":
            cnt += 1
            l_h[j][i] = cnt
        else:
            cnt = 0
    tmp = 0
    for j in range(h - 1, -1, -1):
        if l_h[j][i] > 0 and tmp == 0:
            tmp = l_h[j][i]
        elif l_h[j][i] > 0 and tmp > 0:
            l_h[j][i] = tmp
        elif l_h[j][i] == 0 and tmp > 0:
            tmp = 0
l = l_w + l_h
print(np.max(l)-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [LI()for i in range(n)]
inf = 10**17
mod = 10**9 + 7

h,w=MI()
mat1 =[[] for i in range(h)]
mat2 =[[0 for j in range(w)] for i in range(h)]
mat3 =[[0 for j in range(w)] for i in range(h)]
mat4 =[[0 for j in range(w)] for i in range(h)]
mat5 =[[0 for j in range(w)] for i in range(h)]


for i in range(h):
    s=input().rstrip()
    for j in range(w):
        mat1[i].append(s[j])
#print(mat1)

for i in range(h):
    for j in range(w):
        if mat1[i][j]=="#":
            mat2[i][j]=0
        else:
            if j==0:
                mat2[i][j]=1
            else:
                mat2[i][j]=mat2[i][j-1]+1
#print(mat2)

for i in range(h):
    for j in reversed(range(w)):
        #print(i,j)
        if mat1[i][j]=="#":
            mat3[i][j]=0
        else:
            if j==w-1:
                mat3[i][j]=1
            else:
                mat3[i][j]=mat3[i][j+1]+1
#print(mat3)

for i in range(w):
    for j in range(h):
        if mat1[j][i]=="#":
            mat4[j][i]=0
        else:
            if j==0:
                mat4[j][i]=1
            else:
                mat4[j][i]=mat4[j-1][i]+1
#print(mat4)

for i in range(w):
    for j in reversed(range(h)):
        if mat1[j][i]=="#":
            mat5[j][i]=0
        else:
            if j==h-1:
                mat5[j][i]=1
            else:
                mat5[j][i]=mat5[j+1][i]+1
#print(mat5)
mx=0
for i in range(h):
    for j in range(w):
        if mat1[i][j]==".":
            ans=mat2[i][j]+mat3[i][j]+mat4[i][j]+mat5[i][j]-3
            if ans>mx:
                mx=ans
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
cnt1 = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt1[i][j] = 1

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt1[i][j] += cnt1[i][j-1]
for i in range(H):
  for j in range(W-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= W-1:
      cnt1[i][j] = max(cnt1[i][j], cnt1[i][j+1])

S2 = [[0]*H for _ in range(W)]
for i in range(H):
  for j in range(W):
    S2[j][i] = S[i][j]

cnt2 = [[0]*H for _ in range(W)]
for i in range(W):
  for j in range(H):
    if S2[i][j] == '#':
      continue
    cnt2[i][j] = 1

for i in range(W):
  for j in range(H):
    if S2[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt2[i][j] += cnt2[i][j-1]
for i in range(W):
  for j in range(H-1, -1, -1):
    if S2[i][j] == '#':
      continue
    if j+1 <= H-1:
      cnt2[i][j] = max(cnt2[i][j], cnt2[i][j+1])


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)])
cnt1 = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    cnt1[i][j] = 1

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt1[i][j] += cnt1[i][j-1]
for i in range(H):
  for j in range(W-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= W-1:
      cnt1[i][j] = max(cnt1[i][j], cnt1[i][j+1])

cnt1 = np.array(cnt1)
S = S.T
cnt2 = [[0]*H for _ in range(W)]
for i in range(W):
  for j in range(H):
    if S[i][j] == '#':
      continue
    cnt2[i][j] = 1

for i in range(W):
  for j in range(H):
    if S[i][j] == '#':
      continue
    if j-1 >= 0:
      cnt2[i][j] += cnt2[i][j-1]
for i in range(W):
  for j in range(H-1, -1, -1):
    if S[i][j] == '#':
      continue
    if j+1 <= H-1:
      cnt2[i][j] = max(cnt2[i][j], cnt2[i][j+1])
cnt2 = np.array(cnt2).T

cnt = cnt1 + cnt2
print(np.max(cnt)-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        s = list(input())
        S.append(s)
    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    for i in range(H):
        cnt1 = 0
        cnt2 = 0
        for j in range(W):
            if S[i][j]=='#':
                cnt1 = 0
            else:
                cnt1 += 1
                L[i][j] = cnt1
        for j in range(W-1, -1, -1):
            if S[i][j]=='#':
                cnt2 = 0
            else:
                cnt2 += 1
                R[i][j] = cnt2

    for j in range(W):
        cnt1 = 0
        cnt2 = 0
        for i in range(H):
            if S[i][j]=='#':
                cnt1 = 0
            else:
                cnt1 += 1
                U[i][j] = cnt1
        for i in range(H-1,-1,-1):
            if S[i][j]=='#':
                cnt2 = 0
            else:
                cnt2 += 1
                D[i][j] = cnt2

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import bisect
readline = sys.stdin.buffer.readline
MOD = 10**9+7
INF = float('inf')

def main():
    H, W = map(int, readline().split())
    S = []
    for _ in range(H):
        s = list(input())
        S.append(s)
    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    for i in range(H):
        cnt = 0
        for j in range(W):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                L[i][j] = cnt
    for i in range(H):
        cnt = 0
        for j in range(W-1, -1, -1):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                R[i][j] = cnt
    for j in range(W):
        cnt = 0
        for i in range(H):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                U[i][j] = cnt
    for j in range(W):
        cnt = 0
        for i in range(H-1,-1,-1):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                D[i][j] = cnt
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=['']*h
for i in range(h):
  s[i]=input()
ans=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
for j in range(w):
  for i in range(h):
    if s[i][j]=='#':
      ans[i][j][0]=-1
      ans[i][j][2]=-1
    else:
      if not j==0:
        ans[i][j][0]=ans[i][j-1][0]+1
      if not i==0:
        ans[i][j][2]=ans[i-1][j][2]+1
for j in range(w)[::-1]:
  for i in range(h)[::-1]:
    if s[i][j]=='#':
      ans[i][j][1]=-1
      ans[i][j][3]=-1
    else:
      if not j==w-1:
        ans[i][j][1]=ans[i][j+1][1]+1
      if not i==h-1:
        ans[i][j][3]=ans[i+1][j][3]+1
mx_ans=0
for i in range(h):
  for j in range(w):
    mx_ans=max(mx_ans,sum(ans[i][j]))
print(mx_ans+1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=['']*h
for i in range(h):
  s[i]=input()
ans=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans[i][j][0]=-1
    elif not j==0:
      ans[i][j][0]=ans[i][j-1][0]+1
for i in range(h):
  for j in range(w)[::-1]:
    if s[i][j]=='#':
      ans[i][j][1]=-1
    elif not j==w-1:
      ans[i][j][1]=ans[i][j+1][1]+1
for j in range(w):
  for i in range(h):
    if s[i][j]=='#':
      ans[i][j][2]=-1
    elif not i==0:
      ans[i][j][2]=ans[i-1][j][2]+1
for j in range(w):
  for i in range(h)[::-1]:
    if s[i][j]=='#':
      ans[i][j][3]=-1
    elif not i==h-1:
      ans[i][j][3]=ans[i+1][j][3]+1
mx_ans=0
for i in range(h):
  for j in range(w):
    mx_ans=max(mx_ans,sum(ans[i][j]))
print(mx_ans+1)

Submission status: Time Limit Exceeded

Solution code:
#Satoooh 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# そのマスを含めてLeft, Right, Up, Downに
#それぞれ何マス分明かりを照らせるかを配列に記録
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):#全マスを走査
		if S[i][j] == ".":
			if j == 0:#一番左側のマスについて
				L[i][j] = 1
			else:#それ以外
				L[i][j] = L[i][j - 1] + 1
                #累積和のように、１個左側の値にプラス１

for i in range(H):
	for j in range(W - 1, -1, -1):#右側からの連続をチェック
		if S[i][j] == ".":
			if j == W - 1:#一番右側のマスについて
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

for j in range(W):
	for i in range(H - 1, -1, -1):#下からの連続
		if S[i][j] == ".":
			if i == H - 1:#一番下のマスについて
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:#一番上のマスについて
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1


ans = 0
X = [[0] * W for _ in range(H)]#全マスを０で初期化
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
        #自分自身のマスは上記４回足している
	ans = max(ans, max(X[i]))
    #最大値で更新。配列Xは元々２次元だが、
    #ここでは横１次元をまとめて見ている

print(ans)#最も多くのマスを照らせる場合のマスの個数

Submission status: Time Limit Exceeded

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

U = [[0 for _ in range(w)] for _  in range(h)]
D = [[0 for _ in range(w)] for _  in range(h)]
L = [[0 for _ in range(w)] for _  in range(h)]
R = [[0 for _ in range(w)] for _  in range(h)]

for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            U[y][x],L[y][x] = 0,0
        else:
            if y == 0 and x >= 1:
                U[0][x] = 1
                L[y][x] += 1 + L[y][x-1]
            elif x == 0 and y >= 1: 
                U[y][x] += 1 + U[y-1][x]
                L[y][0] = 1
            elif x == 0 and y == 0:
                U[y][x] = 1
                L[y][x] = 1
            else:
                U[y][x] += 1 + U[y-1][x]
                L[y][x] += 1 + L[y][x-1]

for y in range(h-1,-1,-1):
    for x in range(w-1,-1,-1):
        if maps[y][x] == "#":
            D[y][x],R[y][x] = 0,0
        else:
            if y == h-1 and x < w-1:
                D[y][x] = 1
                R[y][x] += 1 + R[y][x+1]
            elif x == w-1 and y < h-1:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] = 1
            elif  x == w-1 and y == h-1:
                D[y][x] = 1
                R[y][x] = 1
            else:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] += 1 + R[y][x+1]

ans = 0
#AnsMap = [[0 for _ in range(w)] for _  in range(h)]
for i in range(h):
    for j in range(w):
        #AnsMap[i][j] = L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0
for x in range(w):
    for y in range(h):
        if maps[y][x] == "#":
            continue
        else:
            tmpans = 0
            for u in range(y,-1,-1):
                if maps[u][x] == "#":
                    break
                else:
                    tmpans += 1
            for d in range(y+1, h):
                if maps[d][x] == "#":
                    break
                else:
                    tmpans += 1
            
            for l in range(x,-1,-1):
                if maps[y][l] == "#":
                    break
                else:
                    tmpans += 1
            for r in range(x+1,w):
                if maps[y][r] == "#":
                        break
                else:
                    tmpans += 1
                    
            ans = max(tmpans,ans)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = [[0]*w for i in range(h)]
for i in range(h):
    count = 0
    for j in range(w):
        if (a[i][j]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                s[i][k]=count
            count = 0
    for k in range(w-1,w-count-1,-1):
        s[i][k]=count
    count = 0

t = [[0]*w for i in range(h)]
for i in range(w):
    count = 0
    for j in range(h):
        if (a[j][i]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                t[k][i]=count
            count = 0
    for k in range(h-1,h-count-1,-1):
        t[k][i]=count
    count = 0

ans = 0
for i in range(h):
    for j in range(w):
        if (s[i][j]!=0):
            if (s[i][j]+t[i][j]-1 > ans):
                ans = s[i][j]+t[i][j]-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = copy.deepcopy(s)
for i in range(h):
    count = 0
    for j in range(w):
        if (s[i][j]=='.'):
            count += 1
            
        else:
            for k in range(j-1,j-count-1,-1):
                s[i][k]=count
            count = 0
    for k in range(w-1,w-count-1,-1):
        s[i][k]=count
    count = 0

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

ans = 0
for i in range(h):
    for j in range(w):
        if (s[i][j]!="#"):
            if (s[i][j]+t[i][j]-1 > ans):
                ans = s[i][j]+t[i][j]-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re

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

l_wall = [[i.span()[0] for i in re.finditer('#', '#'+s+'#')] for s in S_list]
r_wall = [[i.span()[0] for i in re.finditer('#', '#'+''.join(s)+'#')] for s in list(zip(*S_list))]

l_light = sum([[i[j+1]-i[j]-1 for j in range(len(i)-1)] if len(i) != 1 else i for i in l_wall], [])
r_light = sum([[i[j+1]-i[j]-1 for j in range(len(i)-1)] if len(i) != 1 else i for i in r_wall], [])

ans = max([l+r-1 for l in l_light for r in r_light])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re

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

l_count = [[i.span()[0] for i in re.finditer('#', s+'#')] for s in S_list]

r_count = [[i.span()[0] for i in re.finditer('#', ''.join(s)+'#')] for s in list(zip(*S_list))]

ans = 0
    
for h in range(H):
    for w in range(W):
        if S_list[h][w] == '.':
            l_light = 0
            r_light = 0
            for l in l_count[h]:
                if(w < l):
                    l_light = l - l_light
                    break
                l_light = l+1
            for r in r_count[w]:
                if(h < r):
                    r_light = r - r_light
                    break
                r_light = r+1
            
            ans = max(ans, l_light+r_light-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)

def get_dp(d, width, height):
  pos = np.array([[i for i in range(width)]]*height)
  obs_pos = []
  for i in range(height):
    obs_pos.append(pos[i][d[i]=='#'].tolist()+[width])
  dp = np.zeros_like(d, dtype=int)
  for y in range(height):
    s = 0
    for p in obs_pos[y]:
      dp[y][s:p] = p-s
      s = p+1
  return dp

dp_row = get_dp(S, w, h)
dp_col = get_dp(S.T, h, w)
print((dp_row+dp_col.T).max() - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)
data = np.zeros_like(S, dtype=int)
data[S=='.'] = 1

def get_dp(d, width):
  dp = d.copy()
  for i, row in enumerate(d):
    for j in range(1, width):
      val = row[j]
      if val > 0:
        n = dp[i][j-1]
        dp[i][j] += n
        dp[i, j-n:j] += 1
  return dp

dp_row = get_dp(data, w)
dp_col = get_dp(data.T, h)
print((dp_row+dp_col.T).max() - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
S = [str(input()) for _ in range(h)]
data = []
for s in S:
  row = []
  for c in s:
    row.append(1 if c=='.' else 0)
  data.append(row)
data = np.array(data, dtype=int)

def get_dp(d, width):
  dp = d.copy()
  for i, row in enumerate(d):
    for j in range(1, width):
      val = row[j]
      if val > 0:
        n = dp[i][j-1]
        dp[i][j] += n
        for k in range(n):
          dp[i][j-k-1] += 1
  return dp

dp_row = get_dp(data, w)
dp_col = get_dp(data.T, h)
print((dp_row+dp_col.T).max() - 1)

Submission status: Time Limit Exceeded

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

S_l = [[0] * w for _ in range(h)]
S_r = [[0] * w for _ in range(h)]
S_u = [[0] * w for _ in range(h)]
S_d = [[0] * w for _ in range(h)]

for i in range(h):
    cnt_l = 0
    cnt_r = 0
    for j in range(w):
        if S[i][j] == '.':
            if cnt_l == 0:
                S_l[i][j] = 1
                cnt_l = 1
            else:
                S_l[i][j] = S_l[i][j-1] + 1
        else:
            cnt_l = 0
            S_l[i][j] = 0

        if S[i][w-j-1] == '.':
            if cnt_r == 0:
                S_r[i][w-j-1] = 1
                cnt_r = 1
            else:
                S_r[i][w-j-1] = S_r[i][w-j] + 1
        else:
            cnt_r = 0
            S_r[i][w-j-1] = 0


for j in range(w):
    cnt_u = 0
    cnt_d = 0
    for i in range(h):
        if S[i][j] == '.':
            if cnt_u == 0:
                S_u[i][j] = 1
                cnt_u = 1
            else:
                S_u[i][j] = S_u[i-1][j] + 1
        else:
            cnt_u = 0
            S_u[i][j] = 0
        
        if S[h-i-1][j] == '.':
            if cnt_d == 0:
                S_d[h-i-1][j] = 1
                cnt_d = 1
            else:
                S_d[h-i-1][j] = S_d[h-i][j] + 1
        else:
            cnt_d = 0
            S_d[h-i-1][j] = 0

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, S_l[i][j] + S_r[i][j] + S_u[i][j] + S_d[i][j] - 3)

print(ans)

Submission status: Time Limit Exceeded

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

res_h = []
for line in mp:
    count = 0
    start = 0
#    res_line = [0] * W
    res_line = np.zeros(W, dtype=int)
    for i, v in enumerate(line):
        if v == "#":
            res_line[start:i] = count
            count = 0
            start = i+1
        if v == ".":
            count += 1
    res_line[start:i+1] = count
    res_h += [res_line]

mpt = np.array([list(l) for l in mp]).T
res_v = []
for line in mpt:
    count = 0
    start = 0
    res_line = np.zeros(H, dtype=int)
    for i, v in enumerate(line):
        if v == "#":
            res_line[start:i] = count
            count = 0
            start = i+1
        if v == ".":
            count += 1
    res_line[start:i+1] = count
    res_v += [res_line]

res = (np.array(res_v).T + np.array(res_h)).max()
print(res - 1)

Submission status: Time Limit Exceeded

Solution code:
def convert(L):
    H=len(L)
    W=len(L[0])
    dp = [[0 for _ in range(W)] for _ in range(H)]
    #dp = np.zeros((L.shape[0],L.shape[1]), dtype='int')
    for i in range(H):
        l=L[i]
        for j in range(W):
            if l[j]:
                if j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i][j-1] + 1
            else:
                dp[i][j] = 0
    return dp
H,W=map(int,input().split())
L= [[] for _ in range(H)]
for i in range(H):
    L[i]=list(map(lambda x: False if x=="#" else True,list(input()) ))

def rr(matrix):
    return list(map(list, zip(*matrix)))[::-1]

def mir(L):
    return [list(l[::-1]) for l in L]
def flip(L):
    H=len(L)
    W=len(L[0])
    return [[L[i][j] for i in range(H)] for j in range(W)]
A=rr(L)
B=rr(rr(L))
C=rr(rr(rr(L)))
LL=convert(L)
AA=rr(rr(rr(convert(A))))
BB=rr(rr(convert(B)))
CC=rr(convert(C))
#K=flip(L)
ans = -1
M=[[0for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        t = LL[i][j]+AA[i][j]+BB[i][j]+CC[i][j]-3 
        ans = max(ans,t)
        M[i][j] = t
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
tate=[]

for i in range(W):
    c=0
    ad=[]
    while(c<H):
        ad.append(S[c][i])
        c+=1
    tate.append(ad)

left=[]
right=[]
up=[]
down=[]

for i in range(H):
    tmp=S[i]
    cnt=0
    al = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j]==".":
            cnt+=1
            al[j]=cnt
        else:
            cnt=0
    left.append(al)

for i in range(H):
    tmp = S[i]
    tmp=tmp[::-1]
    cnt = 0
    ar = [0 for _ in range(W)]
    for j in range(W):
        if tmp[j] == ".":
            cnt += 1
            ar[j] = cnt
        else:
            cnt = 0
    ar=ar[::-1]
    right.append(ar)

for j in range(W):
    tt=tate[j]
    cnt=0
    bl=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            bl[k]=cnt
        else:
            cnt=0
    up.append(bl)

for j in range(W):
    tt=tate[j]
    tt=tt[::-1]
    cnt=0
    br=[0 for i in range(H)]
    for k in range(H):
        if tt[k]==".":
            cnt+=1
            br[k]=cnt
        else:
            cnt=0
    br=br[::-1]
    down.append(br)

for i in range(H):
    for j in range(W):
        gh=left[i][j]+right[i][j]+up[j][i]+down[j][i]-3
        ans=max(gh,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[0]*W for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '#':
            for k in range(cur, j):
                horiz[i][k] = j-cur
            cur = j+1
    for k in range(cur, W):
        horiz[i][k] = W-cur

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiz[r][c])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

Submission status: Time Limit Exceeded

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

tate=[[-1 for _ in range(w)] for _ in range(h)]
yoko=[[-1 for _ in range(w)] for _ in range(h)]

def search(i,j):
    ansij=1

    if(yoko[i][j] == -1):
        xl=j
        while(0<xl and s[i][xl-1]=='.'):
            ansij+=1
            xl-=1
        xr=j
        while(xr<w-1 and s[i][xr+1]=='.'):
            ansij+=1
            xr+=1

        for k in range(xl,xr+1):
            yoko[i][k]=xr-xl
    else:
        ansij+=yoko[i][j]

    if(tate[i][j] == -1):
        yu=i
        while(0<yu and s[yu-1][j]=='.'):
            ansij+=1
            yu-=1
        yd=i
        while(yd<h-1 and s[yd+1][j]=='.'):
            ansij+=1
            yd+=1

        for k in range(yu,yd+1):
            tate[k][j]=yd-yu
    else:
        ansij+=tate[i][j]

    return ansij

ans=0
for i in range(h):
    for j in range(w):
        if(s[i][j]=='.'):
            ansij=search(i, j)
            if(ans<ansij):
#                print(i,j,ansij)
                ans=ansij

print(ans)

Submission status: Time Limit Exceeded

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

S_l = [[0] * w for _ in range(h)]
S_r = [[0] * w for _ in range(h)]
S_u = [[0] * w for _ in range(h)]
S_d = [[0] * w for _ in range(h)]

for i in range(h):
    cnt = 0
    for j in range(w):
        if S[i][j] == '.':
            if cnt == 0:
                S_l[i][j] = 1
                cnt = 1
            else:
                S_l[i][j] = S_l[i][j-1] + 1
        else:
            cnt = 0
            S_l[i][j] = 0

for i in range(h):
    cnt = 0
    for j in reversed(range(w)):
        if S[i][j] == '.':
            if cnt == 0:
                S_r[i][j] = 1
                cnt = 1
            else:
                S_r[i][j] = S_r[i][j+1] + 1
        else:
            cnt = 0
            S_r[i][j] = 0

for j in range(w):
    cnt = 0
    for i in range(h):
        if S[i][j] == '.':
            if cnt == 0:
                S_u[i][j] = 1
                cnt = 1
            else:
                S_u[i][j] = S_u[i-1][j] + 1
        else:
            cnt = 0
            S_u[i][j] = 0

ans = 0

for j in range(w):
    cnt = 0
    for i in reversed(range(h)):
        if S[i][j] == '.':
            if cnt == 0:
                S_d[i][j] = 1
                cnt = 1
            else:
                S_d[i][j] = S_d[i+1][j] + 1
        else:
            cnt = 0
            S_d[i][j] = 0
        ans = max(ans, S_l[i][j] + S_r[i][j] + S_u[i][j] + S_d[i][j] - 3)

print(ans)

Submission status: Time Limit Exceeded

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


def search(i,j):
    ansij=1
    y=i
    x=j
    while(0<x and s[y][x-1]=='.'):
        ansij+=1
        x-=1
    y=i
    x=j
    while(x<w-1 and s[y][x+1]=='.'):
        ansij+=1
        x+=1
    y=i
    x=j
    while(0<y and s[y-1][x]=='.'):
        ansij+=1
        y-=1
    y=i
    x=j
    while(y<h-1 and s[y+1][x]=='.'):
        ansij+=1
        y+=1
    return ansij


ans=0
for i in range(h):
    for j in range(w):
        if(s[i][j]=='.'):
            ansij=search(i, j)
            if(ans<ansij):
#                print(i,j,ansij)
                ans=ansij

print(ans)