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 numpy as np
h,w=list(map(int,input().split()))
s=[[i for i in input() ] for _ in range(h)]

l=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
r=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
u=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
d=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
for h_i in range(h):
    for w_i in range(w):
        rev_w=w-w_i-1
        rev_h=h-h_i-1
        if s[h_i][w_i]!="#" and w_i!=0:
            l[h_i][w_i]+=l[h_i][w_i-1]
        if s[h_i][rev_w]!="#" and w_i!=0:
            r[h_i][rev_w]+=r[h_i][rev_w+1]
        if s[h_i][w_i]!="#" and h_i!=0:
            u[h_i][w_i]+=u[h_i-1][w_i]
        if s[rev_h][w_i]!="#" and h_i!=0:
            d[rev_h][w_i]+=d[rev_h+1][w_i]
ans=0
for h_i in range(h):
    for w_i in range(w):
        tmp=l[h_i][w_i]+r[h_i][w_i]+u[h_i][w_i]+d[h_i][w_i]-3
        ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [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 h in range(H):
    for w in range(W):
        if S[h][w]==".":
            if h==0:D[h][w]=1
            else:D[h][w]=D[h-1][w]+1
            if w==0:R[h][w]=1
            else:R[h][w]=R[h][w-1]+1
for h in range(H-1,-1,-1):
    for w in range(W-1,-1,-1):
        if S[h][w]==".":
            if h==H-1:U[h][w]=1
            else:U[h][w]=U[h+1][w]+1
            if w==W-1:L[h][w]=1
            else:L[h][w]=L[h][w+1]+1

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

Submission status: Accepted

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

X = [[0] * W for _ in range(H)]
for i in range(H):
    start = 0
    cnt = 0
    for j in range(W):
        if s[i][j] == "." and j == W - 1:
            cnt += 1
            for k in range(start, W):
                if s[i][k] == ".":
                    X[i][k] = cnt
        elif s[i][j] == ".":
            cnt += 1
        elif s[i][j] == "#":
            for k in range(start, j):
                if s[i][k] == ".":
                    X[i][k] = cnt
            start = j
            cnt = 0

Y = [[0] * W for _ in range(H)]
for i in range(W):
    start = 0
    cnt = 0
    for j in range(H):
        if s[j][i] == "." and j == H - 1:
            cnt += 1
            for k in range(start, H):
                if s[k][i] == ".":
                    Y[k][i] = cnt
        elif s[j][i] == ".":
            cnt += 1
        elif s[j][i] == "#":
            for k in range(start, j):
                if s[k][i] == ".":
                    Y[k][i] = cnt
            start = j
            cnt = 0

XY = []
for i in range(H):
    for j in range(W):
        XY.append(X[i][j] + Y[i][j] - 1)

print(max(XY))

Submission status: Accepted

Solution code:
import numpy as np

h,w=map(int,input().split())
g = np.array([list(input()) for _ in range(h)])
g = np.where(g=='.',1,0)

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

for i in range(w):
  l[:,i] = (l[:,i-1]+1)*g[:,i]
  r[:,-i-1] = (r[:,-i]+1)*g[:,-i-1]

for i in range(h):
  u[i,:]=(u[i-1,:]+1)*g[i,:]
  d[-i-1,:]=(d[-i,:]+1)*g[-i-1,:]

print(np.max(l+r+u+d)-3)

Submission status: Accepted

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

data1=[[0 for i in range(0,W)] for i in range(0,H)]
data2=[[0 for i in range(0,W)] for i in range(0,H)]
for i in range(0,H):
    sequence=[]
    length=0
    for j in range(0,W):
        if S[i][j]=='.':
            sequence.append(j)
            length+=1
        else:
            for k in sequence:
                data1[i][k]=length
            sequence=[]
            length=0
    if sequence!=[]:
        for k in sequence:
            data1[i][k]=length

for i in range(0,W):
    sequence=[]
    length=0
    for j in range(0,H):
        if S[j][i]=='.':
            sequence.append(j)
            length+=1
        else:
            for k in sequence:
                data2[k][i]=length
            sequence=[]
            length=0
    if sequence!=[]:
        for k in sequence:
            data2[k][i]=length

ans=0
for i in range(0,H):
    for j in range(0,W):
        test=data1[i][j]+data2[i][j]-1
        if test>ans:
            ans=test
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(3000)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===
# input_num = getInputListInt()
#
# h = input_num[0]
# w = input_num[1]
#
# data=[]
# for i in range(h):
#     tmp = str(input())
#     tmp_list = list(tmp)
#     data.append(tmp_list)
#
# def saikiU(cnt, i, j):
#     if i < 0 or i > h-1: return cnt
#     if j < 0 or j > w-1: return cnt
#     if data[i][j] == "#": return cnt
#
#     return saikiU(cnt+1, i-1, j)
#
#
# def saikiD(cnt, i, j):
#     if i < 0 or i > h - 1: return cnt
#     if j < 0 or j > w - 1: return cnt
#     if data[i][j] == "#": return cnt
#
#     return saikiD(cnt + 1, i + 1, j)
#
# def saikiL(cnt, i, j):
#     if i < 0 or i > h - 1: return cnt
#     if j < 0 or j > w - 1: return cnt
#     if data[i][j] == "#": return cnt
#
#     return saikiL(cnt + 1, i, j-1)
#
# def saikiR(cnt, i, j):
#     if i < 0 or i > h - 1: return cnt
#     if j < 0 or j > w - 1: return cnt
#     if data[i][j] == "#": return cnt
#
#     return saikiR(cnt + 1, i, j+1)
#
#
# yoko_sum = [[0 for i in range(w)] for j in range(h)] #二次元の静的確保
# tate_sum = [[0 for i in range(w)] for j in range(h)] #二次元の静的確保
#
# for i in range(h):
#     for j in range(w):

import numpy as np
import sys

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

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


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

for i in range(W):
    L[:,i] = (L[:,i-1]+1)*S[:,i]
    R[:,-i-1] = (R[:,-i]+1)*S[:,-i-1]
for j in range(H):
    U[j,:] = (U[j-1,:]+1)*S[j,:]
    D[-j-1,:] = (D[-j,:]+1)*S[-j-1,:]

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

Submission status: Accepted

Solution code:
import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))

Submission status: Accepted

Solution code:
def main(): 
  import numpy as np 
  h,w=map(int,input().split())
  grid=np.array([list(input()) for i in range(h)])
  grid=np.where(grid=='.',1,0)
    
  left=np.zeros((h,w),dtype=np.int64)
  right=np.zeros((h,w),dtype=np.int64)
  up=np.zeros((h,w),dtype=np.int64)
  down=np.zeros((h,w),dtype=np.int64)
  
  for i in range(w):
    left[:,i]=(left[:,i-1]+1)*grid[:,i]
    right[:,-i-1]=(right[:,-i]+1)*grid[:,-i-1]
  for i in range(h):
    up[i]=(up[i-1]+1)*grid[i]
    down[-i-1]=(down[-i]+1)*grid[-i-1]
  
  print(np.max(left+right+up+down)-3)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W=map(int,input().split())
S=[input() for i in range(H)]
y=[[0]*W for i in range(H)]
t=[[0]*W for i in range(H)]
for i,s in enumerate(S):
    n=0
    c=0
    for j in range(W):
        if s[j]==".":
            c+=1
        else:
            for k in range(n,j):
                y[i][k]=c
            c=0
            n=j+1
    for k in range(n,W):
        y[i][k]=c
for i in range(W):
    n=0
    c=0
    for j in range(H):
        if S[j][i]==".":
            c+=1
        else:
            for k in range(n,j):
                t[k][i]=c
            c=0
            n=j+1
    for k in range(n,H):
        t[k][i]=c
a=0
for i in range(H):
    for j in range(W):
        if a<y[i][j]+t[i][j]:
            a=y[i][j]+t[i][j]
print(a-1)

Submission status: Accepted

Solution code:
import numpy as np

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

s=np.array(s)
s=np.where(s=='.',1,0)

L=np.zeros((h,w),dtype=np.int)
R=np.zeros((h,w),dtype=np.int)
U=np.zeros((h,w),dtype=np.int)
D=np.zeros((h,w),dtype=np.int)

for i in range(w):
 L[:,i]=(L[:,i-1]+1)*s[:,i]
 R[:,-i-1]=(R[:,-i]+1)*s[:,-i-1]
for i in range(h):
 U[i]=(U[i-1]+1)*s[i]
 D[-i-1]=(D[-i]+1)*s[-i-1]

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

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j 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)]
#Uを決める
for i in range(w):
    if grid[0][i] == '#':
        U[0][i] = 0
    else:
        U[0][i] = 1
for i in range(1,h):
    for j in range(w):
        if grid[i][j] == '#':
            U[i][j] = 0
        else:
            U[i][j] = U[i-1][j] + 1
 #Dを決める
for i in range(w):
    if grid[-1][i] == '#':
        D[-1][i] = 0
    else:
        D[-1][i] = 1
for i in range(h-2, -1,-1):
    for j in range(w):
        if grid[i][j] == '#':
            D[i][j] = 0
        else:
            D[i][j] = D[i+1][j] + 1
# R を決める
for i in range(h):
    if grid[i][-1] == '#':
        R[i][-1] = 0
    else:
        R[i][-1] = 1
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == '#':
            R[i][j] = 0
        else:
            R[i][j] = R[i][j+1] + 1
#Lを決める
for i in range(h):
    if grid[i][0] == '#':
        L[i][0] = 0
    else:
        L[i][0] = 1
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == '#':
            L[i][j] = 0
        else:
            L[i][j] = L[i][j-1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        #print("x:{} y:{} L:{} R:{} U:{} D:{}".format(j+1,i+1,L[i][j],R[i][j],U[i][j],D[i][j]))
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)

Submission status: Accepted

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

cnt_h = [0]*w
cnt_w=0
ans=0
for i in range(h):
    for j in range(w):
        now = l[i][j]
        if now=="#":
            cnt_w=0
            cnt_h[j]=0
            continue

        if cnt_w==0:
            for k in range(j,w):
                if l[i][k] != "#":
                    cnt_w+=1
                else:
                    break
        if cnt_h[j] == 0:
            for x in range(i,h):
                if l[x][j] != "#":
                    cnt_h[j]+=1
                else:
                    break

        sm = cnt_w + cnt_h[j]
        if ans < sm:
            ans=sm
    cnt_w=0
print(ans-1)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(input()))
G = np.array(S)
G = np.where(G == ".", 1, 0)

## 事前計算
## マスごとに、「そのマスにライトを設置した場合に照らせるマスの数」を上下左右の4配列で求める
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 w in range(1,W):
  L[:,w] = (L[:,w-1]+1)*(G[:,w-1])
for w in range(W-1,0,-1):
  R[:,w-1] = (R[:,w]+1)*(G[:,w])
for h in range(1,H):
  U[h] = (U[h-1]+1)*(G[h-1])
for h in range(H-1,0,-1):
  D[h-1] = (D[h]+1)*(G[h])

ans = np.max((L+R+U+D)*G)+1
print(ans)

Submission status: Accepted

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

hgrid = np.zeros((h, w), dtype="int")

for hi in range(h):
    hdot = np.array(grid[hi] == ".", dtype="int")
    hgrid[hi] = hgrid[hi-1] * hdot + hdot
    
for hi in range(h-2, -1, -1):
    hi_1 = np.minimum(hgrid[hi+1], hgrid[hi] * hgrid[hi+1])
    hgrid[hi] = np.maximum(hgrid[hi], hi_1)
    
wgrid = np.zeros((h, w), dtype="int")

for wi in range(w):
    wdot = np.array(grid[:, wi] == ".", dtype="int")
    wgrid[:, wi] = wgrid[:, wi-1] * wdot + wdot
    
for wi in range(w-2, -1, -1):
    wi_1 = np.minimum(wgrid[:, wi+1], wgrid[:, wi] * wgrid[:, wi+1])
    wgrid[:, wi] = np.maximum(wgrid[:, wi], wi_1)

print(np.max(wgrid + hgrid) - 1)

Submission status: Accepted

Solution code:
import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
grid = np.pad(grid, 1, mode='constant')

def main():
    cnt = np.zeros((h+2, w+2))
    cnt[grid == '.'] = np.inf
    
    l = cnt.copy()
    r = cnt.copy()
    u = cnt.copy()
    d = cnt.copy()

    for i in range(1, w+1):
        l[1:h+1, i] = np.minimum(l[1:h+1, i], l[1:h+1, i-1]+1)
        i = w + 1 - i
        r[1:h+1, i] = np.minimum(r[1:h+1, i], r[1:h+1, i+1]+1)
    
    for i in range(1, h+1):
        u[i, 1:w+1] = np.minimum(u[i, 1:w+1], u[i-1, 1:w+1]+1)
        i = h + 1 - i
        d[i, 1:w+1] = np.minimum(d[i, 1:w+1], d[i+1, 1:w+1]+1)
    
    res = np.maximum(l + r + u + d - 3, 0).astype(np.int64)
    return np.amax(res)

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

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split(' ')))
field = []
for i in range(h):
    field.append(input())
 
dp = []
for i in range(h):
    dp.append([(0, 0)] * w)
for i in range(h):
    for j in range(w):  # 2e3 * 2e3
        if field[i][j] == '#':
            x, y = 0, 0
        else:
            if i == j == 0:
               x, y = 1, 1
            else:
                y = (dp[i-1][j][0] + 1) if i-1 >= 0 else 1
                x = (dp[i][j-1][1] + 1) if j-1 >= 0 else 1
        dp[i][j] = (y, x)
ans = 0 if field[0][0] == '#' else 1  
 
for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
        if field[i][j] != '#':
            y = dp[i+1][j][0] if i+1 < h else dp[i][j][0]
            x = dp[i][j+1][1] if j+1 < w else dp[i][j][1]
            dp[i][j] = (max(dp[i][j][0], y), max(dp[i][j][1], x))
        ans = max(dp[i][j][0] + dp[i][j][1] - 1, ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    H,W = map(int,input().split())
    S = [[1 if s == "." else 0 for s in input()] for _ in range(H)]

    if H == 1:
        for w in range(1,W):
            if S[0][w] and S[0][w - 1]:
                S[0][w] += S[0][w - 1]
        print(max(S[0]))
        return
    if W == 1:
        ans = 0
        for h in range(1,H):
            if S[h][0] and S[h-1][0]:
                S[h][0] += S[h - 1][0]
                ans = max(ans,S[h][0])
        print(ans)
        return


    R = [[0]*W for _ in range(H)]
    L = [[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(1,W - 1):
            if S[h][w] and S[h][w - 1]:
                L[h][w] += L[h][w - 1] + 1
            if S[h][W - w] and S[h][W - w - 1]:
                R[h][W - w - 1] += R[h][W - w] + 1
        if S[h][W -1] and S[h][W - 2]:
            L[h][W - 1] += L[h][W - 2] + 1
        if S[h][0] and S[h][1]:
            R[h][0] += R[h][1] + 1
    for w in range(W):
        for h in range(1,H-1):
            if S[h-1][w] and S[h][w]:
                U[h][w] += U[h-1][w] + 1
            if S[H - h][w] and S[H - h - 1][w]:
                D[H - h - 1][w] += D[H - h][w] + 1
        if S[H - 1][w] and S[H - 2][w]:
            D[H - 1][w] += D[H-2][w] + 1
        if S[0][w] and S[1][w]:
            U[0][w] += U[1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,U[h][w] + D[h][w] + R[h][w] + L[h][w])
    print(ans + 1)
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    NEG = -10**6
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    T = [[NEG] * W for _ in range(H)]
    for w in range(W):
        b = NEG
        for h in range(H):
            if S[h][w] == '.':
                if b == NEG:
                    b = h
            else:
                if b != NEG:
                    for j in range(b, h):
                        T[j][w] = h - b
                    b = NEG
        if b != NEG:
            for j in range(b, h + 1):
                T[j][w] = h + 1 - b
    m = 0
    for s, t in zip(S, T):
        b = NEG
        for i in range(len(s)):
            if s[i] == '#':
                if b != NEG:
                    m = max(m, i - b - 1 + max(t[b:i]))
                    b = NEG
            else:
                if b == NEG:
                    b = i
        if b != NEG:
            m = max(m, i - b + max(t[b:i + 1]))
    print(m)

main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = []
for i in range(h):
  gridi = input()
  grid.append(gridi)
xcnt = [[0]*w for i in range(h)]
ycnt = [[0]*w for i in range(h)]
ans = -10**9
# print(grid, h, w)
for y in range(h):
  cnt = 0
  for x in range(w-1):
    if grid[y][x] == "#":
      cnt = 0
      continue
    if grid[y][x+1] == "#":
      xcnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[y][w-1] == ".":
    xcnt[y][w-1] = cnt + 1
# print(xcnt)
for y in range(h):
  for x in range(w-1):
    if grid[y][w-1-x] == "#":
      continue
    if grid[y][w-1-x-1] == ".":
      xcnt[y][w-1-x-1] = xcnt[y][w-1-x]
# print(*xcnt)

for x in range(w):
  cnt = 0
  for y in range(h-1):
    if grid[y][x] == "#":
      cnt = 0
      continue
    if grid[y+1][x] == "#":
      ycnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[h-1][x] == ".":
    ycnt[h-1][x] = cnt + 1
# print(ycnt)
for x in range(w):
  for y in range(h-1):
    if grid[h-1-y][x] == "#":
      continue
    if grid[h-1-y-1][x] == ".":
      ycnt[h-1-y-1][x] = ycnt[h-1-y][x]
# print(*ycnt)
for y in range(h):
  for x in range(w):
    ans = max(ans, xcnt[y][x] + ycnt[y][x] - 1)
print(ans)

Submission status: Accepted

Solution code:
def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)

Submission status: Accepted

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

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

ans = 0

for i in range(H):
    for j in range(W):
        # Uを求める
        if S[i][j] == '#':  pass  # Uは0で初期化されている
        elif i == 0:        U[i][j] = 1
        else:               U[i][j] = U[i - 1][j] + 1

        # Lを求める
        if S[i][j] == '#':  pass
        elif j == 0:  L[i][j] = 1
        else:       L[i][j] = L[i][j - 1] + 1

        # Dを求める
        if S[H - 1 - i][j] == '#':  pass
        elif i == 0:    D[H - 1 - i][j] = 1
        else:           D[H - 1 - i][j] = D[H - i][j] + 1

        # Rを求める
        if S[i][W - 1 - j] == '#':  pass
        elif j == 0:    R[i][W - 1 - j] = 1
        else:           R[i][W - 1 - j] = R[i][W - j] + 1

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:
H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

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

ans = 0

# L, R, Uを求める
for i in range(H):
    for j in range(W):

        if S[i][j] == '#':
            pass  # L, R, Uは0で初期化されている
        else:
            # Uを求める
            if i == 0:  U[i][j] = 1
            else:       U[i][j] = U[i - 1][j] + 1

            # Lを求める
            if j == 0:  L[i][j] = 1
            else:       L[i][j] = L[i][j - 1] + 1

        # Rを求める
        if S[i][W - 1 - j] == '#':
            pass
        elif j == 0:
            R[i][W - 1 - j] = 1
        else:
            R[i][W - 1 - j] = R[i][W - j] + 1

# Dを求める
for i in range(H - 1, -1, -1):
    for j in range(W):
        if S[i][j] == '#':  pass
        elif i == H - 1:    D[i][j] = 1
        else:               D[i][j] = D[i + 1][j] + 1
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

Submission status: Accepted

Solution code:
import re

H,W = map(int,input().split())
arr = []

for i in range(H):
  S = list(map(int,input().replace("#","0").replace(".","1")))
  arr.append(S)

ANS = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][j]
    elif arr[i][j-1] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i].append(ans)

for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][W-1-j]
    elif arr[i][W-j] == 0:
      ans = arr[i][W-1-j]
    else:
      ans = ans + 1
    ANS[i][W-1-j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[i][j]
    elif arr[i-1][j] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i][j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[H-1-i][j]
    elif arr[H-i][j] == 0:
      ans = arr[H-1-i][j]
    else:
      ans = ans + 1
    ANS[H-1-i][j] += ans

    
    
ans = []
for j in range(W):
  for i in range(H):
    if arr[i][j] != 0:
      a = ANS[i][j] - 3
      ans.append(a)
print(int(max(ans)))

Submission status: Accepted

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

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

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

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0:
                U[i][j] = U[i-1][j]+1
            else:
                U[i][j] = 1
            if j != 0:
                L[i][j] = L[i][j-1]+1
            else:
                L[i][j] = 1
            
        else:
            U[i][j] = 0
            L[i][j] = 0

        ri = H-i-1
        rj = W-j-1
        if S[ri][rj] == ".":
            if i != 0:
                D[ri][rj] = D[ri+1][rj]+1
            else:
                D[ri][rj] = 1
            if j != 0:
                R[ri][rj] = R[ri][rj+1]+1
            else:
                R[ri][rj] = 1
        else:
            D[ri][rj] = 0
            R[ri][rj] = 0


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 numpy as np
H,W = map(int,input().split())
S=np.array([list(input().rstrip("\n")) for _ in range(H)]) == '.'
D = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)
for i in range(H):# 上下
  U[i] = (U[i-1] + 1) * S[i]
  D[-i-1] = (D[-i] + 1) * S[-i-1]
for i in range(W):# 左右
  L[:,i] = (L[:,i-1] + 1) * S[:,i]
  R[:,-i-1] = (R[:,-i] + 1) * S[:,-i-1]
print(np.max(U+D+L+R)-3)

Submission status: Accepted

Solution code:
#  D -Lamp
h,w=map(int,input().split())
g=[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)]
o=[[0]*w for i in range(h)]

for i in range(h):
    if g[i][0]=='.':
        l[i][0]=1

for i in range(h):
    for j in range(w-1):
        if g[i][j+1]=='.':
            l[i][j+1]=l[i][j]+1
        elif g[i][j+1]=='#':
            l[i][j+1]=0

for i in range(h):
    if g[i][w-1]=='.':
        r[i][w-1]=1

for i in range(h):
    for j in range(w-1,0,-1):
        if g[i][j-1]=='.':
            r[i][j-1]=r[i][j]+1
        elif g[i][j-1]=='#':
            r[i][j-1]=0

for i in range(w):
    if g[0][i]=='.':
        u[0][i]=1

for i in range(w):
    for j in range(h-1):
        if g[j+1][i]=='.':
            u[j+1][i]=u[j][i]+1
        elif g[j+1][i]=='#':
            u[j+1][i]=0

for i in range(w):
    if g[h-1][i]=='.':
        o[h-1][i]=1

for i in range(w):
    for j in range(h-1,0,-1):
        if g[j-1][i]=='.':
            o[j-1][i]=o[j][i]+1
        elif g[j-1][i]=='#':
            o[j-1][i]=0

ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+o[i][j]-3)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
G = []
for _ in range(H):
    G.append([1 if x == '.' else 0 for x in input()])
G = np.array(G)

North = np.cumsum(np.ones_like(G), axis=0)
North *= (1 - G)
North = np.maximum.accumulate(North, axis=0) * G

South = np.cumsum(np.ones_like(G), axis=0)
South *= np.flipud(1 - G)
South = np.maximum.accumulate(South, axis=0)
South = (H - np.flipud(South)) * G

West = np.cumsum(np.ones_like(G), axis=1)
West *= (1 - G)
West = np.maximum.accumulate(West, axis=1) * G

East = np.cumsum(np.ones_like(G), axis=1)
East *= np.fliplr(1 - G)
East = np.maximum.accumulate(East, axis=1)
East = (W - np.fliplr(East)) * G

print(np.amax(South - North + East - West) - 1)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
G = []
for _ in range(H):
    G.append([1 if x == '.' else 0 for x in input()])
G = np.array(G)
HWOnes = np.ones_like(G)

North = np.cumsum(np.ones_like(G), axis=0)
North *= (1 - G)
North = np.maximum.accumulate(North, axis=0) * G

South = np.cumsum(np.ones_like(G), axis=0)
South *= np.flipud(1 - G)
South = np.maximum.accumulate(South, axis=0)
South = (H - np.flipud(South)) * G

West = np.cumsum(np.ones_like(G), axis=1)
West *= (1 - G)
West = np.maximum.accumulate(West, axis=1) * G

East = np.cumsum(np.ones_like(G), axis=1)
East *= np.fliplr(1 - G)
East = np.maximum.accumulate(East, axis=1)
East = (W - np.fliplr(East)) * G

print(np.amax(South - North + East - West - 1))

Submission status: Accepted

Solution code:
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

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

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

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

print(ans)