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: Accepted

Solution code:
import sys
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 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: Accepted

Solution code:
import sys
# 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 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: Accepted

Solution code:
import sys
# 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 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: Accepted

Solution code:
import sys
# 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 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: Accepted

Solution code:
import sys
# 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)
# print((L+R+U+D).max()-3)

Submission status: Accepted

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)]
    for r in range(h):
        c = 0
        while c < w:
            if S[r][c] == '.':
                t = S[r][c:].find('#')
                for j in range(c, c + t):
                    W[r][j] = t
                c += t
            c += 1
    for c in range(w):
        r = 0
        while r < h:
            if S[r][c] == '.':
                t = r + 1
                cnt = 1
                while S[t][c] == '.':
                    t += 1
                    cnt += 1
                for i in range(r, t):
                    H[i][c] = cnt
                r = t
            r += 1
    ans = 0
    for r in range(h):
        for c in range(w):
            ans = max(ans, H[r][c] + W[r][c] - 1)
    print(ans)
solve()

Submission status: Accepted

Solution code:
import numpy as np
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        S = [0 if c == '#' else 1 for c in input().strip()]
        A.append(S)

    A = np.array(A)
    up = np.zeros((H+1, W), dtype=np.int)
    down = np.zeros((H+1, W), dtype=np.int)
    right = np.zeros((H, W+1), dtype=np.int)
    left = np.zeros((H, W+1), dtype=np.int)

    for i in range(1, H+1):
        up[i] = (up[i-1] + 1) * A[i-1]
        down[H-i] = (down[H-i+1] + 1) * A[H-i]

    for i in range(1, W+1):
        right[:, i] = (right[:, i-1] + 1) * A[:, i-1]
        left[:, W-i] = (left[:, W-i+1] + 1) * A[:, W-i]

    R = (up[1:] + down[:H] - 1) * A
    C = (right[:, 1:] + left[:, :W] - 1) * A
    W = (R + C - 1) * A
    return W.max()


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [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 s[i][j] == '.':
      l[i][j] = l[i][j-1] + 1
      u[i][j] = u[i-1][j] + 1
    if s[i][-j-1] == '.':
      r[i][-j-1] = r[i][-j] + 1
    if s[-i-1][j] == '.':
      d[-i-1][j] = d[-i][j] + 1
    
torch = 0
for i in range(h):
  for j in range(w):
    torch = max(torch, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)

print(torch)

Submission status: Accepted

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] * S[h]
    downs[H - h - 1] = (downs[H - h] + 1) * S[H - h] * S[H - h-1]
for w in range(1, W):
    lefts[:, w] = (lefts[:, w - 1] + 1) * S[:, w - 1] * S[:, w]
    rights[:, W - w - 1] = (rights[:, W - w] + 1) * S[:, W - w] * S[:, W - w-1]
print(((ups + downs + lefts + rights) * S).max() + 1)

Submission status: Accepted

Solution code:
import numpy as np
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        S = [0 if c == '#' else 1 for c in input().strip()]
        A.append(S)

    A = np.array(A)
    up = np.zeros((H+1, W), dtype=np.int)
    down = np.zeros((H+1, W), dtype=np.int)
    right = np.zeros((H, W+1), dtype=np.int)
    left = np.zeros((H, W+1), dtype=np.int)

    for i in range(1, H+1):
        up[i] = (up[i-1] + 1) * A[i-1]

    for i in range(H-1, -1, -1):
        down[i] = (down[i+1] + 1) * A[i]

    for i in range(1, W+1):
        right[:, i] = (right[:, i-1] + 1) * A[:, i-1]

    for i in range(W-1, -1, -1):
        left[:, i] = (left[:, i+1] + 1) * A[:, i]

    R = (up[1:] + down[:H] - 1) * A
    C = (right[:, 1:] + left[:, :W] - 1) * A
    W = (R + C - 1) * A
    return W.max()


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
hc = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                hc[i][j] = hc[i][j - 1] + 1
            else:
                hc[i][j] = 1
for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j < w - 1:
                if hc[i][j] < hc[i][j + 1]:
                    hc[i][j] = hc[i][j + 1]
wc = [[0] * h for i in range(w)]
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            if j > 0:
                wc[i][j] = wc[i][j - 1] + 1
            else:
                wc[i][j] = 1
for i in range(w):
    for j in range(h - 1, -1, -1):
        if s[j][i] == ".":
            if j < h - 1:
                if wc[i][j] < wc[i][j + 1]:
                    wc[i][j] = wc[i][j + 1]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hc[i][j] + wc[j][i] - 1)
print(ans)

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)
b = np.array(grid)
b = np.where(b == ".", 1, 0)

a1 = np.zeros((h,w), dtype=np.int)
a2 = np.zeros((h,w), dtype=np.int)
a3 = np.zeros((h,w), dtype=np.int)
a4 = np.zeros((h,w), dtype=np.int)
#print(b)

for i in range(1,h):
    a1[i] += (a1[i-1]+1)*b[i-1]

for i in range(h-2,-1,-1):
    a2[i] += (a2[i+1]+1)*b[i+1]

for i in range(1,w):
    a3[:, i] += (a3[:, i-1]+1)*b[:, i-1]

for i in range(w-2,-1,-1):
    a4[:, i] += (a4[:, i+1]+1)*b[:, i+1]

#print(a1,a2,a3,a4)

answer = ( (a1+a2+a3+a4)*b ).max()

print(answer+1)

Submission status: Accepted

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

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

# def ok(i,j,houkou, count):
#     if i==h or j==w:
#         return count
#     elif s[i][j]=='#':
#         return count
#     elif houkou=='yoko':
#         return ok(i,j+1,houkou,count+1)
#     else:
#         return ok(i+1,j,houkou,count+1)

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

count=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                yoko[i][j-k-1]=count
            count=0
    if count>0:
        for k in range(count):
            yoko[i][j-k]=count
        count=0
# print(yoko)


for j in range(w):
    for i in range(h):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                tate[i-k-1][j]=count
            count=0
    if count>0:
        for k in range(count):
            tate[i-k][j]=count
        count=0

# print(tate)

ans=0
for i in range(h):
    for j in range(w):
        if ans<yoko[i][j]+tate[i][j]-1:
            ans=yoko[i][j]+tate[i][j]-1
print(ans)

Submission status: Accepted

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][i])


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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)
def dmatprint(mat):

    if debug == True:
        for row in mat:
            for col in row:
                print("{0:2d} ".format(col), end="")
            print("")
        print("")

def solve():
    H, W = map(int, input().split())
    s_arr = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        s_row = input()
        for w in range(W):
            if s_row[w] == ".":
                s_arr[h][w] = 0
            else:
                s_arr[h][w] = 1

    h_count = [[-1 for w in range(W)] for h in range(H)]
    w_count = [[-1 for w in range(W)] for h in range(H)]

    # w_countを埋める
    for h in range(H):
        row = s_arr[h]
        clearFlag = True
        for w, s in enumerate(row):
            if clearFlag:
                start = w
                end = w
            if s == 0:
                end = w
                clearFlag = False
            else:
                if clearFlag:
                    h_count[h][w] = -1
                else:
                    for iw in range(start, end+1):
                        w_count[h][iw] = end - start + 1
                clearFlag = True
        if clearFlag == False:
            for iw in range(start, max(end + 1, W)):
                w_count[h][iw] = end - start + 1

    # h_countを埋める
    for w in range(W):
        col = [row[w] for row in s_arr]
        clearFlag = True
        for h, s in enumerate(col):
            if clearFlag:
                start = h
                end = h
            if s == 0:
                end = h
                clearFlag = False
            else:
                if clearFlag:
                    h_count[h][w] = -1
                else:
                    for ih in range(start, end+1):
                        h_count[ih][w] = end - start + 1
                clearFlag = True
        if clearFlag == False:
            for ih in range(start, max(end+1, H)):
                h_count[ih][w] = end - start + 1

    dmatprint(h_count)
    dmatprint(w_count)
    mx_ans = 0
    for h in range(H):
        for w in range(W):
            if s_arr[h][w] == 0:
                ans = h_count[h][w] + w_count[h][w] - 1
                if ans >= mx_ans:
                    mx_ans = ans

    print(mx_ans)
    dmatprint(s_arr)
solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
import numpy

def main():
    H, W = LI()
    S = []
    for i in range(H):
        S.append(list(SI()))
    S = (numpy.array(S) == '.')
    L = numpy.zeros((H, W), dtype=int)
    R = numpy.zeros((H, W), dtype=int)
    T = numpy.zeros((H, W), dtype=int)
    B = numpy.zeros((H, W), dtype=int)
    for i in range(H):
        L[i] = (L[i - 1] + 1) * S[i]
        R[-1 - i] = (R[-i] + 1) * S[-1 - i]
    for i in range(W):
        T[:, i] = (T[:, i - 1] + 1) * S[:, i]
        B[:, -1 - i] = (B[:, -i] + 1) * S[:, -1 - i]
    ans = numpy.max(L + R + T + B) - 3
    return ans

print(main())

Submission status: Accepted

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

S_h1 = [[0]*(W+1) for i in range(H)]
S_w1 = [[0]*(H+1) for i in range(W)]
S_h2 = [[0]*(W+1) for i in range(H)]
S_w2 = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h1[y][x] = 0
            S_w1[x][y] = 0
        else:
            S_h1[y][x] += S_h1[y][x-1]+1
            S_w1[x][y] += S_w1[x][y-1]+1

for x in range(W-1,-1,-1):
    for y in range(H-1,-1,-1):
        if S[y][x] == '#':
            S_h2[y][x] = 0
            S_w2[x][y] = 0
        else:
            S_h2[y][x] += S_h2[y][x+1]+1
            S_w2[x][y] += S_w2[x][y+1]+1

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(ans,S_h1[y][x]+S_h2[y][x]+S_w1[x][y]+S_w2[x][y]-3)
 
print(ans)

Submission status: Accepted

Solution code:
# 5858744

H,W = map(int,input().split())
S = [input() for _ in range(H)]
L,R,D,U = [[[0]*W for _ in range(H)] for i in range(4)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            L[h][w] = L[h][w-1]+1
            U[h][w] = U[h-1][w]+1
        if S[h][W-1-w] == '.':
            R[h][-w-1] = R[h][-w]+1
        if S[H-1-h][w] == '.':
            D[-h-1][w] = D[-h][w]+1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(ans,L[h][w]+U[h][w]+R[h][w]+D[h][w]-3)

print(ans)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
Hs = [[0] * W for i in range(H)]
Vs = [[0] * W for i in range(H)]
 
Ss = [0] * H
for i in range(H):
    Ss[i] = input()
 
for i in range(H):
    s = 0
    e = 0
    c = 0
    for k in range(W):
        if Ss[i][k] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Hs[i][s + m] = c
            s = e + 1
            c = 0
    e = W
    for m in range(e - s):
        Hs[i][s + m] = c
# 縦
for i in range(W):
    s = 0
    e = 0
    c = 0
    for k in range(H):
        if Ss[k][i] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Vs[s + m][i] = c
            s = e + 1
            c = 0
    e = H
    for m in range(e - s):
        Vs[s + m][i] = c
 
maxv = 0
for i in range(H):
    for k in range(W):
        t = Hs[i][k] + Vs[i][k] - 1
        if t > maxv:
            maxv = t
print(maxv)

Submission status: Accepted

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

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

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

count=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#' or j+1==w:
            for k in range(count):
                yoko[i][j-k-1]=count
            count=0

# print(yoko)


for j in range(w):
    for i in range(h):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#' or i+1==h:
            for k in range(count):
                tate[i-k-1][j]=count
            count=0

# print(tate)

ans=0
for i in range(h):
    for j in range(w):
        if ans<yoko[i][j]+tate[i][j]-1:
            ans=yoko[i][j]+tate[i][j]-1
print(ans)

Submission status: Accepted

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

def cal(l):
    ll = list(l)
    ll.append('#')
    vol = [-100 for j in range(len(ll))]
    i = 0
    while i <= len(ll)-1:
        cnt = 0
        while (ll[i] != '#' and i <= len(ll)-1):
            cnt += 1
            i += 1

        for j in range(i-cnt,i):
            vol[j] = cnt

        i += 1
    return vol[:-1]

ver = [] # 縦
hori = [] # 横
fmap = []

for h in range(H):
    l = list(input())
    hori.append(cal(l))
    fmap.append(l)



new_map = []
for i in range(len(fmap[0])):
    mini_l = []
    for j in range(len(fmap)):
        mini_l.append(fmap[j][i])
    new_map.append(mini_l)

fmap = new_map    

for w in range(W):
    ver.append(cal(fmap[w]))

ans = 0

for h in range(H):
    for w in range(W):
        s = hori[h][w]+ver[w][h]
        if s > ans:
            ans = s
print(ans-1)

Submission status: Accepted

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

# 4方向の累積和をとって計算する
Rs = [[0]*W for i in range(H)]
Ls = [[0]*W for i in range(H)]
Ds = [[0]*W for i in range(H)]
Us = [[0]*W for i in range(H)]

for i in range(H):
    tmp = 0
    # 順方向(左にどれだけ伸びてるか)
    for j in range(W):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Ls[i][j] = tmp
    tmp = 0
    # 逆方向(右にどれだけ伸びてるか)
    for j in reversed(range(W)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Rs[i][j] = tmp

# 行列転置 順番逆にするだけ
for j in range(W):
    tmp = 0
    # 順方向 上にどれだけ伸びているか
    for i in range(H):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Us[i][j] = tmp
    tmp = 0
    # 順方向 下にどれだけ伸びているか
    for i in reversed(range(H)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Ds[i][j] = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': 
            continue
        # 上下左右に伸びた数を重なっている部分引く
        tmp = Rs[i][j] + Ls[i][j] + Ds[i][j] + Us[i][j] - 3
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
h,w = map(int,input().split())
s = []
for i in range(h):
        a = [i for i in input().rstrip()]
        s.append(a)
ans = [[1]*w for i in range(h)]
res = 0
for i in range(h):
        res = 0
        for j in range(w):
                if s[i][j] == "." and 0<j and s[i][j-1] == ".":
                        res = res +1
                if s[i][j] == ".":
                        ans[i][j] += res
                else:
                        res = 0

res = 0
for i in range(h):
        res = 0
        for j in range(w-1,-1,-1):
                if s[i][j] == "." and w-1>j and s[i][j+1] == ".":
                        res = res +1
                if s[i][j] == ".":
                        ans[i][j] += res
                else:
                        res = 0
res = 0
for i in range(w):
        res = 0
        for j in range(h-1,-1,-1):
                if s[j][i] == "." and h-1>j and s[j+1][i] == ".":
                        res = res+1
                if s[j][i] == ".":
                        ans[j][i] += res
                else:
                        res = 0
res = 0
for i in range(w):
        res = 0
        for j in range(h):
                if s[j][i] == "." and 0<j and s[j-1][i] == ".":
                        res = res +1
                if s[j][i] == ".":
                        ans[j][i] += res           
                else:
                        res = 0  
ans2 = 0
for i in range(h):
        for j in range(w):
                ans2 = max(ans2,ans[i][j])
print(ans2)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
T=[["#"]*(w+2)]
T.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
T.append(["#"]*(w+2))
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(1,h+1):
  for j in range(1,w+1):
    if T[i][j]==".":
      if j==1:
        L[i-1][j-1]=1
      else:
        L[i-1][j-1]=L[i-1][j-2]+1
      if i==1:
        U[i-1][j-1]=1
      else:
        U[i-1][j-1]=U[i-2][j-1]+1
    if T[h+1-i][w+1-j]==".":
      if j==1:
        R[h-i][w-j]=1
      else:
        R[h-i][w-j]=R[h-i][w-j+1]+1
      if i==1:
        D[h-i][w-j]=1
      else:
        D[h-i][w-j]=D[h-i+1][w-j]+1
ans=0
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: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
grid = [list(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 h in range(H):
    for w in range(W):
        if grid[h][w] ==".":
            L[h][w] = L[h][w-1]+1
            U[h][w] = U[h-1][w]+1
        if grid[h][W-w-1]==".":
            R[h][-w-1]=R[h][-w]+1
        if grid[H-h-1][w] ==".":
            D[-h-1][w] = D[-h][w]+1
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] =="#":
            ans = max(ans,L[i][j]+R[i][j]+D[i][j]+U[i][j])
        else:
            ans = max(ans,L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)