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

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	h,w=map(int,input().split())
	S=[input().rstrip().decode('utf-8') for _ in range(h)]
	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)]
	
	for i in range(h):
		for j in range(w):
			if j==0:
				if S[i][j]==".":
					L[i][j]=1
			else:
				if S[i][j] == ".":
					L[i][j]=L[i][j-1]+1
	
	for i in reversed(range(h)):
		for j in reversed(range(w)):
			if j==w-1:
				if S[i][j]==".":
					R[i][j]=1
			else:
				if S[i][j] == ".":
					R[i][j]=R[i][j+1]+1
	
	for j in range(w):
		for i in range(h):
			if i==0:
				if S[i][j]==".":
					U[i][j]=1
			else:
				if S[i][j] == ".":
					U[i][j]=U[i-1][j]+1
	
	for j in reversed(range(w)):
		for i in reversed(range(h)):
			if i==h-1:
				if S[i][j]==".":
					D[i][j]=1
			else:
				if 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)
	
	
	
	
	
	
	
	
	
	
	



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = [int(i) for i in input().split()]
s = [input() for _ in range(h)]

a = np.zeros((h, w), dtype=np.int64)
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for i in range(h):
    k = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in range(h):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
for j in range(w):
    k = 0
    for i in reversed(range(h)):
        if s[i][j] == ".":
            k += 1
        else:
            k = 0
        a[i][j] += k
a = np.where(a == 0, 0, a-3)
print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
lists1=[0]*h
import sys
input=sys.stdin.readline
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)
#今度は横の方向について調べる
judgelist2=[]
for j in  range(w):
    count=0
    addlist=[0]*w
    sublist=[]
    for k in range(h):
        some=lists1[k][j]
        if some=="#" and count==0:
            sublist.append(0)
            
            count=0
        elif some=="#" and count>=1:
          sublist.append(count)
          sublist.append(0)
          count=0
          
        if some==".":
            count+=1
            if k==h-1:
                sublist.append(count)
    judgelist2.append(sublist)

reallist2=[[] for _ in range(w)]
for i in range(w):
  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
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())
lists1=[0]*h
import sys
input=sys.stdin.readline
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:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = ['#' * (W + 2)]
    for _ in range(H):
        s = '#' + sys.stdin.readline().rstrip() + '#'
        grid.append(s)
    grid.append('#' * (W + 2))

    l, r, u, d = [[[0 for _ in range(W+2)] for _ in range(H+2)] for _ in range(4)]
    for i in range(1, H+1):
        for j in range(1, W+1):
            l[i][j] = l[i][j-1] + 1 if grid[i][j] == '.' else 0
            r[i][-j-1] = r[i][-j-1+1] + 1 if grid[i][-j-1] == '.' else 0
            u[i][j] = u[i-1][j] + 1 if grid[i][j] == '.' else 0
            d[-i-1][j] = d[-i-1+1][j] + 1 if grid[-i-1][j] == '.' else 0

    lighted_squares = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if grid[h][w] == 'w':
                lighted_squares.append(0)
            else:
                lighted_squares.append(l[h][w] + r[h][w] + u[h][w] + d[h][w] - 3)

    ans = max(lighted_squares)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = ['#' * (W + 2)]
    for _ in range(H):
        # s = f'#{sys.stdin.readline().rstrip()}#'
        s = '#' + sys.stdin.readline().rstrip() + '#'
        grid.append(s)
    grid.append('#' * (W + 2))

    lighted_squares = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if grid[h][w] == '#':
                lighted_squares.append(0)
            else:
                count = 1
                for j in range(w-1, -1, -1):
                    if grid[h][j] == '.':
                        count += 1
                        continue
                    else:
                        break
                for j in range(w+1, W+2):
                    if grid[h][j] == '.':
                        count += 1
                        continue
                    else:
                        break
                for i in range(h-1, -1, -1):
                    if grid[i][w] == '.':
                        count += 1
                        continue
                    else:
                        break
                for i in range(h+1, H+2):
                    if grid[i][w] == '.':
                        count += 1
                        continue
                    else:
                        break
                lighted_squares.append(count)
    
    print(max(lighted_squares))




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

L=[[0]*W for i in range(H)]
R=[[0]*W for i in range(H)]
U=[[0]*W for i in range(H)]
D=[[0]*W for i in range(H)]

cntr=0
cntd=[0]*W
for i in range(H):
    temp=input()
    for j in range(W):
        if temp[j]!="#":
            if j==0:
                L[i][j]=1
            else:
                L[i][j]=L[i][j-1]+1
            cntr+=1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j]=U[i-1][j]+1
            cntd[j]+=1
        else:
            for k in range(cntr):
                R[i][j-1-k]=k+1
            cntr=0
            for k in range(cntd[j]):
                D[i-1-k][j]=k+1
            cntd[j]=0
    if cntr!=0:
        for k in range(cntr):
            R[i][W - 1 - k] = k + 1
        cntr=0
for i in range(W):
    if cntd[i]!=0:
        for k in range(cntd[i]):
            D[H-1-k][i]=k+1

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

Submission status: Time Limit Exceeded

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

s=[[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    temp=input()

    for j in range(W):
        if temp[j]!="#":
            cnt+=1
        else:
            if j==0:
                continue
            else:
                for k in range(cnt):
                    s[i][j-(1+k)]=cnt
                cnt=0
    if cnt!=0:
        for k in range(cnt):
            s[i][W-1 - k] = cnt
        cnt = 0

ans=[]
mx=0
for i in range(W):
    cnt=0
    for j in range(H):
        if s[j][i]!=0:
            cnt+=1
            mx=max(mx,s[j][i])
        else:
            if j==0:
                continue
            else:
                ans.append(mx+cnt-1)
                cnt=0
                mx=0
    if cnt!=0:
        ans.append(mx+cnt-1)
        mx=0
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = 10**18

def input():
    return sys.stdin.readline().rstrip()

def main():
    H, W = map(int, input().split())
    S = [list(input()) for i in range(H)]
    ans = 0
    memo_y = [[-INF]*W for i in range(H)]
    memo_x = [[-INF]*W for i in range(H)]
    for y in range(H):
        for x in range(W):
            c = 0
            if S[y][x] == '.':
                c += 1
                c_x = 0
                c_y = 0
                tmp_x = [x]
                tmp_y = [y]
                if memo_x[y][x] == -INF:
                    for i in range(1, x+1):
                        if S[y][x-i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in range(x+1, W):
                        if S[y][i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in tmp_x:
                        memo_x[y][i] = c_x
                else:
                    c_x += memo_x[y][x]
                if memo_y[y][x] == -INF:
                    for i in range(1, y+1):
                        if S[y-i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in range(y+1, H):
                        if S[i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in tmp_y:
                        memo_y[i][x] = c_y
                else:
                    c_y += memo_y[y][x]
                c += c_x + c_y
            ans = max(ans, c)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def dfs(graph, start):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    W = len(graph)
    H = len(graph[0])
    ans = 0

    for x in range(len(graph)):
        for y in range(len(graph[x])):
            if graph[x][y] == '#':
                continue

            val = 1
            path = []
            stack = [(x, y, options)]
            # print(x, y)

            while stack != []:
                v = stack.pop()

                if v not in path:
                    path.append(v)

                for op in v[2]:
                    n = (v[0] + op[0], v[1] + op[1], [op])

                    if n[0] >= 0 and n[0] < W and n[1] >= 0 and n[1] < H:
                        f = graph[n[0]][n[1]]
                        if n not in path and f == '.':
                            stack.append(n)
                            val += 1

            ans = max(ans, val)

    return ans


def main():
    H, W = map(int, input().split())
    S = [None] * H

    for i in range(H):
        S[i] = list(input())

    print(dfs(S, S[0][0]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    S=[list(input()) for i in range(H)]
    ans=0
    memo_y = [[-float('inf')]*W for i in range(H)]
    memo_x = [[-float('inf')]*W for i in range(H)]
    for y in range(H):
        for x in range(W):
            if S[y][x] == '.':
                c_x = 0
                c_y = 0
                tmp_x = [x]
                tmp_y = [y]
                if memo_x[y][x] == -float('inf'):
                    for i in range(1, x+1):
                        if S[y][x-i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in range(x+1, W):
                        if S[y][i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in tmp_x:
                        memo_x[y][i] = c_x
                else:
                    c_x += memo_x[y][x]
                if memo_y[y][x] == -float('inf'):
                    for i in range(1, y+1):
                        if S[y-i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in range(y+1, H):
                        if S[i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in tmp_y:
                        memo_y[i][x] = c_y
                else:
                    c_y += memo_y[y][x]
                    
    for y in range(H):
        for x in range(W):
            c = 0
            c += 1 + memo_x[y][x] + memo_y[y][x]
            ans=max(ans,c)
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    S=[list(input()) for i in range(H)]
    ans=0
    memo_y = [[-float('inf')]*W for i in range(H)]
    memo_x = [[-float('inf')]*W for i in range(H)]
    for y in range(H):
        for x in range(W):
            c = 0
            if S[y][x]=='.':
                c += 1
                c_x = 0
                c_y = 0
                tmp_x = [x]
                tmp_y = [y]
                if memo_x[y][x] == -float('inf'):
                    for i in range(1, x+1):
                        if S[y][x-i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in range(x+1, W):
                        if S[y][i] == '.':
                            c_x += 1
                            tmp_x.append(i)
                        else:
                            break
                    for i in tmp_x:
                        memo_x[y][i] = c_x
                else:
                    c_x += memo_x[y][x]
                if memo_y[y][x] == -float('inf'):
                    for i in range(1, y+1):
                        if S[y-i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in range(y+1, H):
                        if S[i][x] == '.':
                            c_y += 1
                            tmp_y.append(i)
                        else:
                            break
                    for i in tmp_y:
                        memo_y[i][x] = c_y
                else:
                    c_y += memo_y[y][x]
                c += c_x + c_y
            ans=max(ans,c)
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
S = list()
for n in range(H):
    S.append(input())
res = 0
for n in range(H):
    for m in range(W):
        if S[n][m] == ".":
            x = -1
            c = 0
            for k in range(n):
                if S[k][m] == "#":
                    c = 0
                else:
                    c += 1
            x += c
            for k in range(n, H):
                if S[k][m] == "#":
                    break
                else:
                    x += 1
            c = 0
            for l in range(m):
                if S[n][l] == "#":
                    c = 0
                else:
                    c += 1
            x += c
            for l in range(m, W):
                if S[n][l] == "#":
                    break
                else:
                    x += 1
            res = max(res, x)
print(res)

Submission status: Time Limit Exceeded

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

import numpy as np
a = np.zeros([H,W],dtype=int)
b = np.zeros([H,W],dtype=int)
c = np.zeros([H,W],dtype=int)
d = np.zeros([H,W],dtype=int)

for h in range(H):
  for w in range(W):
    if S[h][w]=="#":
      a[h,w]=0
    elif w == 0:
      a[h,w]=1
    else: 
      a[h,w] = a[h,w-1] + 1

for h in range(H):
  for w in range(W):
    w = W-w-1
    if S[h][w]=="#":
      b[h,w]=0
    elif w == W-1:
      b[h,w]=1
    else: 
      b[h,w] = b[h,w+1] + 1
      
for w in range(W):
  for h in range(H):
    if S[h][w]=="#":
      c[h,w]=0
    elif h == 0:
      c[h,w]=1
    else: 
      c[h,w] = c[h-1,w] + 1
      
for w in range(W):
  for h in range(H):
    h = H-h-1
    
    if S[h][w]=="#":
      d[h,w]=0
    elif h == H-1:
      d[h,w]=1
    else: 
      d[h,w] = d[h+1,w] + 1
      
print((a+b+c+d).max()-3)

Submission status: Time Limit Exceeded

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

S = []
Score = []
for i in range(H):
    S.append(input())

Score = [[[0]*4 for i in range(W)] for j in range(H)]

#print(S)
max_cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#" and S[i][W-1-j] == "#" and S[H-1-i][j] == "#":
            continue
        elif S[i][W-1-j] == "#" and S[H-1-i][j] == "#":
            ##左
            Score[i][j][0] = 1 if j == 0 else Score[i][j-1][0] + 1
            #上
            Score[i][j][2] = 1 if i == 0 else Score[i-1][j][2] +1
        elif  S[i][j] == "#" and S[H-1-i][j] == "#":
            #右
            Score[i][W-1-j][1] = 1 if j == 0 else Score[i][W-j][1] + 1
        elif S[i][W-1-j] == "#" and  S[i][j] == "#":
            #下
            Score[H-1-i][j][3] = 1 if i == 0 else Score[H-i][j][3] +1

        elif S[i][W-1-j] == "#":
            ##左
            Score[i][j][0] = 1 if j == 0 else Score[i][j-1][0] + 1
            #上
            Score[i][j][2] = 1 if i == 0 else Score[i-1][j][2] +1
            #下
            Score[H-1-i][j][3] = 1 if i == 0 else Score[H-i][j][3] +1

        elif S[H-1-i][j] == "#":
             ##左
            Score[i][j][0] = 1 if j == 0 else Score[i][j-1][0] + 1
            #右
            Score[i][W-1-j][1] = 1 if j == 0 else Score[i][W-j][1] + 1
            #上
            Score[i][j][2] = 1 if i == 0 else Score[i-1][j][2] +1


        elif S[i][j] == "#":
            #右
            Score[i][W-1-j][1] = 1 if j == 0 else Score[i][W-j][1] + 1
            #下
            Score[H-1-i][j][3] = 1 if i == 0 else Score[H-i][j][3] +1

        else:
            ##左
            Score[i][j][0] = 1 if j == 0 else Score[i][j-1][0] + 1
            #右
            Score[i][W-1-j][1] = 1 if j == 0 else Score[i][W-j][1] + 1
            #上
            Score[i][j][2] = 1 if i == 0 else Score[i-1][j][2] +1
            #下
            Score[H-1-i][j][3] = 1 if i == 0 else Score[H-i][j][3] +1

max_cnt = 0
for i in range(H):
    for j in range(W):
        cnt = max(sum(Score[i][j]) - 3,1)
        if cnt > max_cnt:
            max_cnt = cnt
print(max_cnt)
#print(Score)
#for i in Score: print(i)

Submission status: Time Limit Exceeded

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

r_lens = []
for s in S:
  counts = [len(block) for block in s.split("#")]
  
  r_len = []
  for c in counts:
    r_len+=[c]*c
    r_len+=[0]
  r_len.pop()
  r_lens.append(r_len)
r_lens = np.array(r_lens)

S2 = [""]*W
for h in range(H):
  for w in range(W):
    S2[w] += S[h][w]
    
c_lens = []
for s in S2:
  counts = [len(block) for block in s.split("#")]
  
  c_len = []
  for c in counts:
    c_len+=[c]*c
    c_len+=[0]
  c_len.pop()
  c_lens.append(c_len)
c_lens = np.array(c_lens)

print((r_lens+c_lens.T-1).max())

Submission status: Time Limit Exceeded

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

import numpy as np
mat = np.full([H,W,2], -1)
  
def calc_c(S,r,c):
  count = 0
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
  
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      mat[r,c1,1] = count
    else: break
  return count

def calc_r(S,r,c):
  count = 0
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      mat[r1,c,0]=count
    else: break
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
      
    rc, cc = mat[r,c]
    if rc == -1:
    	rc = calc_r(S,r,c)
    if cc == -1:
    	cc = calc_c(S,r,c)
        
    ans = max(rc+cc+1, ans) 

print(int(ans))

Submission status: Time Limit Exceeded

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

import numpy as np
mat = np.full([H,W,2], -1)
  
def calc_c(S,r,c):
  count = 0
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
      
  mat[r,c]=count
  return count

def calc_r(S,r,c):
  count = 0
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  mat[r,c]=count
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
      
    rc, cc = mat[r,c]
    if rc == -1:
    	rc = calc_r(S,r,c)
    if cc == -1:
    	cc = calc_c(S,r,c)
        
    ans = max(rc+cc+1, ans) 

print(ans)

Submission status: Time Limit Exceeded

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

def calc_len(S,r,c):
  count = 1
  
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
    count = calc_len(S,r,c)
    ans = max(count, ans) 

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(2):
    C = [A, B][i]
    for r, row in enumerate(board):
        cnt, frm = 0, -1
        for c, j in enumerate(row):
            if j == '#':
                for k in range(frm + 1, c):
                    C[r][k] = cnt
                cnt = 0
                frm = c
            else:
                cnt += 1
        else:
            for k in range(frm + 1, W):
                C[r][k] = cnt
    H, W = W, H
    board = [list(row) for row in list(zip(*board))]

res = 0
for i in range(H):
    for j in range(W):
        res = max(res, A[i][j] + B[j][i] - 1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A=[]
B=[]
count=0
pivot=0
for i in range(H):
    S=input()
    S+='#'
    A.append(S)

S='#'*(W+1)
A.append(S)



for i in range(H):
    C=[0]*W
    B.append(C)

for i in range(H):
    for j in range(W):
        if A[i][j]=='.' and count==0:
            pivot=j
            count+=1
        elif A[i][j]=='.':
            count+=1
        if A[i][j]=='.' and A[i][j+1]=='#':
            for k in range(pivot,j+1):
                B[i][k]+=count
            count=0


A=[list(i) for i in list(zip(*A))]
B=[list(i) for i in list(zip(*B))]


for i in range(W):
    for j in range(H):
        if A[i][j]=='.' and count==0:
            pivot=j
            count+=1
        elif A[i][j]=='.':
            count+=1
        if A[i][j]=='.' and A[i][j+1]=='#':
            for k in range(pivot,j+1):
                B[i][k]+=count
            count=0
max=0
for i in range(W):
    for j in range(H):
        if B[i][j]>=max:
            max=B[i][j]

print(max-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A=[]
B=[]
count=0
pivot=0
for i in range(H):
    S=input()
    S+='#'
    A.append(S)

S='#'*(W+1)
A.append(S)



for i in range(H):
    C=[0]*W
    B.append(C)

for i in range(H):
    for j in range(W):
        if A[i][j]=='.' and count==0:
            pivot=j
            count+=1
        elif A[i][j]=='.':
            count+=1
        if A[i][j]=='.' and A[i][j+1]=='#':
            for k in range(pivot,j+1):
                B[i][k]+=count
            count=0





A=[list(i) for i in list(zip(*A))]
B=[list(i) for i in list(zip(*B))]




for i in range(W):
    for j in range(H):
        if A[i][j]=='.' and count==0:
            pivot=j
            count+=1
        elif A[i][j]=='.':
            count+=1
        if A[i][j]=='.' and A[i][j+1]=='#':
            for k in range(pivot,j+1):
                B[i][k]+=count
            count=0
max=0
for i in range(W):
    for j in range(H):
        if B[i][j]>=max:
            max=B[i][j]

print(max-1)