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: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

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

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

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

for i in range(H-1, -1, -1):
	for j in range(W):
		if S[i][j] == '#':
			D[i][j] = 0
		elif i == H-1:
			D[i][j] = 1
		else:
			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: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
# from numpy.fft import fft, ifft
from fractions import gcd
# import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

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


for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

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

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

# L = np.array(L)
# R = np.array(R)
# U = np.array(U)
# D = np.array(D)

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: Runtime Error

Solution code:
import numpy as np
 
def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        i_col = 0
        j_col = 0
        s = s_list[i_row]
        while(i_col < W):
            char = s[i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s[j_col]
                    if c == '#':
                        break
 
                row_count[i_row, i_col:j_col] = j_col - i_col
            i_col = j_col + 1
 
 
    col_count = np.zeros((H, W))
    for i_col in range(W):
        i_row = 0
        j_row = 0
        s_col = [s[i_col] for s in s_list]
        while(i_row < H):
            char = s_col[i_row]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_col[j_row]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
            i_row = j_row + 1
    print(int(np.max(row_count + col_count)) - 1)
 
 
 
if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())
 
    main(H, W, s_list)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)

# for h in range(H):
#     print(S[h])
    
# print('#############')
    
L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh.append(a)
    L.append(Lh)

# for h in range(H):
#     print(L[h])
    
# print('#############')
    
R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh.append(a)
    Rh.reverse()
    R.append(Rh)

# for h in range(H):
#     print(R[h])
    
# print('#############')

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw.append(a)
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]
    
# for h in range(H):
#     print(U[h])

# print('#############')

D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw.append(a)
    Dw.reverse()
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]
    
# for h in range(H):
#     print(D[h])
    
# print('#############')

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)

# for h in range(H):
#     print(S[h])
    
# print('#############')
    
L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh.append(a)
    L.append(Lh)

# for h in range(H):
#     print(L[h])
    
# print('#############')
    
R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh.append(a)
    Rh.reverse()
    R.append(Rh)

# for h in range(H):
#     print(R[h])
    
# print('#############')

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw.append(a)
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]
    
# for h in range(H):
#     print(U[h])

# print('#############')

D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw.append(a)
    Dw.reverse()
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]
    
# for h in range(H):
#     print(D[h])
    
# print('#############')

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

Submission status: Runtime Error

Solution code:
import numpy as np


def acinput():
    return list(map(int, input().split(" ")))


H, W = acinput()
S = [["#"]*(W+2)]
for i in range(H):
    tmp=["#"]
    tmp.extend(list(input()))
    tmp.append("#")

    S.append(tmp)
S.append(["#"]*(W+2))

def search(x,d):
    global res

    xx=(x[0],x[1])
    if xx in dp:
        if len(dp[xx][d])>0:
            return dp[xx]

    if S[xx[0]][xx[1]] == "#":
        return (x,x,x,x,0)
    
    dp[xx]=[[]for i in range(5)]
    dp[xx][0]=search(x+[1,0],0)[0]
    dp[xx][1]=search(x+[0,1],1)[1]
    dp[xx][2]=search(x+[-1,0],2)[2]
    dp[xx][3]=search(x+[0,-1],3)[3]

    tdp=dp[xx]
    tate=abs(tdp[2][0]-tdp[0][0])-1
    yoko=abs(tdp[3][1]-tdp[1][1])-1
    dp[xx][4]=tate+yoko-1
    if res <tate+yoko-1:
        res=tate+yoko-1
        #input()
    return dp[xx]

dp={}
res=0

for i in range(1,H+1):
    for j in range(1,W+1):
        search(np.array([i,j]),0)


print(res)

#print(dp)

Submission status: Runtime Error

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

from collections import defaultdict


y = [[] for i in range(W)]
x=0
left=-1

ans=1

for i in range(H):
    left=-1
    for j in range(W):
        if S[i][j]=='.' and left==-1:
            left=j
        elif (S[i][j]=='#' and left!=-1) or j==W-1:
            if S[i][j]=='#':
                x=j-left
            else:
                x=j-left+1

            for k in range(left,left+x):
                if y[i][k]!=0:
                    ans=max(ans,x+y[i][k]-1)
                else:
                    l=i+1
                    while l<H and S[l][k]==".":
                        l+=1
                    y_val=l-i
                    ans = max(ans,x+y_val-1)
                    for m in range(i+1,l):
                        y[m][k]=y_val
            left=-1

print(ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from numpy.fft import fft, ifft
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

S = np.array(S)

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


for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

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

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

L = np.array(L)
R = np.array(R)
U = np.array(U)
D = np.array(D)

print((L+R+U+D).max()-3)

Submission status: Runtime Error

Solution code:
import numpy as np


def acinput():
    return list(map(int, input().split(" ")))


H, W = acinput()
S = [["#"]*(W+2)]
for i in range(H):
    tmp=["#"]
    tmp.extend(list(input()))
    tmp.append("#")

    S.append(tmp)
S.append(["#"]*(W+2))

def search(x,d):
    global res

    xx=(x[0],x[1])
    if xx in dp:
        if dp[xx][d]:
            return dp[xx]

    if S[xx[0]][xx[1]] == "#":
        return (x,x,x,x,0)
    
    dp[xx]=[[-1]for i in range(5)]
    dp[xx][0]=search(x+[1,0],0)[0]
    dp[xx][1]=search(x+[0,1],1)[1]
    dp[xx][2]=search(x+[-1,0],2)[2]
    dp[xx][3]=search(x+[0,-1],3)[3]

    tdp=dp[xx]
    tate=abs(tdp[2][0]-tdp[0][0])-1
    yoko=abs(tdp[3][1]-tdp[1][1])-1
    dp[xx][4]=tate+yoko-1
    if res <tate+yoko-1:
        res=tate+yoko-1
        #input()
    return dp[xx]

dp={}
res=0

for i in range(1,H+1):
    for j in range(1,W+1):
        search(np.array([i,j]),0)


print(res)

#print(dp)

Submission status: Runtime Error

Solution code:
from collections import deque

def solve():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    rowm = [None] * H
    for i in range(H):
        start = -1
        end = 0
        save = (start, end, i)
        for j in range(W):
            if S[i][j] == '.':
                end = j
            else:
                start = j
                end = j
            if end - start > save[1] - save[0]:
                save = (start, end, i)
        rowm[i] = save
    colm = [None] * W
    for j in range(W):
        start = -1
        end = 0
        save = (start, end, j)
        for i in range(H):
            if S[i][j] == '.':
                end = i
            else:
                start = i
                end = i
            if end - start > save[1] - save[0]:
                save = (start, end, j)
        colm[j] = save
    rowm.sort(key = lambda x: x[1] - x[0], reverse = True)
    colm.sort(key = lambda x: x[1] - x[0], reverse = True)
    def max_ans(i,j):
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        return e1 - s1 + e2 - s2 - 1
    # priority queue
    ij_set = set()
    ij_set.add((0, 0))
    queue = deque()
    queue.append((max_ans(0, 0), 0,0))
    def AddToQueue(_ele):
        if len(queue) == 0:
            queue.append(_ele)
        else:
            cnt = 0
            while cnt < len(queue) and queue[cnt][0] >= _ele[0]:
                cnt += 1
            ij = (_ele[1], _ele[2])
            if not (ij in ij_set):
                queue.insert(cnt, _ele)
                ij_set.add(ij)
    ret = 1
    while len(queue) > 0:
        ans, i, j = queue.popleft()
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        if ans == 1:
            ret = ans
            break
        if row >= s2 and row <=e2 and col >= s1 and col <= e1:
            ret = ans
            break
        if i + 1 < H:
            AddToQueue((max_ans(i+1,j), i+1, j))
        if j + 1 < W:
            AddToQueue((max_ans(i,j+1), i, j+1))
    print ret

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    H, W = [int(s) for s in input().split()]
    S = [input() for _ in range(H)]
    sharps = set([(h, w) for h in range(H) for w in range(W) if S[h][w] == '#'])

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

    def count(h, w, n):
        if dp[h][w][n] != 0:
            return dp[h][w][n]
        elif (h, w) in sharps:
            dp[h][w][n] = 0
            return dp[h][w][n]
        else:
            if h > 0 and n == 0:
                dp[h][w][n] = count(h - 1, w, n) + 1
            elif h < H - 1 and n == 1:
                dp[h][w][n] = count(h + 1, w, n) + 1
            elif w > 0 and n == 2:
                dp[h][w][n] = count(h, w - 1, n) + 1
            elif w < W - 1 and n == 3:
                dp[h][w][n] = count(h, w + 1, n) + 1
            else:
                dp[h][w][n] = 1
            return dp[h][w][n]

    print(max([sum([count(h, w, n) for n in range(4)]) - 3 for h in range(H) for w in range(W)]))

solve()

Submission status: Runtime Error

Solution code:
from collections import deque

def solve():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    rowm = [None] * H
    for i in range(H):
        start = -1
        end = 0
        save = (start, end, i)
        for j in range(W):
            if S[i][j] == '.':
                end = j
            else:
                start = j
                end = j
            if end - start > save[1] - save[0]:
                save = (start, end, i)
        rowm[i] = save
    colm = [None] * W
    for j in range(W):
        start = -1
        end = 0
        save = (start, end, j)
        for i in range(H):
            if S[i][j] == '.':
                end = i
            else:
                start = i
                end = i
            if end - start > save[1] - save[0]:
                save = (start, end, j)
        colm[j] = save
    rowm.sort(key = lambda x: x[1] - x[0], reverse = True)
    colm.sort(key = lambda x: x[1] - x[0], reverse = True)
    def max_ans(i,j):
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        return e1 - s1 + e2 - s2 - 1
    # priority queue
    ij_set = set()
    ij_set.add((0, 0))
    queue = deque()
    queue.append((max_ans(0, 0), 0,0))
    def AddToQueue(_ele):
        if len(queue) == 0:
            queue.append(_ele)
        else:
            cnt = 0
            while cnt < len(queue) and queue[cnt][0] >= _ele[0]:
                cnt += 1
            ij = (_ele[1], _ele[2])
            if not (ij in ij_set):
                queue.insert(cnt, _ele)
                ij_set.add(ij)
    ret = 1
    while len(queue) > 0:
        ans, i, j = queue.popleft()
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        if ans == 1:
            ret = ans
            break
        if row >= s2 and row <=e2 and col >= s1 and col <= e1:
            ret = ans
            break
        if i + 1 < H:
            AddToQueue((max_ans(i+1,j), i+1, j), queue, ij_set)
        if j + 1 < W:
            AddToQueue((max_ans(i,j+1), i, j+1), queue, ij_set)
    print ret

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue
    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][1])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def acinput():
    return list(map(int, input().split(" ")))


H, W = acinput()
S = [["#"]*(W+2)]
for i in range(H):
    tmp=["#"]
    tmp.extend(list(input()))
    tmp.append("#")

    S.append(tmp)
S.append(["#"]*(W+2))

def search(x,d):
    global res


    xx=(x[0],x[1])
    if xx in dp:
        if len(dp[xx][d])>0:
            return dp[xx]

    if S[x[0]][x[1]] == "#":
        return (x,x,x,x,0)
    
    dp[xx]=[[]for i in range(5)]
    dp[xx][0]=search(x+[1,0],0)[0]
    dp[xx][1]=search(x+[0,1],1)[1]
    dp[xx][2]=search(x+[-1,0],2)[2]
    dp[xx][3]=search(x+[0,-1],3)[3]

    tdp=dp[xx]
    tate=abs(tdp[2][0]-tdp[0][0])-1
    yoko=abs(tdp[3][1]-tdp[1][1])-1
    dp[xx][4]=tate+yoko-1
    if res <tate+yoko-1:
        res=tate+yoko-1
        #input()
    return dp[xx]

dp={}
res=0

for i in range(1,H+1):
    for j in range(1,W+1):
        search(np.array([i,j]),0)


print(res)

#print(dp)

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int, input().split())
S = []
for i in range(h):
    S.append(input())
 
sw = []
 
for i in range(h):
    c = []
    for j in range(w):
        if S[i][j] == '#':
            c.append(j)
    c.append(w)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sw.append(k[0:-1])
 
sh =[]
 
for i in range(w):
    c = []
    for j in range(h):
        if S[j][i] == '#':
            c.append(j)
    c.append(h)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sh.append(k[0:-1])
 
sw = np.array(sw)
sh = np.array(sh)
sh = sh.T
 
x = sw + sh
 
print(np.amax(x) - 1)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
MAP = [list('#' + input() + '#') for j in range(H)]
MAP.insert(0, ['#' for i in range(W + 2)])
MAP.append(['#' for i in range(W + 2)])
MAP2 = copy.deepcopy(MAP)


def line(MAP):
    for i in range(1, H + 2):
        before = 0
        for j in range(1, W + 2):
            if MAP[i][j] == '#':
                for x in range(before + 1, j):
                    MAP[i][x] = j - before - 1
                before = j


def column(MAP2):
    for j in range(1, W + 2):
        before = 0
        for i in range(1, H + 2):
            if MAP2[i][j] == '#':
                for y in range(before + 1, i):
                    global ans
                    ans = max(ans, i - before - 1 + MAP[y][j])
                before = i


line(MAP)
ans = 0
column(MAP2)
print(ans - 1)

Submission status: Runtime Error

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

dp = [[[-1] * 4 for _ in range(W)] for _ in range(H)]


def count(h, w, n):
    if dp[h][w][n] != -1:
        return dp[h][w][n]
    elif S[h][w] == '#':
        dp[h][w][n] = 0
        return dp[h][w][n]
    else:
        if h > 0 and n == 0:  # up
            dp[h][w][n] = count(h - 1, w, n) + 1
        elif h < H - 1 and n == 1:
            dp[h][w][n] = count(h + 1, w, n) + 1
        elif w > 0 and n == 2:
            dp[h][w][n] = count(h, w - 1, n) + 1
        elif w < W - 1 and n == 3:
            dp[h][w][n] = count(h, w + 1, n) + 1
        else:
            dp[h][w][n] = 1
        return dp[h][w][n]

# north, west, south, east
print(max([sum([count(h, w, n) for n in range(4)]) - 3 for h in range(H) for w in range(W)]))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
S = [""] * H
tate = [[-1] * H for i in range(H)]
yoko = [[-1] * W for i in range(W)]

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

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': continue
        
        t = 0
        if tate[h][w] == -1:
            for i in range(H):
                if h + i >= H or S[h + i][w] == '#': break
                t += 1
            
            for i in range(H):
                if h + i >= H or S[h + i][w] == '#': break
                tate[h + i][w] = t

        y = 0
        if yoko[h][w] == -1:
            for i in range(W):
                if w + i >= W or S[h][w + i] == '#': break
                y += 1
            
            for i in range(W):
                if w + i >= W or S[h][w + i] == '#': break
                yoko[h][w + i] = y

        ans = max(ans, tate[h][w] + yoko[h][w] - 1)

print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
S = [""] * H
tate = [[-1] * H for i in range(H)]
yoko = [[-1] * W for i in range(W)]

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

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': continue
        
        t = 0
        if tate[h][w] == -1:
            for i in range(H):
                if h + i >= H or S[h + i][w] == '#': break
                t += 1
            
            for i in range(H):
                if h + i >= H or S[h + i][w] == '#': break
                tate[h + i][w] = t

        y = 0
        if yoko[h][w] == -1:
            for i in range(W):
                if w + i >= W or S[h][w + i] == '#': break
                y += 1
            
            for i in range(H):
                if w + i >= W or S[h][w + i] == '#': break
                yoko[h][w + i] = y

        ans = max(ans, tate[h][w] + yoko[h][w] - 1)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


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

dp = np.array([[[-1] * 4 for _ in range(W)] for _ in range(H)])


def count(h, w, n):
    if dp[h, w, n] != -1:
        return dp[h, w, n]
    elif S[h][w] == '#':
        dp[h, w, n] = 0
        return dp[h, w, n]
    else:
        if h > 0 and n == 0:  # up
            dp[h, w, n] = count(h - 1, w, n) + 1
        elif h < H - 1 and n == 1:
            dp[h, w, n] = count(h + 1, w, n) + 1
        elif w > 0 and n == 2:
            dp[h, w, n] = count(h, w - 1, n) + 1
        elif w < W - 1 and n == 3:
            dp[h, w, n] = count(h, w + 1, n) + 1
        else:
            dp[h, w, n] = 1
        return dp[h, w, n]

# north, west, south, east
best = 0
for h in range(H):
    for w in range(W):
        best = max([best, sum([count(h, w, n) for n in range(4)]) - 3])

print(best)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
L = [[0] * W]*H; R = [[0] * W]*H; D = [[0] * W]*H; U = [[0] * W]*H;
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.'
            L[i][j] = L[i][j-1] if j >= 1 else 1
            U[i][j] = U[i-1][j] if i >= 1 else 1
for i in reversed(range(H)):
    for j in reversed(range(W)):
        if grid[i][j] == '.':
            R[i][j] = R[i][j+1] if j <= W-1 else 1
            D[i][j] = D[i+1][j] if i <= H-1 else 1
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3)
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
L = [[0] * W]*H; R = [[0] * W]*H; D = [[0] * W]*H; U = [[0] * W]*H;
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.'
            L[i][j] = L[i][j-1] if j >= 1 else 1
            U[i][j] = U[i-1][j] if i >= 1 else 1
for i in reversed(range(H)):
    for j in reversed(range(W)):
        if grid[i][j] == '.'
            R[i][j] = R[i][j+1] if j <= W-1 else 1
            D[i][j] = D[i+1][j] if i <= H-1 else 1
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int H, W;

int main() {
    cin >> H >> W;
    vector<vector<int>> a(H + 1, vector<int>(W + 1));
    vector<vector<int>> b(H + 1, vector<int>(W + 1, 0));
    for(int i = 0; i < W + 1; i++){
        a.at(H).at(i) = 1;
    }
    for(int j = 0; j < H; j++){
        string str;
        cin >> str;
        a.at(j).at(W) = 1;
        for(int i = 0; i < W; i++){
            if(str.at(i) == '.')
                a.at(j).at(i) = 0;
            else
                a.at(j).at(i) = 1;
        }
    }

    //横方向
    for(int j = 0; j < H; j++){
        int prev = 1;
        int start = 0;
        for(int i = 0; i < W + 1; i++){
            if (a.at(j).at(i) == 0){
                if(prev == 1){
                    start = i;
                    prev = 0;
                }
            }else{
                if(prev == 0){
                    int num = i - start;
                    for(int k = start; k < i; k++){
                        b.at(j).at(k) = num;
                    }
                    prev = 1;
                }
            }
        }
    }

    //縦方向
    for(int i = 0; i < W; i++){
        int prev = 1;
        int start = 0;
        for(int j = 0; j < H + 1; j++){
            if (a.at(j).at(i) == 0){
                if(prev == 1){
                    start = j;
                    prev = 0;
                }
            }else{
                if(prev == 0){
                    int num = j - start;
                    for(int k = start; k < j; k++){
                        b.at(k).at(i) += num - 1;
                    }
                    prev = 1;
                }
            }
        }
    }

    int ans = 0;
    for(int j = 0; j < H; j++){
        int m1 = *max_element(b.at(j).begin(), b.at(j).end());
        ans = max(ans, m1);
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

H, W = list(map(int, sys.stdin.readline().split()))
S = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)]) == '.'
ups = np.zeros((H, W), dtype=int)
downs = np.zeros((H, W), dtype=int)
rights = np.zeros((H, W), dtype=int)
lefts = np.zeros((H, W), dtype=int)

for h in range(1, H):
    ups[h] = (ups[h - 1] + 1) * S[h - 1]
    downs[H - h] = (downs[H - h + 1] + 1) * S[H - h + 1]
for w in range(1, W):
    lefts[:, w] = (lefts[:, w - 1] + 1) * S[:, w - 1]
    rights[:, W - w] = (rights[:, W - w + 1] + 1) * S[:, W - w + 1]
print(((ups + downs + lefts + rights) * S).max() + 1)

Submission status: Runtime Error

Solution code:
def solve():
    h, w = map(int, input().split())
    S = list(input() + '#' for _ in range(h)) + ['#' * (w + 1)]
    H = [[0] * w for _ in range(h + 1)]
    W = [[0] * w for _ in range(h + 1)]
    def f(r, c, num):
        if W[r][c] == 0:
            if c < w and S[r][c + 1] == '.':
                W[r][c] = f(r, c + 1, num + 1)
            else:
                W[r][c] = num
        return W[r][c]
    def g(r, c, num):
        if H[r][c] == 0:
            if r < h and S[r + 1][c] == '.':
                H[r][c] = g(r + 1, c, num + 1)
            else:
                H[r][c] = num
        return H[r][c]
    ans = 0
    for r in range(h):
        for c in range(w):
            if S[r][c] == '.':
                ans = max(ans, f(r, c, 1) + g(r, c, 1) - 1)
    print(ans)
solve()