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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	H,W = inputMap()
	S = []
	for i in range(H):
		tmp = inputStr()
		S.append(list(tmp))

	part_x = []
	x = 0
	for i in range(H):
		tmp = []
		for j in range(W):
			if S[i][j] == "#":
				tmp.append(x)
				x = 0
				continue
			x += 1
		tmp.append(x)
		x = 0
		part_x.append(tmp)

	part_y = []
	x = 0
	for j in range(W):
		tmp = []
		for i in range(H):
			if S[i][j] == "#":
				tmp.append(x)
				x = 0
				continue
			x += 1
		tmp.append(x)
		x = 0
		part_y.append(tmp)

	#print(part_x)
	#print(part_y)
	ans = 0
	mem = [0 for i in range(W)]
	index_xx = 0
	index_xy = 0
	index_yx = 0
	index_yy = 0
	for i in range(H):
		index_yx = 0
		for j in range(W):
			index_yx += 1
			if S[i][j] == "#":
				index_xx += 1
				mem[j] += 1
				continue
			tmp = part_x[index_xy][index_xx] + part_y[index_yx-1][mem[j]]
			#print("{} {} {}".format(i,j,part_y[index_yx-1][mem[j]]))
			if ans < tmp:
				#print("{} {}".format(i,j))
				ans = tmp
		index_xx = 0
		index_xy += 1

	print(ans-1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
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 i in range(h):
  u[i, :] = (u[i-1]+1)*ar[i]
  d[-i-1, :] = (d[-i]+1)*ar[-i-1]

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    H, W = map(int, input().split())
    grid = [[_ for _ in 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 h in range(H):
        cur = 0
        for w in range(W):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            l[h][w] = cur

    for h in range(H):
        cur = 0
        for w in reversed(range(W)):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            r[h][w] = cur

    for w in range(W):
        cur = 0
        for h in range(H):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            u[h][w] = cur

    for w in range(W):
        cur = 0
        for h in reversed(range(H)):
            if grid[h][w] == '#':
                cur = 0
            else:
                cur += 1
            d[h][w] = cur

    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, r[h][w] + l[h][w] + u[h][w] + d[h][w] - 3)
    print(ans)


resolve()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
hdp=[[0]*w for _ in range(h)] # hdp[i][j]:i,jマスに明かりを置いた時のてらせる縦マス数
wdp=[[0]*w for _ in range(h)] # wdp[i][j]:i,jマスに明かりを置いた時のてらせる横マス数
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      continue
    if j>0 and wdp[i][j-1]>0:
      wdp[i][j]=wdp[i][j-1]
    else:
      for k in range(j,w):
        if s[i][k]=='#':
          break
        wdp[i][j]+=1
    if i>0 and hdp[i-1][j]>0:
      hdp[i][j]=hdp[i-1][j]
    else:
      for k in range(i,h):
        if s[k][j]=='#':
          break
        hdp[i][j]+=1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,hdp[i][j]+wdp[i][j]-1)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(lambda x:range(int(x)),input().split())
g=[[c=='.'for c in input()]for _ in h]
a=[[-3]*len(w)for _ in h]
for i in h:
  l=r=0
  for j in w: l=-~l*g[i][j]; a[i][j]+=l; r=-~r*g[i][~j]; a[i][~j]+=r
for i in w:
  d=u=0
  for j in h: d=-~d*g[j][i]; a[j][i]+=d; u=-~u*g[~j][i]; a[~j][i]+=u
print(max(a[i][j] for i in h for j in w))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
f=range
g=[[c=='.'for c in input()]for _ in f(h)]
a=[[-3]*w for _ in f(h)]
for i in f(h):
  l=r=0
  for j in f(w): l=-~l*g[i][j]; a[i][j]+=l; r=-~r*g[i][~j]; a[i][~j]+=r
for i in f(w):
  d=u=0
  for j in f(h): d=-~d*g[j][i]; a[j][i]+=d; u=-~u*g[~j][i]; a[~j][i]+=u
print(max(a[i][j] for i in f(h) for j in f(w)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
g=[[c=='.'for c in input()] for _ in range(h)]
a=[[-3]*w for _ in range(h)]
for i in range(h):
  l=r=0
  for j in range(w):
    l=-~l*g[i][j]; a[i][j]+=l
    r=-~r*g[i][-1-j]; a[i][-1-j]+=r
for i in range(w):
  d=u=0
  for j in range(h):
    d=-~d*g[j][i]; a[j][i]+=d
    u=-~u*g[-1-j][i]; a[-1-j][i]+=u
print(max(a[i][j] for i in range(h) for j in range(w)))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
f=lambda:[[0]*w for _ in range(h)]
g=[input() for _ in range(h)]
l,r=f(),f()
for i in range(h):
  lc=rc=0
  for j in range(w):
    if g[i][j]=='.': lc+=1; l[i][j]=lc
    else: lc=0
    if g[i][-1-j]=='.': rc+=1; r[i][-1-j]=rc
    else: rc=0
d,u=f(),f()
for i in range(w):
  dc=uc=0
  for j in range(h):
    if g[j][i]=='.': dc+=1; d[j][i]=dc
    else: dc=0
    if g[-1-j][i]=='.': uc+=1; u[-1-j][i]=uc
    else: uc=0
print(max(l[i][j]+r[i][j]+d[i][j]+u[i][j]-3 for i in range(h) for j in range(w)))

Submission status: Accepted

Solution code:
import numpy as np
 
H, W = map(int, input().split())
S_list = [list(input()) for _ in range(H)]
S_list=(np.array(S_list) ==".")*1
 
L = np.zeros((H, W), int) # i,jより左のランプをてらせる数
R = np.zeros((H, W), int)
U = np.zeros((H, W), int)
D = np.zeros((H, W), int)
 
for w in range(W):
    if w == 0: 
        L[:,w] = S_list[:,w] # 一番左であれば、Lは1, 他の行も同じ
        R[:,W-w-1] = S_list[:,W-w-1] # 一番右であれば、Rは1, 他の行も同じ
    else:
        L[:,w] = (L[:,w-1]+1) * S_list[:,w] # Lは一つ左のものに1を加えたもの, 他の行も同じ
        R[:,W-w-1] = (R[:,W-w]+1) * S_list[:,W-w-1] # Rは一つ右のものに1を加えたもの, 他の行も同じ
 
for h in range(H):
    if h == 0:
        U[h,:] = S_list[h,:]
        D[H-h-1,:] = S_list[H-h-1,:]
    else:
        U[h,:] = (U[h-1,:]+1) * S_list[h,:]
        D[H-h-1,:] = (D[H-h,:]+1) * S_list[H-h-1,:]
        
ans = max(np.max(L+R+U+D-3), 0) # 行列のH,Wの中で最大のものをとる
 
print(ans)

Submission status: Accepted

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

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

for i in range(h):
    if s[i][0] == ".":
        left[i][0] = 1
    if s[i][w-1] == ".":
        right[i][w-1] = 1

for j in range(w):
    if s[0][j] == ".":
        down[0][j] = 1
    if s[h-1][j] == ".":
        up[h-1][j] = 1
        
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                left[i][j] = left[i][j-1] + 1
            if i > 0:
                down[i][j] = down[i-1][j] + 1

for i in range(h)[::-1]:
    for j in range(w)[::-1]:
        if s[i][j] == ".":
            if i < h-1:
                up[i][j] = up[i+1][j] + 1
            if j < w-1:
                right[i][j] = right[i][j+1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        count = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        if ans < count:
            ans = count
print(ans)

Submission status: Accepted

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

for i in range(h):
    box = []
    a = 0
    for j in range(w):
        if s[i][j] == '.':
            box.append(j)
            a += 1
            if j == w-1:
                for k in range(len(box)):
                    ans[i][box[k]] += a
                box = []
                a = 0
        else:
            if j != 0 and len(box) >= 1:
                for k in range(len(box)):
                    ans[i][box[k]] += a
                box = []
                a = 0

for i in range(w):
    box = []
    a = 0
    for j in range(h):
        if s[j][i] == '.':
            box.append(j)
            a += 1
            if j == h-1:
                for k in range(len(box)):
                    ans[box[k]][i] += a
                box = []
                a = 0
        else:
            if j != 0 and len(box) >= 1:
                for k in range(len(box)):
                    ans[box[k]][i] += a
                box = []
                a = 0
aans = 0
for i in range(h):
    aans = max(aans,max(ans[i]))
print(aans-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int, input().split())
S=[]
for h in range(H):
    s=list(input())
    S.append(s)
S=np.array(S)
ruit=np.zeros((H,W))
ruit[0,:]=np.where(S[0,:]==".",1,0)
ruil=np.zeros((H,W))
ruil[:,0]=np.where(S[:,0]==".",1,0)
ruir=np.zeros((H,W))
ruir[:,-1]=np.where(S[:,-1]==".",1,0)
ruib=np.zeros((H,W))
ruib[-1,:]=np.where(S[-1,:]==".",1,0)

for h in range(1,H):
    nowt=np.where(S[h,:]==".",1,0)
    ruit[h,:]=(ruit[h-1,:]+nowt)*nowt

    nowb=np.where(S[-(h+1),:]==".",1,0)
    ruib[-(h+1),:]=(ruib[-h,:]+nowb)*nowb

for w in range(1,W):
    nowl=np.where(S[:,w]==".",1,0)
    ruil[:,w]=(ruil[:,w-1]+nowl)*nowl
    nowr=np.where(S[:,-(w+1)]==".",1,0)
    ruir[:,-(w+1)]=(ruir[:,-w]+nowr)*nowr
#print(ruir)
#print(ruil)
#print(ruib)
print(int((ruit+ruib+ruil+ruir-3).max()))

Submission status: Accepted

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

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

for i in range(h):
    current = 0
    for j in range(w):
        if grid[i][j] == '#':
            current = 0
        else:
            current += 1
        left[i][j] = current
    
for i in range(h):
    current = 0
    for j in range(w - 1, -1, -1):
        if grid[i][j] == '#':
            current = 0
        else:
            current += 1
        right[i][j] = current

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

for i in range(w):
    current = 0
    for j in range(h - 1, -1, -1):
        if grid[j][i] == '#':
            current = 0
        else:
            current += 1
        down[j][i] = current

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

print(ans)

Submission status: Accepted

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

yoko = [[0] * w for i in range(h)]
for i in range(h):
    tmp = 0
    l = 0
    for j in range(w + 1):
        if j == w or s[i][j] == "#":
            for k in range(l, j):
                yoko[i][k] = tmp
            l = j + 1
            tmp = 0
        else:
            tmp += 1
            
tate = [[0] * w for i in range(h)]
for j in range(w):
    tmp = 0
    l = 0
    for i in range(h + 1):
        if i == h or s[i][j] == "#":
            for k in range(l, i):
                tate[k][j] = tmp
            l = i + 1
            tmp = 0
        else:
            tmp += 1

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
s.append("#"*(w+2))
for i in range(h):
  s.append("#"+input()+"#")
s.append("#"*(w+2))
r=[[0]*(w+2) for i in range(h+2)]
l=[[0]*(w+2) for i in range(h+2)]
d=[[0]*(w+2) for i in range(h+2)]
u=[[0]*(w+2) for i in range(h+2)]

for i in range(1,h+1):
  for j in range(w+1,0,-1):
    if s[i][j]=="#":
      r[i][j]=0
    else:
      r[i][j]+=r[i][j+1]+1
# print(r)
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j]=="#":
      l[i][j]=0
    else:
      l[i][j]+=l[i][j-1]+1
# print(l)
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j]=="#":
      u[i][j]=0
    else:
      u[i][j]+=u[i-1][j]+1
# print(u)
for i in range(h+1,0,-1):
  for j in range(1,w+1):
    if s[i][j]=="#":
      d[i][j]=0
    else:
      d[i][j]+=d[i+1][j]+1
# print(d)
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    ans=max(r[i][j]+l[i][j]+u[i][j]+d[i][j]-3,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map_as(H, W, replace={'#': 1, '.': 0}):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    ret = []
    ret.append([1] * (W + 2))
    for _ in range(H):
        ret.append([1] + [replace[s] for s in read()[:-1]] + [1])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    ret.append([1] * (W + 2))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc129/tasks/abc129_d
# すべてのマスにおいてみてって感じかな
# 2000*2000だとマスにおいたときにO(1)で何マス照らせるか取得したい
# 前処理で横/縦に何マス伸びてるか記録しておけばいいのでは？

H, W = read_ints()
S = read_map_as(H, W)

yoko = [[-1] * (W + 2) for _ in ra(H + 2)]
tate = [[-1] * (W + 2) for _ in ra(H + 2)]

# 横の前処理
for i in ra(H + 2):
    fillranges = []
    pre_0 = 0
    for j in ra(1, W + 2):
        if S[i][j] == 1:
            fillranges.append((pre_0, j))
            pre_0 = j
    for l, r in fillranges:
        for j in range(l, r):
            yoko[i][j] = r - l - 1

# 縦の前処理
for j in ra(W + 2):
    fillranges = []
    pre_0 = 0
    for i in ra(1, H + 2):
        if S[i][j] == 1:
            fillranges.append((pre_0, i))
            pre_0 = i
    for l, r in fillranges:
        for i in range(l, r):
            tate[i][j] = r - l - 1

# from pprint import pprint
# pprint(tate)
# pprint(yoko)
ans = 0
for i, j in product(range(1, H + 1), range(1, W + 1)):
    ans = max(yoko[i][j] + tate[i][j] - 1, ans)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
for h in range(1,H+1):
    S[h] = '*' + input() + '*'

left = [[0]*(W+1) for _ in range(H+1)]
right = [[0]*(W+1) for _ in range(H+1)]
up = [[0]*(W+1) for _ in range(H+1)]
down = [[0]*(W+1) for _ in range(H+1)]

for h in range(1,H+1):
    for w in range(1,W+1):
        if S[h][w-1] in ['#','*'] or S[h][w]=='#':
            left[h][w] = 0
        else:
            left[h][w] = left[h][w-1]+1

for h in range(1,H+1):
    for w in range(W,0,-1):
        if S[h][w+1] in ['#','*'] or S[h][w]=='#':
            right[h][w] = 0
        else:
            right[h][w] = right[h][w+1]+1

for w in range(1,W+1):
    for h in range(1,H+1):
        if S[h-1][w] in ['#','*'] or S[h][w]=='#':
            up[h][w] = 0
        else:
            up[h][w] = up[h-1][w]+1

for w in range(1,W+1):
    for h in range(H,0,-1):
        if S[h+1][w] in ['#','*'] or S[h][w]=='#':
            down[h][w] = 0
        else:
            down[h][w] = down[h+1][w]+1
ans = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        ans = max(ans,left[h][w]+right[h][w]+up[h][w]+down[h][w]+1)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
S = np.array(['#' * (W+2)] + ['#' + sr() + '#' for _ in range(H)] + ['#' * (W+2)])
S = np.array([[x == '.' for x in row] for row in S])
S = S.astype(np.int16)
left = S.copy(); right = S.copy(); up = S.copy(); down = S.copy()
for i in range(1, W+1):
    left[:, i] += left[:, i-1]
    left[:, i] *= S[:, i]
for i in range(W, 0, -1):
    right[:, i] += right[:, i+1]
    right[:, i] *= S[:, i]
for i in range(1, H+1):
    up[i, :] += up[i-1, :]
    up[i, :] *= S[i, :]
for i in range(H, 0, -1):
    down[i, :] += down[i+1, :]
    down[i, :] *= S[i, :]

answer = (left + right + up + down - 3).max()
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]

imoslr = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
  c = 0
  prev = 0
  for j in range(W):
    if S[i][j] == "#":
      imoslr[i][j] -= c
      imoslr[i][prev] += c
      prev = j + 1
      c = 0
    else: c += 1
  imoslr[i][prev] += c
  for j in range(W): imoslr[i][j + 1] += imoslr[i][j]

imosud = [[0] * (W) for _ in range(H + 1)]
for i in range(W):
  c = 0
  prev = 0
  for j in range(H):
    if S[j][i] == "#":
      imosud[j][i] -= c
      imosud[prev][i] += c
      prev = j + 1
      c = 0
    else: c += 1
  imosud[prev][i] += c
  for j in range(H): imosud[j + 1][i] += imosud[j][i]

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

Submission status: Accepted

Solution code:
def resolve():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    hs = [[0]*w for _ in range(h)]
    ws = [[0]*w for _ in range(h)]

    for i in range(h):
        cums = 0
        for j in range(w):
            if s[i][j] == "#":
                cums = 0
                ws[i][j] = 0
            else:
                cums += 1
                ws[i][j] = cums
        for j in reversed(range(w-1)):
            if ws[i][j+1] != 0 and ws[i][j] != 0:
                ws[i][j] = ws[i][j+1]

    for i in range(w):
        cums = 0
        for j in range(h):
            if s[j][i] == "#":
                cums = 0
                hs[j][i] = 0
            else:
                cums += 1
                hs[j][i] = cums
        for j in reversed(range(h-1)):
            if hs[j+1][i] != 0 and hs[j][i] != 0:
                hs[j][i] = hs[j+1][i]

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    """まずは縦に何連続かだけ計測"""
    dp = [[0] * W for _ in range(H)]
    # 0列目
    for j in range(W):
        if S[0][j] != '#':
            dp[0][j] = 1
    # dp-part
    for i in range(1, H):
        for j in range(W):
            if S[i][j] != '#':
                dp[i][j] = dp[i - 1][j] + 1
            else:
                num = dp[i - 1][j]
                for k in range(num):
                    dp[i - 1 - k][j] = num
    # last-line
    for j in range(W):
        num = dp[H - 1][j]
        for k in range(num):
            dp[H - 1 - k][j] = num
    
    """次に横に何連続かを計測"""

    dp2 = [[0] * W for _ in range(H)]
    # 0列目
    for i in range(H):
        if S[i][0] != '#':
            dp2[i][0] = 1
    # dp-part
    for j in range(1, W):
        for i in range(H):
            if S[i][j] != '#':
                dp2[i][j] = dp2[i][j - 1] + 1
            else:
                num = dp2[i][j - 1]
                for k in range(num):
                    dp2[i][j - 1 - k] = num
    # last-line
    for i in range(H):
        num = dp2[i][W - 1]
        for k in range(num):
            dp2[i][W - 1 - k] = num
    
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, dp[i][j] + dp2[i][j] - 1)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

H, W = map(int, input().split())

grid = []

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

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

answer = 0

for h in range(H):
  for w in range(W):
    answer = max(answer, count_h[h][w] + count_w[h][w] - 1)

print(answer)

Submission status: Accepted

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

l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if field[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 reversed(range(w)):
        if field[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 field[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 reversed(range(h)):
    for j in range(w):
        if field[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):
        tmp=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

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

Left  = [[0] * 2100 for _ in range(2100)]
Right = [[0] * 2100 for _ in range(2100)]
Up    = [[0] * 2100 for _ in range(2100)]
Down  = [[0] * 2100 for _ in range(2100)]

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

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

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

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

cnt = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			continue
		cnt = max(cnt, Left[i][j] + Right[i][j] + Up[i][j] + Down[i][j] - 3)

print(cnt)