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:
# -*- coding: utf-8 -*-


def main():
    h, w = map(int, input().split())
    grids = [list(input()) for _ in range(h)]
    up = [[1 for __ in range(w)] for _ in range(h)]
    down = [[1 for __ in range(w)] for _ in range(h)]
    left = [[1 for __ in range(w)] for _ in range(h)]
    right = [[1 for __ in range(w)] for _ in range(h)]
    ans = 0

    for i in range(h - 1, -1, -1):
        for j in range(w):
            if (grids[i][j] == '.') and (i < h - 1):
                up[i][j] = up[i + 1][j] + 1
            elif grids[i][j] == '#':
                up[i][j] = 0

    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (i > 0):
                down[i][j] = down[i - 1][j] + 1
            elif grids[i][j] == '#':
                down[i][j] = 0

    for i in range(h):
        for j in range(w - 1, -1, -1):
            if (grids[i][j] == '.') and (j < w - 1):
                left[i][j] = left[i][j + 1] + 1
            elif grids[i][j] == '#':
                left[i][j] = 0

    for i in range(h):
        for j in range(w):
            if (grids[i][j] == '.') and (j > 0):
                right[i][j] = right[i][j - 1] + 1
            elif grids[i][j] == '#':
                right[i][j] = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def solve():
    readline = sys.stdin.readline

    H, W = map(int, readline().split())
    C = [[i]*i for i in range(W+1)]
    rW = range(W); rH = range(H)
    S = [readline() for i in rH]
    P = [[0]*W for i in rH]
    for i in rH:
        p = -1
        Si = S[i]
        Pi = P[i]
        for j in rW:
            if Si[j] == '#':
                c = j - p - 1
                Pi[p+1:j] = C[c]
                p = j
        c = W - p - 1
        Pi[p+1:W] = C[c]

    def gen():
        U = [-1]*W
        V = [0]*W
        for i in rH:
            Si = S[i]; Pi = P[i]
            for j in rW:
                if Si[j] == '#':
                    yield V[j] + (i - U[j] - 1)
                    V[j] = 0
                    U[j] = i
                else:
                    V[j] = max(V[j], Pi[j])
        for u, v in zip(U, V):
            yield v + (H - u - 1)
    sys.stdout.write("%d\n" % (max(gen()) - 1))
solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np

h, w = list(map(int, input().split()))
field = np.array([[c == '.' for c in line.rstrip()] for line in sys.stdin], dtype=np.int32)
li, ri, ui, di = (field.copy() for _ in [0] * 4)

for i in range(1, h):
    ui[i] = (ui[i - 1] + 1) * field[i]
    di[h - i - 1] = (di[h - i] + 1) * field[h - i - 1]
field = field.T
li, ri = li.T, ri.T
for j in range(1, w):
    li[j] = (li[j - 1] + 1) * field[j]
    ri[w - j - 1] = (ri[w - j] + 1) * field[w - j - 1]
li, ri = li.T, ri.T
print((li + ri + ui + di).max() - 3)

Submission status: Accepted

Solution code:
import sys
import numpy as np

h, w = list(map(int, input().split()))
field = np.array([[c == '.' for c in line.rstrip()] for line in sys.stdin], dtype=np.int32)
li, ri, ui, di = (field.copy() for _ in [0] * 4)

for i in range(1, h):
    ui[i] = (ui[i - 1] + 1) * field[i]
    di[h - i - 1] = (di[h - i] + 1) * field[h - i - 1]
for j in range(1, w):
    li[:, j] = (li[:, j - 1] + 1) * field[:, j]
    ri[:, w - j - 1] = (ri[:, w - j] + 1) * field[:, w - j - 1]
print((li + ri + ui + di).max() - 3)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W = map(int,input().split())
grid = []
for i in range(H):
    S = input()
    grid.append(S)

#print(grid)
left = [[0 for i in range(W)] for j in range(H)]   #そのマスからあとどれだけ左にいったら壁かを表す
right = [[0 for i in range(W)] for j in range(H)]
up = [[0 for i in range(W)] for j in range(H)]
down = [[0 for i in range(W)] for j in range(H)]

#iは行、jは列を表す

for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == "#":
            cur = 0
        else:
            cur += 1
        left[i][j] = cur

for i in range(H):
    cur = 0
    for j in reversed(range(W)):
        if grid[i][j] == "#":
            cur = 0
        elif grid[i][j] == ".":
            cur += 1
        right[i][j] = cur

for j in range(W):       
    cur = 0
    for i in range(H):
        if grid[i][j] == "#":
            cur = 0
        else:
            cur += 1
        up[i][j] = cur

for j in range(W):       
    cur = 0
    for i in reversed(range(H)):
        if grid[i][j] == "#":
            cur = 0
        else:
            cur += 1
        down[i][j] = cur

res = 0
for i in range(H):
    for j in range(W):
        res = max([res, (left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3)])
print(res)

Submission status: Accepted

Solution code:
import numpy as np
import sys


def main():
    stream = sys.stdin
    buf = stream.buffer.readline()
    H, W = map(int, buf.split())
    buf = stream.buffer.read(H * (W + 1))
    arr = np.frombuffer(buf, dtype='B').reshape((H, W + 1))[:, : -1]
    a = (arr == ord('.'))
    L = np.empty((H, W), dtype='i4')
    R = np.empty((H, W), dtype='i4')
    T = np.empty((H, W), dtype='i4')
    B = np.empty((H, W), dtype='i4')
    T[0] = a[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * a[i]
    B[-1] = a[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * a[i]
    L[:, 0] = a[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * a[:, i]
    R[:, -1] = a[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * a[:, i]

    print((T + B + L + R - 3).max())


main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer

H,W = map(int,buf.readline().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'.').reshape((H,W+1))

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = np.where(x,0,-np.arange(L)) # 左の壁のindexの-1倍
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.where(x[::-1],0,np.arange(L)) # 逆順ソートした上で左の壁のindex
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

h, w = map(int, input().split())

up = np.zeros((h, w), dtype=int)
down = np.zeros((h, w), dtype=int)
right = np.zeros((h, w), dtype=int)
left = np.zeros((h, w), dtype=int)

map = np.array([list(input()) for i in range(h)]) == "."

for i in range(1, h):
    up[i] = (up[i-1] + 1) * map[i-1]
    down[h-1-i] = (down[h-i] + 1) * map[h-i]
for j in range(1, w):
    left[:,j] = (left[:,j-1] + 1) * map[:,j-1]
    right[:,w-1-j] = (right[:,w-j] + 1) * map[:,w-j]

print(((up+down+right+left+1) * map).max())

Submission status: Accepted

Solution code:
from subprocess import *
call(('pypy3','-c',"""
n,m = map(int,input().split())
ls = [[x for x in input() + '#'] for i in range(n)] + [['#']*(m+1)]
yokodp = [[0 for x in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    yoko = 0
    for j in range(m+1):
        if ls[i][j] == '#':
            yokodp[i][j] = yoko
            yoko = 0
        else:
            yoko += 1
for i in range(n,-1,-1):
    check = 0
    for j in range(m,-1,-1):
        if yokodp[i][j] != 0:
            check = yokodp[i][j]
        if ls[i][j] == '.':
            yokodp[i][j] = check
tatedp = [[0 for x in range(m+1)] for i in range(n+1)]            
for j in range(m+1):
    tate = 0
    for i in range(n+1):
        if ls[i][j] == '#':
            tatedp[i][j] = tate
            tate = 0
        else:
            tate += 1
for j in range(m,-1,-1):
    for i in range(n,-1,-1):
        if tatedp[i][j] != 0:
            check = tatedp[i][j]
        if ls[i][j] == '.':
            tatedp[i][j] = check
ans = 0
for i in range(n):
    for j in range(m):
        if ls[i][j] == '.':
            ans = max(ans,tatedp[i][j] + yokodp[i][j] - 1)
print(ans)
"""))

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
h,*s=open(0)
h,w=map(int,h.split())
r=range
a,b,c,d=[[[0]*w for _ in r(h)]for i in r(4)]
for i in r(h*w):
    i,j=i//w,i%w
    a[i][j]=-~a[i][j-1]*(s[i][j]=='.')
    b[i][~j]=-~b[i][-j]*(s[i][-j-2]=='.')
    c[i][j]=-~c[i-1][j]*(s[i][j]=='.')
    d[~i][j]=-~d[-i][j]*(s[~i][j]=='.')
print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in r(h)for j in r(w)))
"""))

Submission status: Accepted

Solution code:
import sys
import numpy as np


def solve(field):
    idx = np.arange(field.size).reshape(field.shape)
    field_idx = field * idx
    li = np.maximum.accumulate(field_idx, axis=1)
    ui = np.maximum.accumulate(field_idx, axis=0)

    field_idx += (field ^ 1) * field.size
    ri = np.fliplr(np.minimum.accumulate(np.fliplr(field_idx), axis=1))
    di = np.flipud(np.minimum.accumulate(np.flipud(field_idx), axis=0))
    return (ri - li + (di - ui) // field.shape[1]).max() - 3


h, w = list(map(int, input().split()))
h2, w2 = h + 2, w + 2
field = np.ones((h2, w2), dtype=np.int32)
field[1:h + 1, 1:w + 1] = [[c == '#' for c in line.rstrip()] for line in sys.stdin]
print(solve(field))

Submission status: Accepted

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer

H,W = map(int,buf.readline().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'.').reshape((H,W+1))

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = -np.arange(L) # 左の壁のindexの-1倍
  left_zero[x] = 0
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.arange(L) # 逆順ソートした上で左の壁のindex
  right_zero[x[::-1]] = 0
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Submission status: Accepted

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

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

    for i in range(H):
        for j in range(W):
            # 上方向
            if i > 0:
                if S[i - 1][j] == '#':
                    U[i][j] = 0
                else:
                    U[i][j] = U[i - 1][j] + 1
            
            # 左方向
            if j > 0:
                if S[i][j - 1] == '#':
                    L[i][j] = 0
                else:
                    L[i][j] = L[i][j - 1] + 1
    
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            # 下方向
            if i < H - 1:
                if S[i + 1][j] == '#':
                    D[i][j] = 0
                else:
                    D[i][j] = D[i + 1][j] + 1
            
            # 右方向
            if j < W - 1:
                if S[i][j + 1] == '#':
                    R[i][j] = 0
                else:
                    R[i][j] = R[i][j + 1] + 1

    res = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != '#':
                res = max(res, U[i][j] + D[i][j] + R[i][j] + L[i][j])
    
    print(res + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '.')

L = grid.size

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = x.T
  x = np.ravel(x) # to 1D array
  
  left_zero = -np.arange(L) # 左の壁のindexの-1倍
  left_zero[x] = 0
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.arange(L) # 逆順ソートした上で左の壁のindex
  right_zero[x[::-1]] = 0
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y -= right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()+2*L-5
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '.')

L = grid.size
a = np.arange(L)

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  
  left_zero = -a.copy() # 左の壁のindexの-1倍
  left_zero[x] = 0
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = a.copy() # 逆順ソートした上で左の壁のindex
  right_zero[x[::-1]] = 0
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '.')

# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = -np.arange(L) # 左の壁のindexの-1倍
  left_zero[x] = 0
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.arange(L) # 逆順ソートした上で左の壁のindex
  right_zero[x[::-1]] = 0
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Submission status: Accepted

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

# 横
A = [[-10000] * W for i in range(H)]
B = [[-10000] * W for i in range(H)]

for i in range(H):
    jj = 0
    s = 0
    for j in range(W+1):
        if j == W or S[i][j] == '#':
            for x in range(jj, j):
                A[i][x] = s
            s = 0
            jj = j + 1
        else:
            s += 1


for j in range(W):
    ii = 0
    s = 0
    for i in range(H+1):
        if i == H or S[i][j] == '#':
            for y in range(ii, i):
	            B[y][j] = s
            s = 0
            ii = i + 1
        else:
            s += 1

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

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)

Submission status: Accepted

Solution code:
import numpy as np
 
H, W = map(int, input().split())
#mapの入力
mymap = [] 
for i in range(H):
    mymap.append(list(input()))

#探索可能性をブーリアン表記
mymap = (np.array(mymap) == ".")
  
L = np.zeros((H, W), dtype=int) #左側から探索した場合の配列
R = np.zeros((H, W), dtype=int) #右側から探索した場合の配列
U = np.zeros((H, W), dtype=int) #上側から探索した場合の配列
D = np.zeros((H, W), dtype=int) #下側から探索した場合の配列

#列ごとに左から
for j in range(W):
  if j == 0: #左端
    L[:, j] = mymap[:, j] #true = 1, false = 0
  else:
    L[:, j] = (L[:, j - 1] + 1) * mymap[:, j] #trueの場合は1つ左の列の値を加算しながら

#列ごとに右から
for j in range(W - 1, -1, -1): #(引数：開始数，終了数，加算数）
  if j >= W - 1: #右端
    R[:, j] = mymap[:, j]
  else:
    R[:, j] = (R[:, j + 1] + 1) * mymap[:, j] 

#行ごとに上から
for i in range(H):
  if i <= 0: #上端
    U[i, :] = mymap[i, :]
  else:
    U[i, :] = (U[i - 1, :] + 1) * mymap[i, :]

#行ごとに下から
for i in range(H - 1, -1, -1):
  if i >= H - 1: #下端
    D[i, :] = mymap[i, :]
  else:
    D[i, :] = (D[i + 1, :] + 1) * mymap[i, :]

#総和から重複分(=3)の差をとって，最大値を出力
print(np.max(L + R + U + D - 3))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

h, w = map(int, input().split())
map_list = [[0 if s == '#' else 1 for s in input()[:-1]] for _ in range(h)]

h_map = []
for h_list in map_list:
    cnt = 0
    tmp_list = []
    for a in h_list:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    h_map.append(tmp_list)

w_map = []
for w_arr in [list(x) for x in zip(*map_list)]:
    cnt = 0
    tmp_list = []
    for a in w_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    w_map.append(tmp_list)
w_map = [list(x) for x in zip(*w_map)]
max_l = 0
for h_list, w_list in zip(h_map, w_map):
    for h_num, w_num in zip(h_list, w_list):
        max_l = max(max_l, h_num + w_num)
print(max_l - 1)

Submission status: Accepted

Solution code:
import numpy as np
h, w = map(int, input().split())
table = np.array([list(input())for _ in range(h)]) == '.'

d = np.zeros((h, w), dtype = int)
u = np.zeros((h, w), dtype = int)
r = np.zeros((h, w), dtype = int)
l = np.zeros((h, w), dtype = int)

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

Submission status: Accepted

Solution code:
from itertools import takewhile

# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

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

Submission status: Accepted

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

U=np.zeros((H,W), dtype=int)
D=np.zeros((H,W), dtype=int)
R=np.zeros((H,W), dtype=int)
L=np.zeros((H,W), dtype=int)

for i in range(H):
    if i==0:
        U[i,:]=S[i,:]
    else:
        U[i,:]=(U[i-1,:]+1)*S[i,:]

for i in range(H-1,-1,-1):
    if i==H-1:
        D[i,:]=S[i,:]
    else:
        D[i,:]+=(D[i+1,:]+1)*S[i,:]

for i in range(W):
    if i==0:
        L[:,i]=S[:,i]
    else:
        L[:,i]+=(L[:,i-1]+1)*S[:,i]
        
for i in range(W-1,-1,-1):
    if i==W-1:
        R[:,i]=S[:,i]
    else:
        R[:,i]+=(R[:,i+1]+1)*S[:,i]
    
print(np.max(U+D+R+L-3))

Submission status: Accepted

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

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

for i in range(h):
    p=0
    for j in range(w):
        if s[i][j]=="#" or j==w-1:
            if s[i][j]==".":
                for k in range(p):
                    yoko[i][j-k-1]+=p+1
                yoko[i][j]+=p+1
            else:
                for k in range(p):
                    yoko[i][j-k-1]+=p
            p=0
        elif s[i][j]==".":
            p+=1
for i in range(w):
    p=0
    for j in range(h):
        if s[j][i]=="#" or j==h-1:
            if s[j][i]==".":
                for k in range(p):
                    tate[j-k-1][i]+=p+1
                yoko[j][i]+=p+1
            else:
                for k in range(p):
                    tate[j-k-1][i]+=p
            p=0
        elif s[j][i]==".":
            p+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,yoko[i][j]+tate[i][j]-1)

print(ans)

Submission status: Accepted

Solution code:
#   ABC129　D問題
H, W = map(int, input().split())    #   1 <= H, W <= 2000
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

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

start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            for i in range(start, stop):
                point_arr[y][i] += stop - start
            start = stop + 1
    for i in range(start, W):
        point_arr[y][i] += W - start


for x in range(W):  #   コードのコピペ禁止の原則に違反してるけど、改善方法が思いつかない問題
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            for i in range(start, stop):
                point_arr[i][x] += stop - start
            start = stop + 1
    for i in range(start, H):
        point_arr[i][x] += H - start

ans = 0
for i in range(H):
    for j in range(W):
        if ans < point_arr[i][j]:
            ans = point_arr[i][j]
ans -= 1
print(ans)
#   O(H*W)程度の計算量で十分高速だと思ってたのに、そうでもない問題
#   2019/06/10 現在未解決　PyPy使ったらどうなるのかやってみた。Numpy含まれてるからランタイムエラーになるのだろうか？

Submission status: Accepted

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

light_space = [[1 for i in range(w)] for j in range(h)]
max_light = 0
for i in range(w):
    light = -1
    light_right = -1
    for j in range(h):
        low_point = len(space)-j-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light

        if space[low_point][i] == "#":
            light_right = -1
            light_space[low_point][i] = 0
        else:
            light_right += 1
            light_space[low_point][i] += light_right

for j in range(h):
    light = -1
    light_right = -1
    for i in range(w):
        right_point = len(space[j])-i-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light
        
        if space[j][right_point] == "#":
            light_right = -1
            light_space[j][right_point] = 0
        else:
            light_right += 1
            light_space[j][right_point] += light_right

        max_light = max(max_light,light_space[j][right_point],light_space[j][i])


print(max_light)

Submission status: Accepted

Solution code:
import numpy as np
import sys


def get_data(stream):
    buf = b''
    b = stream.buffer.read(1)
    while b != b'\n':
        buf += b
        b = stream.buffer.read(1)
    H, W = map(int, buf.split())
    c = stream.buffer.read(H * (W + 1))
    arr = np.array(c.split())
    arr = np.frombuffer(arr, dtype='S1').reshape((H, W))
    return H, W, arr


def main():
    H, W, arr = get_data(sys.stdin)
    a = arr == b'.'
    L = np.empty((H, W), dtype='i8')
    R = np.empty((H, W), dtype='i8')
    T = np.empty((H, W), dtype='i8')
    B = np.empty((H, W), dtype='i8')
    T[0] = a[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * a[i]
    B[-1] = a[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * a[i]
    L[:, 0] = a[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * a[:, i]
    R[:, -1] = a[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * a[:, i]

    print((T + B + L + R - 3).max())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int32(h.split())
s=int32([[u>'#'for u in t]for t in s])
a,b,c,d=eval('copy(s),'*4)
for i in range(1,h+w):
 if i<w:a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
 if i<h:c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(amax(a+b+c+d)-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int32(h.split())
s=int32([[u>'#'for u in t]for t in s])
a,b,c,d=eval('copy(s),'*4)
for i in range(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in range(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(amax(a+b+c+d)-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int32(h.split())
r=range
s=int32([[u>'#'for u in t]for t in s])
a,b,c,d=eval('copy(s),'*4)
for i in r(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in r(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(int((a+b+c+d).max())-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int64(h.split())
r=range
s=int32([[u>'#'for u in t[:w]]for t in s])
a,b,c,d=eval('copy(s),'*4)
for i in r(1,w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in r(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(int((a+b+c+d).max())-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int64(h.split())
r=range
s=int32([[u>'#'for u in t[:w]]for t in s])
a,b,c,d=eval('s.copy(),'*4)
for i in r(1,w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in r(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(int((a+b+c+d).max())-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int64(h.split())
r=range
s=int64([[u>'#'for u in t[:w]]for t in s])
a,b,c,d=eval('zeros((h,w),"i"),'*4)
for i in r(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in r(h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(int((a+b+c+d).max())-3)

Submission status: Accepted

Solution code:
from numpy import*
h,*s=open(0)
h,w=int64(h.split())
r=range
s=array([list(t[:-1])for t in s])
a,b,c,d=eval('zeros((h,w),"i"),'*4)
for i in r(w):
    a[:,i]=-~a[:,i-1]*(s[:,i]>'#')
    b[:,~i]=-~b[:,-i]*(s[:,~i]>'#')
for i in r(h):
    c[i,:]=-~c[i-1,:]*(s[i,:]>'#')
    d[~i,:]=-~d[-i,:]*(s[~i,:]>'#')
print(int((a+b+c+d).max())-3)

Submission status: Accepted

Solution code:
#解説コードコピペです

import numpy as np
 
def solve():
    H, W = list(map(int, input().split()))
    grid = []
    for i in range(H):
        grid.append(list(input()))
    #print((np.array(grid) == ".") * 1) #行列演算 "." ならTrue そうでなければFalseの行列をつくる *1で1と0に変換
    grid = (np.array(grid) == ".") * 1  # ランプをおける:1, 障害物:0
 
    L = np.zeros((H,W), dtype=int) #0でうめつくした行列をつくる
    R = np.zeros((H,W), dtype=int)
    U = np.zeros((H,W), dtype=int)
    D = np.zeros((H,W), dtype=int)
    
    for j in range(W): #列単位で処理
        if j == 0:
            L[:, j] = grid[:, j]
        else:
            L[:, j] = (L[:, j-1] + 1) * grid[:, j] #gridでかけることで 障害物があったときにそのマスを0にする
    
    for j in range(W-1, -1, -1):
        if j == W-1:
            R[:, j] = grid[:, j]
        else:
            R[:, j] = (R[:, j+1] + 1) * grid[:, j]
 
    for i in range(H):
        if i == 0:
            U[i] = grid[i] * 1
        else:
            U[i] = (U[i-1] + 1) * grid[i]
    
    for i in range(H-1, -1, -1):
        if i == H-1:
            D[i] = grid[i]
        else:
            D[i] = (D[i+1] + 1) * grid[i]
 
    ans = np.max(L+R+U+D-3)
    print(ans)
 
 
if __name__ == "__main__": #ここはしらん
    solve()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in S:
    for j in range(W):
        if i[j]!='#' and j!=W-1:
            ans+=1
        elif i[j]!='#'and j==W-1 :
            for k in range(ans+1):
                i[j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in S_t:
    for j in range(H):
        if i[j]!='#' and j!=H-1:
            ans+=1
        elif i[j]!='#'and j==H-1 :
            for k in range(ans+1):
                i[j-k]+=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]+=ans
            ans=0
            i[j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)