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:
from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = []
  for i in range(h):
    tmp = input()
    maze.append(tmp)
  l = [[0]*w for _ in range(h)]
  r = [[0]*w for _ in range(h)]
  u = [[0]*w for _ in range(h)]
  d = [[0]*w for _ in range(h)]
  cur = 0
  for i in range(h):
    cur = 0
    for j in range(w):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      l[i][j] = cur
  for i in range(h):
    cur = 0
    for j in range(w-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      r[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      d[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      u[i][j] = cur      
  ans = 0
  for i in range(h):
    for j in range(w):
      now = l[i][j]+r[i][j]+u[i][j]+d[i][j] -3
      ans = max(now,ans)
  print(ans)
solve()

Submission status: Time Limit Exceeded

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

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

for i in range(H):
    for j in range(W):
        if S[i][j] == "." and j > 0:
            L[i][j] = L[i][j-1]+1
        elif S[i][j] == ".":
            L[i][j] = 1
    for j in range(W-1, 0, -1):
        if L[i][j-1] > 0:
            L[i][j-1] = max(L[i][j-1], L[i][j])
            
L2 = [[0]*W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == "." and i > 0:
            L2[i][j] = L2[i-1][j] + 1
        elif S[i][j] == ".":
            L2[i][j] = 1
    for i in range(H-1, 0, -1):
        if L2[i-1][j] > 0:
            L2[i-1][j] = max(L2[i-1][j], L2[i][j])
            
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j]+L2[i][j]-1)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Lamp

#import numpy as np

H, W = map(int, input().split())
#S = np.array([list(input()) for _ in range(H)])
S = [list(input()) for _ in range(H)]

def trans(M):
    output_list = []
    for col in range(len(M[0])):
        tmp = []
        for row in range(len(M)):
            tmp.append(M[row][col])
        output_list.append(tmp)
    return output_list
            
def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

#n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
ans = 0
tmp1 = n_matrix_lighten(S)
tmp2 = trans(n_matrix_lighten(trans(S)))

for row in range(H):
    for col in range(W):
        ans = max(ans, tmp1[row][col] + tmp2[row][col] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Lamp

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)])

def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
print(np.amax(n_lighten))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
field = [[0]*w for _ in range(h)]


for i in range(h):
    obs = []
    for x in range(w):
        if s[i][x] == '#':
            obs.append(x)
    if not obs:
        for x in range(w):
            field[i][x] += w
    else:
        for j in range(obs[0]):
            field[i][j] += obs[0]
        for x in range(len(obs)-1):
            for j in range(obs[x]+1, obs[x+1]):
                field[i][j] += obs[x+1]-obs[x]-1
        for j in range(obs[-1]+1, w):
            field[i][j] += w-obs[-1]-1


for j in range(w):
    obs = []
    for y in range(h):
        if s[y][j] == '#':
            obs.append(y)
    if not obs:
        for y in range(h):
            field[y][j] += h
    else:
        for i in range(obs[0]):
            field[i][j] += obs[0]
        for y in range(len(obs)-1):
            for i in range(obs[y]+1, obs[y+1]):
                field[i][j] += obs[y+1]-obs[y]-1
        for i in range(obs[-1]+1, h):
            field[i][j] += h-obs[-1]-1

# print(field)
print(max([max(field[i]) for i in range(h)])-1)

Submission status: Time Limit Exceeded

Solution code:
def light(s,i,j):
    res=1
    k=0
    while i-k-1>=0 and not s[i-k-1][j]:
        k+=1
    res+=k
    k=0
    while i+k+1<=H-1 and not s[i+k+1][j]:
        k+=1
    res+=k
    k=0
    while j-k-1>=0 and not s[i][j-k-1]:
        k+=1
    res+=k
    k=0
    while j+k+1<=W-1 and not s[i][j+k+1]:
        k+=1
    res+=k
    return res

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='#')
    s.append(si)

ans=0
for i in range(H):
    for j in range(W):
        if not s[i][j]:
            ans=max(ans,light(s,i,j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='.')
    s.append(si)

# 左に照らした場合 行ごとに見てゆく
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and s[i][j]:
            L[i][j]=1
        elif s[i][j]:
            L[i][j]=L[i][j-1]+1

# 右に照らした場合 行ごとに見てゆく
R=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in reversed(range(W)):
        if j==W-1 and s[i][j]:
            R[i][j]=1
        elif s[i][j]:
            R[i][j]=R[i][j+1]+1

# 上に照らした場合 列ごとに見てゆく
U=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in range(H):
        if i==0 and s[i][j]:
            U[i][j]=1
        elif s[i][j]:
            U[i][j]=U[i-1][j]+1

# 下に照らした場合 列ごとに見てゆく
D=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in reversed(range(H)):
        if i==H-1 and s[i][j]:
            D[i][j]=1
        elif s[i][j]:
            D[i][j]=D[i+1][j]+1

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)

Submission status: Time Limit Exceeded

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

# 上下左右に余分に1マスとっとく
square = [[[0, 0, 0, 0] for _ in range(W + 2)] for _ in range(H + 2)]
for row in range(H + 2):
	for column in range(W + 2):
		if row == 0 or row == H + 1 or column == 0 or column == W + 1:
			square[row][column] = [-1, -1, -1, -1]

for row in range(H):
	S = list(map(str, input()))
	for column in range(W):
		if S[column] == "#":
			# 下駄をはかせるの忘れない
			square[row + 1][column + 1] = [-1, -1, -1, -1]
			

for row in range(1, H + 1):
	for column in range(1, W + 1):
		if square[row][column][0] == -1: continue
		square[row][column][0] = square[row][column - 1][0] + 1
		
for row in range(1, H + 1):
	for column in reversed(range(1, W + 1)):
		if square[row][column][0] == -1: continue
		square[row][column][1] = square[row][column + 1][1] + 1
		
for column in range(1, W + 1):
	for row in range(1, H + 1):
		if square[row][column][0] == -1: continue
		square[row][column][2] = square[row - 1][column][2] + 1
		
for column in range(1, W + 1):
	for row in reversed(range(1, H + 1)):
		if square[row][column][0] == -1: continue
		square[row][column][3] = square[row + 1][column][3] + 1

ret = 0
		
for row in range(1, H + 1):
	for column in range(1, W + 1):
		# print(row, column, 1 + sum(square[row][column]))
		ret = max(ret, 1 + sum(square[row][column]))
		
print(ret)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
h, w = map(int,input().split())
s = np.array(list(list((ord(x) - 35) // 11 for x in list(input())) for _ in range(h)))
u = np.zeros((h+1, w), dtype = int)
d = np.zeros((h+1, w), dtype = int)
l = np.zeros((h, w+1), dtype = int)
r = np.zeros((h, w+1), dtype = int)
ans = np.zeros((h, w), dtype = int)
for i in range(1, h+1):
    x = h + 1 - i
    for j in range(w):
        if s[i - 1, j] == 1:
            u[i, j] = u[i - 1, j] + 1
        if s[x - 1 , j] == 1:
            d[x - 1, j] = d[x, j] + 1
for j in range(1, w+1):
    y = w + 1 - j
    for i in range(h):
        if s[i, j - 1] == 1:
            l[i, j] = l[i, j - 1] + 1
        if s[i, y - 1] == 1:
            r[i, y - 1] = r[i, y] + 1

for i in range(h):
    for j in range(w):
        ans[i, j] = u[i + 1, j] + d[i, j] + l[i, j + 1] + r[i, j] -3
print(np.max(ans))

Submission status: Time Limit Exceeded

Solution code:
def light(s,i,j):
    res=1
    k=0
    while i-k-1>=0 and not s[i-k-1][j]:
        k+=1
    res+=k
    k=0
    while i+k+1<=H-1 and not s[i+k+1][j]:
        k+=1
    res+=k
    k=0
    while j-k-1>=0 and not s[i][j-k-1]:
        k+=1
    res+=k
    k=0
    while j+k+1<=W-1 and not s[i][j+k+1]:
        k+=1
    res+=k
    return res

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='#')
    s.append(si)

ans=0
for i in range(H):
    for j in range(W):
        if not s[i][j]:
            ans=max(ans,light(s,i,j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

  
    
uselists1=[0]*h
judgelist=[]
for j in  range(h):
    some=lists1[j]
    count=0
    addlist=[0]*w
    sublist=[]
    for k in range(w):
        if some[k]=="#" and count==0:
            sublist.append(0)
            
            count=0
        elif some[k]=="#" and count>=1:
          sublist.append(count)
          sublist.append(0)
          count=0
          
        if some[k]==".":
            count+=1
            if k==w-1:
                sublist.append(count)
    judgelist.append(sublist)

reallist1=[[] for _ in range(h)]
for i in range(h):
  use=judgelist[i]
  for j in range(len(use)):
    if use[j]!=0:
    	for k in range(use[j]):
    		reallist1[i].append(use[j])
    else:
      reallist1[i].append(0)


lists2=[0]*w
for i in range(w):
  s=[0]*h
  for j in range(h):
    s[j]=lists1[j][i]
  lists2[i]=s


h,w=w,h
judgelist2=[]
for j in  range(h):
    some=lists2[j]
    count=0
    addlist=[0]*w
    sublist=[]
    for k in range(w):
        if some[k]=="#" and count==0:
            sublist.append(0)
            
            count=0
        elif some[k]=="#" and count>=1:
          sublist.append(count)
          sublist.append(0)
          count=0
          
        if some[k]==".":
            count+=1
            if k==w-1:
                sublist.append(count)
    judgelist2.append(sublist)
   
reallist2=[[] for _ in range(h)]
for i in range(h):
  use=judgelist2[i]
  for j in range(len(use)):
    if use[j]!=0:
    	for k in range(use[j]):
    		reallist2[i].append(use[j])
    else:
      reallist2[i].append(0)
               

answer=0
h,w=w,h
for i in range(h):
  for j in range(w):
    if reallist1[i][j]==0 or reallist2[j][i]==0:
      continue
    else:
      answer=max(answer,reallist1[i][j]+reallist2[j][i]-1)
      
print(answer)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
yoko=[[0]*w for i in range(h)]
for i in range(h):
	j=0
	while j <w:
		if data[i][j]=='#':
			j+=1
		else:
			start=j
			while j<w-1:
				j+=1
				if data[i][j]=='#':
					for k in range(start,j):
						yoko[i][k]=j-start-1
					j+=1
					break
			else:
				j+=1
				for k in range(start,j):
					yoko[i][k]=j-start-1
				j+=1
# for i in range(h):
# 	print(yoko[i])

for j in range(w):
	i=0
	while i <h:
		if data[i][j]=='#':
			i+=1
		else:
			start=i
			while i<h-1:
				i+=1
				if data[i][j]=='#':
					for k in range(start,i):
						yoko[k][j]+=i-start-1
					i+=1
					break
			else:
				i+=1
				for k in range(start,i):
					yoko[k][j]+=i-start-1
				i+=1

# print(yoko)
for i in range(h):
	# print(yoko[i])
	yoko[i]=max(yoko[i])
print(max(yoko)+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
h, w = map(int,input().split())
s = list(input() for _ in range(h))
s_t = [[0] * h for _ in range(w)]
ans = [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        s_t[j][i] = s[i][j]
s_count = []
s_t_count = []
temp = []
for i in range(h):
    for k, v in itertools.groupby(s[i]):
        if k == ".":
            temp.append(len(list(v)))
        else:
            temp.append((-1) * len(list(v)))
    s_count.append(temp)
    temp = []
for i in range(w):
    for k, v in itertools.groupby(s_t[i]):
        if k == ".":
            temp.append(len(list(v)))
        else:
            temp.append((-1) * len(list(v)))
    s_t_count.append(temp)
    temp = []

ans_1 = [[0] * w for _ in range(h)]
ans_2 = [[0] * h for _ in range(w)]
ans_2_t = [[0] * w for _ in range(h)]
t = 0
for i in range(h):
    for j in s_count[i]:
        if j > 0:
            ans_1[i][t:t+j] = [j for _ in range(j)]
            t += j
        else:
            t -= j
    t = 0
for i in range(w):
    for j in s_t_count[i]:
        if j > 0:
            ans_2[i][t:t+j] = [j for _ in range(j)]
            t += j
        else:
            t -= j
    t = 0
for i in range(h):
    for j in range(w):
        ans[i][j] = ans_1[i][j] + ans_2[j][i]

print(max(itertools.chain.from_iterable(ans))-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

def find(LI,i,j,p):
    data=[(0,1),(0,-1),(1,0),(-1,0)]
    if not (0<=i<h and 0<=j<w):
        return -1

    if s[i][j]=="#":
        LI[i][j] = -1
        return LI[i][j]

    if LI[i][j]!=-2:
        return LI[i][j]
    else:
        LI[i][j]= find(LI, i+data[p][0], j+data[p][1], p)+1
        return LI[i][j]
    

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
R=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
F=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        find(R,i,j,0)
        find(L,i,j,1)
        find(F,i,j,2)
        find(B,i,j,3)
        if s[i][j]!="#":
            ans = max(ans, sum((R[i][j], L[i][j], F[i][j], B[i][j]))+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import groupby
h, w = map(int,input().split())
s = list(input() for _ in range(h))
s_t = [[0] * (h) for j in range(w)]
for i in range(h):
    for j in range(w):
        s_t[j][i] = s[i][j]
s_count = []
s_t_count = []
temp = []
for i in range(h):
    for k, v in groupby(s[i]):
        if k == ".":
            temp.append(len(list(v)))
        else:
            temp.append((-1) * len(list(v)))
    s_count.append(temp)
    temp = []
for i in range(w):
    for k, v in groupby(s_t[i]):
        if k == ".":
            temp.append(len(list(v)))
        else:
            temp.append((-1) * len(list(v)))
    s_t_count.append(temp)
    temp = []

ans = np.array([[0] * w for _ in range(h)])
t = 0
for i in range(h):
    for j in s_count[i]:
        if j > 0:
            ans[i, t:t+j] += j
            t += j
        else:
            t -= j
    t = 0
for i in range(w):
    for j in s_t_count[i]:
        if j > 0:
            ans[t:t+j, i] += j
            t += j
        else:
            t -= j
    t = 0
print(np.max(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

def find(LI,i,j,p):
    data=[(0,1),(0,-1),(1,0),(-1,0)]
    if not (0<=i<h and 0<=j<w):
        return -1
    if s[i][j]=="#":
        return -1
    if LI[i][j]!=-2:
        return LI[i][j]
    else:
        LI[i][j]= find(LI, i+data[p][0], j+data[p][1], p)+1
        return LI[i][j]
    

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
R=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
F=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        find(R,i,j,0)
        find(L,i,j,1)
        find(F,i,j,2)
        find(B,i,j,3)
        if s[i][j]!="#":
            ans = max(ans, sum((R[i][j], L[i][j], F[i][j], B[i][j]))+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    s = [[1 if t == "#" else 0 for t in l] for l in s]
    s = np.array(s, dtype=np.int64)
    data = np.zeros((h, w, 4), dtype=np.int64)


    for i in range(h):
        for j in range(w):
            if s[i][j] == 0:
                data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1
            if s[i][w-j-1] == 0:
                data[i][w-j-1][1] = (data[i][w-j][1] if j > 0 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == 0:
                data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1
            if s[h-i-1][j] == 0:
                data[h-i-1][j][3] = (data[h-i][j][3] if i > 0 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == 1:
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print("%d" % maxx)


    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    s = [[1 if t == "#" else 0 for t in l] for l in s]
    s = np.array(s)
    data = np.zeros((h, w, 4))

    for i in range(h):
        for j in range(w):
            if s[i][j] == 0:
                data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1
            if s[i][w-j-1] == 0:
                data[i][w-j-1][1] = (data[i][w-j][1] if j > 0 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == 0:
                data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1
            if s[h-i-1][j] == 0:
                data[h-i-1][j][3] = (data[h-i][j][3] if i > 0 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == 1:
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print("%d" % maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    data = [[[0, 0, 0, 0] for j in range(w)] for i in range(h)]
    # left = [[0 for j in range(w)] for i in range(h)]
    # right = copy.deepcopy(left)
    # up = copy.deepcopy(left)
    # down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] != "#":
                data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1
            if s[i][w-j-1] != "#":
                data[i][w-j-1][1] = (data[i][w-j][1] if j > 0 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] != "#":
                data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1
            if s[h-i-1][j] != "#":
                data[h-i-1][j][3] = (data[h-i][j][3] if i > 0 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    data = [[[0, 0, 0, 0] for j in range(w)] for i in range(h)]
    data = np.array(data)
    # left = [[0 for j in range(w)] for i in range(h)]
    # right = copy.deepcopy(left)
    # up = copy.deepcopy(left)
    # down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            # left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1
            data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1

    for i in range(h-1, -1, -1):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            # right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
            data[i][j][1] = (data[i][j+1][1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            # up[i][j] = (up[i-1][j] if i > 0 else 0) + 1
            data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1

    for j in range(w-1, -1, -1):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            # down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1
            data[i][j][3] = (data[i+1][j][3] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    data = [[[0, 0, 0, 0] for j in range(w)] for i in range(h)]
    # left = [[0 for j in range(w)] for i in range(h)]
    # right = copy.deepcopy(left)
    # up = copy.deepcopy(left)
    # down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            # left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1
            data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1

    for i in range(h-1, -1, -1):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            # right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
            data[i][j][1] = (data[i][j+1][1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            # up[i][j] = (up[i-1][j] if i > 0 else 0) + 1
            data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1

    for j in range(w-1, -1, -1):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            # down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1
            data[i][j][3] = (data[i+1][j][3] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    data = [[[0, 0, 0, 0] for j in range(w)] for i in range(h)]
    # left = [[0 for j in range(w)] for i in range(h)]
    # right = copy.deepcopy(left)
    # up = copy.deepcopy(left)
    # down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            # left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1
            data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1

    for i in range(h):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            # right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
            data[i][j][1] = (data[i][j+1][1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            # up[i][j] = (up[i-1][j] if i > 0 else 0) + 1
            data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1

    for j in range(w):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            # down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1
            data[i][j][3] = (data[i+1][j][3] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    left = [[0 for j in range(w)] for i in range(h)]
    right = copy.deepcopy(left)
    up = copy.deepcopy(left)
    down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1

    for i in range(h):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            up[i][j] = (up[i-1][j] if i > 0 else 0) + 1

    for j in range(w):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np
import copy

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    left = [[0 for j in range(w)] for i in range(h)]
    right = copy.deepcopy(left)
    up = copy.deepcopy(left)
    down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1

    for i in range(h):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            up[i][j] = (up[i-1][j] if i > 0 else 0) + 1

    for j in range(w):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

                


    return 0

if __name__ == '__main__':
    sys.exit(main())