Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w=mii()
arr=[["#"]*(w+2)]
for i in range(h):
    x=["#"]+list(ss())+["#"]
    arr.append(x)
arr.append(["#"]*(w+2))

ans=[[[0]*4 for j in range(w+2)] for i in range(h+2)]

for i in range(1,h+2):
    for j in range(1,w+2):
        if arr[i][j]=="#":
            ans[i][j][0]=0
            ans[i][j][1]=0
        else:
            ans[i][j][0]=ans[i][j-1][0]+1
            ans[i][j][1]=ans[i-1][j][1]+1


for i in list(reversed(range(1,h+2))):
    for j in list(reversed(range(1,w+2))):
        if arr[i][j]=="#":
            ans[i][j][2]=0
            ans[i][j][3]=0
        else:
            ans[i][j][2]=ans[i][j+1][2]+1
            ans[i][j][3]=ans[i+1][j][3]+1

chk=0

for i in range(1,h+2):
    for j in range(1,w+2):
        chk=max(chk,sum(ans[i][j])-3)

print(chk)

Submission status: Time Limit Exceeded

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

F = [input() 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 F[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        else:
            L[i][j] = L[i][j - 1] + 1 if j - 1 >= 0 else 1
            U[i][j] = U[i - 1][j] + 1 if i - 1 >= 0 else 1

        if F[i][-1 - j] == "#":
            R[i][-1 - j] = 0
        else:
            R[i][-1 - j] = R[i][-j] + 1 if j > 0 else 1

        if F[- 1 - i][j] == "#":
            D[- 1 - i][j] = 0
        else:
            D[- 1 - i][j] = D[-i][j] + 1 if i > 0 else 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())
l = [list(input()) for i in range(h)]

c = [[[-1]*2 for i in range(w)] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if c[i][j][0] == -1:
            n = 0
            while i+n < h:
                if l[i+n][j] == ".":
                    n += 1
                else:
                    break
            for k in range(n):
                c[i+k][j][0] = n
            
        if c[i][j][1] == -1:
            n = 0
            while j+n < w:
                if l[i][j+n] == ".":
                    n += 1
                else:
                    break
            for k in range(n):
                c[i][j+k][1] = n


        ans = max(ans,c[i][j][0]+c[i][j][1])
print(ans-1)

Submission status: Time Limit Exceeded

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

    c = [[[-1]*2 for i in range(w)] for i in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if c[i][j][0] == -1:
                n = 0
                while i+n < h:
                    if l[i+n][j] == ".":
                        n += 1
                    else:
                        break
                for k in range(n):
                    c[i+k][j][0] = n
                
            if c[i][j][1] == -1:
                n = 0
                while j+n < w:
                    if l[i][j+n] == ".":
                        n += 1
                    else:
                        break
                for k in range(n):
                    c[i][j+k][1] = n
    
    
            ans = max(ans,c[i][j][0]+c[i][j][1])
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    c = [[[-1]*2 for i in range(w)] for i in range(h)]

    for i in range(h):
        for j in range(w):
            if c[i][j][0] == -1:
                n = 0
                while i+n < h and l[i+n][j] == ".":
                    n += 1
                for k in range(n):
                    c[i+k][j][0] = n
                
            if c[i][j][1] == -1:
                n = 0
                while j+n < w and l[i][j+n] == ".":
                    c[i][j+n][1] = 1
                    n += 1
                for k in range(n):
                    c[i][j+k][1] = n


            
    ans = 0
    for i in range(h):
        for j in range(w):
            if l[i][j] == ".":
                ans = max(ans,c[i][j][0]+c[i][j][1])
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int,input().split())
    l = [list(input()) for i in range(h)]

    c = [[[-1]*2 for i in range(w)] for i in range(h)]

    def count(x,y):

        if c[x][y][0] == -1:
            n = 0
            while x+n < h and l[x+n][y] == ".":
                c[x+n][y][0] = 1
                n += 1
            c[x][y][0] = n
        elif c[x][y][0] == 1:
            c[x][y][0] = c[x-1][y][0]
            
        if c[x][y][1] == -1:
            n = 0
            while y+n < w and l[x][y+n] == ".":
                c[x][y+n][1] = 1
                n += 1
            c[x][y][1] = n
        elif c[x][y][1] == 1:
            c[x][y][1] = c[x][y-1][1]


        return c[x][y][0]+c[x][y][1]-1
    ans = 0
    for i in range(h):
        for j in range(w):
            if l[i][j] == ".":
                ans = max(ans,count(i,j))
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

c = [[[-1]*2 for i in range(w)] for i in range(h)]

def count(x,y):

    if c[x][y][0] == -1:
        n = 0
        while x+n < h and l[x+n][y] == ".":
            n += 1
        for i in range(n):
            c[x+i][y][0] = n
        
    if c[x][y][1] == -1:
        n = 0
        while y+n < w and l[x][y+n] == ".":
            n += 1
        for i in range(n):
            c[x][y+i][1] = n

    return c[x][y][0]+c[x][y][1]
ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans,count(i,j))
print(ans-1)

Submission status: Time Limit Exceeded

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

c = [[[-1]*2 for i in range(w)] for i in range(h)]

def count(x,y):

    if c[x][y][0] == -1:
        n = 0
        while x+n < h and l[x+n][y] == ".":
            n += 1
        for i in range(n):
            c[x+i][y][0] = n
        
    if c[x][y][1] == -1:
        n = 0
        while y+n < w and l[x][y+n] == ".":
            n += 1
        for i in range(n):
            c[x][y+i][1] = n

    return c[x][y][0]+c[x][y][1]
ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans,count(i,j))
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#python3

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

    sumv = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
        done = [0 for _ in range(w)]
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                sumv[i][j+k] = sumv[i][j+k] + seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    for j in range(w):
        done = [0 for _ in range(h)]
        for i in range(h):
            if ss[i][j] == '#':
                continue
            if done[i] == 1:
                continue
            seq = 0
            while i + seq < h:
                if ss[i+seq][j] == '#':
                    break
                seq = seq + 1
            for k in range(seq):
                sumv[i+k][j] = sumv[i+k][j] +  seq
                done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumv[i][j]-1)            
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
#python3

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

    sumv = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
        done = [0 for _ in range(w)]
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                sumv[i][j+k] += seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    for j in range(w):
        done = [0 for _ in range(h)]
        for i in range(h):
            if ss[i][j] == '#':
                continue
            if done[i] == 1:
                continue
            seq = 0
            while i + seq < h:
                if ss[i+seq][j] == '#':
                    break
                seq = seq + 1
            for k in range(seq):
                sumv[i+k][j] += seq
                done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumv[i][j]-1)            
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
#python3

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

    sumh = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
            done = [0 for _ in range(w)]
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                if sumh[i][j+k] != 0:
                    continue
                sumh[i][j+k] += seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    sumv = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
            for i in range(h):
                done = [0 for _ in range(h)]
                if ss[i][j] == '#':
                    continue
                if done[i] == 1:
                    continue
                seq = 0
                while i + seq < h:
                    if ss[i+seq][j] == '#':
                        break
                    seq = seq + 1
                for k in range(seq):
                    if sumv[i+k][j] != 0:
                        continue
                    sumv[i+k][j] += seq
                    done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumh[i][j]+sumv[i][j]-1)            
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
#python3

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

    sumh = [[0 for _ in range(w)] for _ in range(h)]
    #横方向について連続で何マス続くかを求める
    for i in range(h):
        for j in range(w):
            #i,jはぞれぞれ縦と横のマスの位置を表すインデックス
            #doneは連続何マス続くかをすでに求めたかどうかを保持するリスト　
            done = [0 for _ in range(w)]
            if ss[i][j] == '#':
                continue
            if done[j] == 1:
                continue
            #seqは横に何マス続くかを記録する変数
            seq = 0
            while j + seq < w:
                if ss[i][j+seq] == '#':
                    break
                seq = seq + 1
            #ss[i][j]からss[i][j+seq]までのマスは連続してseqマスである
            for k in range(seq):
                if sumh[i][j+k] != 0:
                    continue
                sumh[i][j+k] += seq
                #連続するマスが求め終わったマスを記録する
                done[j+k] = 1
    
    #縦方向について同様に
    sumv = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
            for i in range(h):
                done = [0 for _ in range(h)]
                if ss[i][j] == '#':
                    continue
                if done[i] == 1:
                    continue
                seq = 0
                while i + seq < h:
                    if ss[i+seq][j] == '#':
                        break
                    seq = seq + 1
                for k in range(seq):
                    if sumv[i+k][j] != 0:
                        continue
                    sumv[i+k][j] += seq
                    done[i+k] = 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, sumh[i][j]+sumv[i][j]-1)            
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(np.amax(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(np.amax(ans)-1)

Submission status: Time Limit Exceeded

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

dph = [[0 for _ in range(w)] for _ in range(h)]
dpw = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if maze[i][j] == '#':
      continue
    if dpw[i][j] != 0:
      continue
    k = j
    count = 0
    while k< w:
      
      if maze[i][k] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dpw[i][l] = count
      
for i in range(w):
  for j in range(h):
    if maze[j][i] == '#':
      continue
    if dph[j][i] != 0:
      continue
    k = j
    count = 0
    while k< h:
      
      if maze[k][i] == '.':
        count += 1
        k += 1
      else:
        break
    for l in range(j,k):
      dph[l][i] = count


ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dpw[i][j] + dph[i][j])
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
	s.append(input().rstrip())
num=[[0]*w for _ in range(h)]
for i in range(h):
	p=0
	for j in range(w):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(h):
	p=0
	for j in range(w-1,-1,-1):
		if s[i][j]==".":
			p+=1
			num[i][j]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
for i in range(w):
	p=0
	for j in range(h-1,-1,-1):
		if s[j][i]==".":
			p+=1
			num[j][i]+=p
		else:
			p=0
ans=0
for i in range(h):
	ans=max(ans,max(num[i])-3)
print(ans)

Submission status: Time Limit Exceeded

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

def f(x,y):
    c=1
    for i in range(1,h):
        if x+i>=h:
            break
        if M[x+i][y]=='#':
            break
        c+=1
    for i in range(-1,-h,-1):
        if x+i<0:
            break
        if M[x+i][y]=='#':
            break
        c+=1
        
    for i in range(1,w):
        if y+i>=w:
            break
        if M[x][y+i]=='#': 
            break
        c+=1
    for i in range(-1,-w,-1):
        if y+i<0:
            break
        if M[x][y+i]=='#':
            break
        c+=1
    return c
            
        

ans=1

for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(ans,f(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = [int(i) for i in input().split()]
room = ['0'] * H
ans = -1
for i in range(H):
    room[i] = list(input())
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
B = [[0] * W for _ in range(H)]
for i in range(W):
    if room[0][i] == '.':
        U[0][i] = 1
        if i == 0:
            L[0][i] = 1
        else:
            L[0][i] = L[0][i-1] +1
for i in range(H):
    if room[i][0] == '.':
        L[i][0] = 1
        if i == 0:
            U[i][0] = 1
        else:
            U[i][0] = U[i-1][0] +1
for x in range(1,H):
    for y in range(1,W):
        if room[x][y] == '.':
            U[x][y] = U[x-1][y]+1
            L[x][y] = L[x][y-1]+1
Ha = [int(i) for i in range(H)]
Wa = [int(i) for i in range(W)]
for i in Wa[::-1]:
    if room[H-1][i] == '.':
        B[H-1][i] = 1
        if i == W-1:
            R[H-1][i] = 1
        else:
            R[H-1][i] = R[H-1][i+1] +1
for i in Ha[::-1]:
    if room[i][W-1] == '.':
        R[i][W-1] = 1
        if i == H-1:
            B[i][W-1] = 1
        else:
            B[i][W-1] = B[i+1][W-1] +1
Haa = [int(i) for i in range(H-1)]
Waa = [int(i) for i in range(W-1)]
for x in Haa[::-1]:
    for y in Waa[::-1]:
        if room[x][y] == '.':
            R[x][y] = R[x][y+1]+1
            B[x][y] = B[x+1][y]+1
for x in range(H):
    for y in range(W):
        if room[x][y] == '.':
            ansa = U[x][y]+R[x][y]+B[x][y]+L[x][y]-3
            ans = max(ans,ansa)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

queue = deque()

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

cnt = 0

for i in range(h):
    cnt = 0
    for j in range(w):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            left[i][j] = cnt

    cnt = 0
    for j in reversed(range(w)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            right[i][j] = cnt


for j in range(w):
    cnt = 0
    for i in range(h):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            up[i][j] = cnt

    cnt = 0
    for i in reversed(range(h)):
        if maze[i][j] == '#': cnt = 0
        else:
            cnt += 1
            down[i][j] = cnt

ans = 0
for i in range(h):
    for j in range(w):
        tmp = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        ans = max(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import numpy as np

h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

queue = deque()

vert = np.array([[0 for j in range(w)] for i in range(h)])
hori = np.array([[0 for j in range(w)] for i in range(h)])

h_start = 0
h_val = 0
v_start = 0
v_val = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            h_val += 1
            if j == w-1:
                hori[i,h_start:w] += h_val
                h_val = 0
                h_start = 0
        else:
            hori[i,h_start:j] += h_val
            h_val = 0
            h_start = (j+1)%(w)

for j in range(w):
    for i in range(h):
        if maze[i][j] == '.':
            v_val += 1
            if i == h-1:
                vert[v_start:h,j] += v_val
                v_val = 0
                v_start = 0
        else:
            vert[v_start:i,j] += v_val
            v_val = 0
            v_start = (i+1)%(h)


sum_ = hori + vert - 1

print(np.max(sum_))

Submission status: Time Limit Exceeded

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

# leftの個数カウントを行う
Left_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Left_count[i][j] = count

# Rightの個数カウントを行う
Right_count = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = S[i][::-1]
    count = 0
    for j in range(w):
        if s[j] == '#':
            count = 0
            continue
        else:
            count += 1
            Right_count[i][j] = count
for i in range(h):
    Right_count[i] = Right_count[i][::-1]

# Upの個数カウントを行う
Up_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Up_count[i][j] = count

# Downの個数カウントを行う
Down_count = [[0 for _ in range(w)] for _ in range(h)]
for j in range(w):
    count = 0
    for i in range(h-1,-1,-1):
        if S[i][j] == '#':
            count = 0
            continue
        else:
            count += 1
            Down_count[i][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        tot_ij = Left_count[i][j] + Right_count[i][j] + Down_count[i][j] + Up_count[i][j] -3
        ans = max(tot_ij, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def set_value(l, i, j, di, dj, is_edge):
    if is_edge:
        return 1
    return l[i + di][j + dj] + 1


def main():
    height, width = map(int, input().split())
    grid = [input() for _ in range(height)]
    left = [[0 for _ in range(width)] for _ in range(height)]
    right = deepcopy(left)
    down = deepcopy(left)
    upper = deepcopy(left)
    for i in range(height):
        for j in range(width):
            if grid[i][j] == ".":
                upper[i][j] = set_value(upper, i, j, -1, 0, i == 0)
                left[i][j] = set_value(left, i, j, 0, -1, j == 0)
            if grid[-i - 1][-j - 1] == ".":
                down[-i - 1][-j - 1] = set_value(down, - i - 1,  - j - 1, 1, 0, i == -height + 1)
                right[-i - 1][-j - 1] = set_value(right, - i - 1,  - j - 1, 0, 1, j == -width + 1)
    answer = 0
    for i in range(height):
        for j in range(width):
            answer = max(answer, upper[i][j] + left[i][j] + down[i][j] + right[i][j] - 3)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
M = np.array([list(input()) for i in range(H)])
dp = np.zeros((H, W, 2), dtype=np.int)
ans = 0
#LU
for h in range(H):
  for w in range(W):
    if M[h][w] == "#": continue
    dp[h][w][0] = dp[h][w-1][0] + 1 if w != 0 else 1
    dp[h][w][1] = dp[h-1][w][1] + 1 if h != 0 else 1
#RD
for h in range(H-1, -1, -1):
  for w in range(W-1, -1, -1):
    if M[h][w] == "#": continue
    x = dp[h][w+1][0] + 1 if w != W - 1 else 1
    y = dp[h+1][w][1] + 1 if h != H - 1 else 1
    ans = max(ans, np.sum(dp[h][w]) + x + y -3)
    dp[h][w] = [x, y]
print(ans)

Submission status: Time Limit Exceeded

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

hor = [[0 for _ in range(w)] for _ in range(h)]
ver = [[0 for _ in range(w)] for _ in range(h)]

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

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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hor[i][j] + ver[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
Board=[[False for i in range(0,W)] for i in range(0,H)]
for _ in range(H):
    S=input()
    for c in range(W):
        if S[c]=='.':
            Board[_][c]=True
ans=0
for h in range(0,H):
    for w in range(0,W):
        if not Board[h][w]:
            continue
        tmp=1
        cnt=1
        while cnt+w<W and Board[h][cnt+w]:
            cnt+=1
            tmp+=1
        cnt=1
        while w-cnt>=0 and Board[h][-cnt+w]:
            cnt+=1
            tmp+=1
        cnt=1
        while cnt+h<H and Board[cnt+h][w]:
            cnt+=1
            tmp+=1
        cnt=1
        while -cnt+h>=0 and Board[h-cnt][
            w]:
            cnt+=1
            tmp+=1

        ans=max(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

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


ans_w = [[0] * w for i in range(h)]
ans_h = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == '#': continue
        if ans_w[i][j] != 0: continue

        while j + cnt < w:
            if s[i][j + cnt] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_w[i][j + k] = cnt
# print(ans_w)

for i in range(w):
    for j in range(h):
        cnt = 0
        if s[j][i] == '#': continue
        if ans_h[j][i] != 0: continue

        while j + cnt < h:
            if s[j + cnt][i] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_h[j + k][i] = cnt
# print(ans_h)

out = 0
for i in range(h):
    for j in range(w):
        out = max(out, ans_h[i][j] + ans_w[i][j])

print(out - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

h,w=list(map(int,input().split()))
s=[]

left=[[0]*w for _ in range(h)]
right=[[0]*w for _ in range(h)]
up=[[0]*w for _ in range(h)]
down=[[0]*w for _ in range(h)]

for i in range(h):
    s.append([x for x in sys.stdin.readline().strip()])

for i in range(h):
    cntl=0
    cntr=0
    for jl in range(w):
        jr=w-jl-1

        if s[i][jl]=='#':
            cntl=0
        else:
            cntl+=1
        
        if s[i][jr]=='#':
            cntr=0
        else:
            cntr+=1
        
        left[i][jl]=cntl
        right[i][jr]=cntr

for j in range(w):
    cntu=0
    cntd=0
    for iu in range(h):
        id=h-iu-1

        if s[iu][j]=='#':
            cntu=0
        else:
            cntu+=1
        
        if s[id][j]=='#':
            cntd=0
        else:
            cntd+=1
        
        up[iu][j]=cntu
        down[id][j]=cntd
ret=0

for i in range(h):
    for j in range(w):
        ret=max(ret,left[i][j]+right[i][j]+up[i][j]+down[i][j]-3)

print(ret)