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 = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
 
for i in range(H):
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]

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

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

Submission status: Accepted

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

dw = []
dh = []

for i in range(h):
    cw = []
    for j in range(w):
        if s[i][j] == '#':
            cw.append(0)
        elif j == 0 or s[i][j - 1] == '#':
            count = 0
            for k in range(j, w):
                if s[i][k] == '.':
                    count += 1
                    if k == w - 1:
                        cw.append(count)
                else:
                    cw.append(count)
                    break
        else:
            cw.append(cw[j - 1])
    dw.append(cw)

for j in range(w):
    ch = []
    for i in range(h):
        if s[i][j] == '#':
            ch.append(0)
        elif i == 0 or s[i - 1][j] == '#':
            count = 0
            for k in range(i, h):
                if s[k][j] == '.':
                    count += 1
                    if k == h - 1:
                        ch.append(count)
                else:
                    ch.append(count)
                    break
        else:
            ch.append(ch[i - 1])
    dh.append(ch)

max = 0
for i in range(h):
    for j in range(w):
        sum = dw[i][j] + dh[j][i]
        if max < sum:
            max = sum
print(max - 1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

l = [[0]*w for _ in [0]*h] #左にある白マス（自分含む）
r = [[0]*w for _ in [0]*h]
u = [[0]*w for _ in [0]*h] #上にある白マス（自分含む）
d = [[0]*w for _ in [0]*h]
for hi in range(h):
    for wj in range(w):
        if b[hi][wj] == '.':
            l[hi][wj] = l[hi][wj-1]+1
            u[hi][wj] = u[hi-1][wj]+1
        if b[hi][w-wj-1] == '.':
            r[hi][w-wj-1] = r[hi][-wj]+1
        if b[h-hi-1][wj] == '.':
            d[h-hi-1][wj] = d[-hi][wj]+1

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

Submission status: Accepted

Solution code:
import numpy as np

H, W = list(map(int, input().split()))
S = np.array([list(input()) 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 i in range(H):
  lefts[i] = (lefts[i - 1] + 1) * S[i]
  rights[-1 - i] = (rights[-i] + 1) * S[-1 - i]
for i in range(W):
  ups[:, i] = (ups[:, i - 1] + 1) * S[:, i]
  downs[:, -1 - i] = (downs[:, -i] + 1) * S[:, -1 - i]
  
ans = np.max(lefts + rights + ups + downs) - 3
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W = list(map(int, input().split()))
S = np.array([list(input()) 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+rights+lefts)*S).max()+1)

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w=map(int,h.split())
r=range
a,b,c,d=eval('eval("w*[0],"*h),'*4)
for i in r(h*w):i,j=i//w,i%w;f=s[i][j]>'#';a[i][j]=-~a[i][j-1]*f;b[i][~j]=-~b[i][-j]*(s[i][-j-2]>'#');c[i][j]=-~c[i-1][j]*f;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:
h,*s=open(0)
h,w=map(int,h.split())
r=range
a,b,c,d=eval('eval("w*[0],"*h),'*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:
a=[]
h,w=map(int,input().split())
for i in range(h):
    a.append(input()+'#')
a.append('#'*(w+1))
b=[[0]*(w+1) for i in range(h+1)]
c=[[0]*(w+1) for i in range(h+1)]

for i in range(h+1):
    t=0
    for j in range(w+1):
        if a[i][j]=='#':
            for k in range(t):
                b[i][j-k-1]=t
            t=0
        else:
            t+=1

for j in range(w+1):
    t=0
    for i in range(h+1):
        if a[i][j]=='#':
            for k in range(t):
                c[i-k-1][j]=t
            t=0
        else:
            t+=1
ans=0
for i in range(h+1):
    for j in range(w+1):           
        ans=max(b[i][j]+c[i][j]-1,ans)
print(ans)

Submission status: Accepted

Solution code:
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 range(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:
def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()

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,dtype=int)
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((L+R+U+D).max()-3)

Submission status: Accepted

Solution code:
def solve2():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    L = [[0] * W for i in range(H)]
    R = [[0] * W for i in range(H)]
    D = [[0] * W for i in range(H)]
    U = [[0] * W for i in range(H)]
    # Left
    for i in range(H):
        if S[i][0] == '.':
            L[i][0] = 1
    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                L[i][j] = L[i][j-1] + 1
            else:
                L[i][j] = 0
    # Right
    for i in range(H):
        if S[i][W-1] == '.':
            R[i][W-1] = 1
    for i in range(H):
        for j in range(W-2,-1,-1):
            if S[i][j] == '.':
                R[i][j] = R[i][j+1] + 1
            else:
                R[i][j] = 0
    # Down
    for j in range(W):
        if S[0][j] == '.':
            D[0][j] = 1
    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                D[i][j] = D[i-1][j] + 1
            else:
                D[i][j] = 0
    # Up
    for j in range(W):
        if S[H-1][j] == '.':
            U[H-1][j] = 1
    for j in range(W):
        for i in range(H-2,-1,-1):
            if S[i][j] == '.':
                U[i][j] = U[i+1][j] + 1
            else:
                U[i][j] = 0
    ans = 1
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3)
    print ans

if __name__ == '__main__':
    solve2()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
l = []
r = []
u = []
d = []
for i in range(h):
  s.append(input())
  l.append([0 for j in range(w)])
  r.append([0 for j in range(w)])
  u.append([0 for j in range(w)])
  d.append([0 for j in range(w)])
  
# lみる
for x in range(w):
  for y in range(h):
    if s[y][x] == '.':
      if x == 0:
        l[y][x] = 1
      else:
        l[y][x] = l[y][x-1] + 1
 
# rみる
for x in range(w-1, -1, -1):
  for y in range(h-1, -1, -1):
    if s[y][x] == '.':
      if x == w-1:
        r[y][x] = 1
      else:
        r[y][x] = r[y][x+1] + 1
 
# uみる
for y in range(h):
  for x in range(w):
    if s[y][x] == '.':
      if y == 0:
        u[y][x] = 1
      else:
        u[y][x] = u[y-1][x] + 1
 
# dみる
for y in range(h-1, -1, -1):
  for x in range(w-1, -1, -1):
    if s[y][x] == '.':
      if y == h-1:
        d[y][x] = 1
      else:
        d[y][x] = d[y+1][x] + 1
 
 
max_all = 0
for y in range(h):
  for x in range(w):
    max_tmp = l[y][x] + r[y][x] + u[y][x] + d[y][x]
    if max_tmp > max_all:
      max_all = max_tmp
      
print(max_all - 3)

Submission status: Accepted

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

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

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

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

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:

H, W = map(int, input().split())
s = [input() for i 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)]
d = [[0 for i in range(W)] for j in range(H)]
u = [[0 for i in range(W)] for j in range(H)]

# Up-Light
for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            l[i][j] = 0
            u[i][j] = 0
            continue

        if j == 0:
            l[i][j] = 1
        else:
            l[i][j] = l[i][j-1] + 1

        if i == 0:
            u[i][j] = 1
        else:
            u[i][j] = u[i-1][j] + 1

# Right-Down
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if s[i][j] == "#":
            r[i][j] = 0
            d[i][j] = 0
            continue

        if j == W-1:
            r[i][j] = 1
        else:
            r[i][j] = r[i][j+1] + 1

        if i == H-1:
            d[i][j] = 1
        else:
            d[i][j] = d[i+1][j] + 1

max_score = 0
for i in range(H):
    for j in range(W):
        score = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if score > max_score:
            max_score = score
print(max_score)

Submission status: Accepted

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

H, W = map(int, input().split())
S = [input() for x 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)

S_ = np.zeros([H, W], dtype=int)
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': S_[h, w] = 0
        else: S_[h, w] = 1
L[:, 0] = S_[:, 0]
for w in range(1, W):
    L[:, w] = (L[:, w-1] + 1) * S_[:, w]
R[:, W-1] = S_[:, W-1]
for w in range(W-2, -1, -1):
    R[:, w] = (R[:, w+1] + 1) * S_[:, w]
U[0] = S_[0]
for h in range(1, H):
    U[h] = (U[h-1] + 1) * S_[h]
D[H-1] = S_[H-1]
for h in range(H-2, -1, -1):
    D[h] = (D[h+1] + 1) * S_[h]

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

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
F = np.array([[1 if i == "." else 0 for i in input()] for _ in range(H)])
FU = np.zeros((H, W), dtype=int)
FD = np.zeros((H+1, W), dtype=int)
FL = np.zeros((H, W), dtype=int)
FR = np.zeros((H, W+1), dtype=int)

for i in range(H):
    FU[i] += (FU[i-1]+1)*F[i]

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

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

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

FV = FU + FD[:-1] - 1
FH = FL + FR[:, :-1] - 1
ans = np.max(FV+FH)
if ans >= 2:
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def lmi(): return list(map(int, input().split()))

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

cnt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    j = 0
    while j < w:
        if s[i][j] == '#':
            j += 1
            continue
        l = 0
        while j+l < w:
            if s[i][j+l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
        j += l+1

for i in range(w):
    j = 0
    while j < h:
        if s[j][i] == '#':
            j += 1
            continue
        l = 0
        while j+l < h:
            if s[j+l][i] == '#':
                break
            l += 1
        for k in range(l):
            cnt[j+k][i] += l
        j += l+1


print(max([max([cnt[i][j] for i in range(h)]) for j in range(w)])-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = np.ones((H, W), dtype=int)
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i][j] = 0

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

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

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


main()

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    s1=[]
    for j in range(W):
        if s[j]=='.':
            s1+=[1]
        else:
            s1+=[0]
    S+=[s1]
S=np.array(S)

Tl=np.zeros((H,W),dtype=np.int)
Tr=np.zeros((H,W),dtype=np.int)

Tu=np.zeros((H,W),dtype=np.int)
Td=np.zeros((H,W),dtype=np.int)
for i in range(1,W):
    Tl[:,i]+=(Tl[:,i-1]+1)*S[:,i-1]

for i in range(W-2,-1,-1):
    Tr[:,i]+=(Tr[:,i+1]+1)*S[:,i+1]

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

for i in range(H-2,-1,-1):
    Td[i,:]+=(Td[i+1,:]+1)*S[i+1,:]

print(((Tl+Tr+Tu+Td)*S).max()+1)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

H, W = l_inpl()
field = [ input() for _ in range(H) ]

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

for hi in range(H):
    for wi in range(W):
        now = field[hi][wi]
        if now == "#":
            L[hi][wi] = 0
        else:
            if wi == 0:
                L[hi][wi] = 1
            else:
                L[hi][wi] = L[hi][wi-1] + 1

for hi in range(H):
    for wi in range(W)[::-1]:
        now = field[hi][wi]
        if now == "#":
            R[hi][wi] = 0
        else:
            if wi == W-1:
                R[hi][wi] = 1
            else:
                R[hi][wi] = R[hi][wi+1] + 1

for hi in range(H):
    for wi in range(W):
        now = field[hi][wi]
        if now == "#":
            U[hi][wi] = 0
        else:
            if hi == 0:
                U[hi][wi] = 1
            else:
                U[hi][wi] = U[hi-1][wi] + 1

for hi in range(H)[::-1]:
    for wi in range(W):
        now = field[hi][wi]
        if now == "#":
            D[hi][wi] = 0
        else:
            if hi == H-1:
                D[hi][wi] = 1
            else:
                D[hi][wi] = D[hi+1][wi] + 1

print(max([ L[hi][wi] + R[hi][wi] + D[hi][wi] + U[hi][wi] - 3 for hi in range(H) for wi in range(W)]))

Submission status: Accepted

Solution code:

import copy

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

board = [input() for _ in range(h)]

left = [ [0]*w for _ in range(h)] 
right = [ [0]*w for _ in range(h)]        #いくつ右のマスを照らせるか
down = [ [0]*w for _ in range(h)]
up = [ [0]*w for _ in range(h)]



for hi in range(h):
    for wi in range(w):

        if board[hi][wi] == '.':
            left[hi][wi] = 1
            up[hi][wi] = 1

            if 1 <= wi:
                left[hi][wi] += left[hi][wi-1]

            if 1 <= hi:
                up[hi][wi] += up[hi-1][wi]


        if board[hi][w-wi-1] =='.':
            right[hi][w-wi-1] = 1

            if 1<=wi:
                right[hi][w-wi-1] += right[hi][w-wi] 

        if board[h-hi-1][wi] == '.':
            down[h-hi-1][wi] = 1

            if 1 <= hi:
                down[h-hi-1][wi] += down[h-hi][wi]


def dbcheck():
    print()
    tag = ["r","l","d","u"]
    for t,x in zip(tag,[right,left,down,up]):
        print(t)
        for row in x:
            print(row)
        print()


#dbcheck()

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

print(ans)

Submission status: Accepted

Solution code:

import copy

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

board = [input() for _ in range(h)]

left = [ [0]*w for _ in range(h)] 
right = copy.deepcopy(left )        #いくつ右のマスを照らせるか
down = copy.deepcopy(left)
up = copy.deepcopy(left)



for hi in range(h):
    for wi in range(w):

        if board[hi][wi] == '.':
            left[hi][wi] = 1
            up[hi][wi] = 1

            if 1 <= wi:
                left[hi][wi] += left[hi][wi-1]

            if 1 <= hi:
                up[hi][wi] += up[hi-1][wi]


        if board[hi][w-wi-1] =='.':
            right[hi][w-wi-1] = 1

            if 1<=wi:
                right[hi][w-wi-1] += right[hi][w-wi] 

        if board[h-hi-1][wi] == '.':
            down[h-hi-1][wi] = 1

            if 1 <= hi:
                down[h-hi-1][wi] += down[h-hi][wi]


def dbcheck():
    print()
    tag = ["r","l","d","u"]
    for t,x in zip(tag,[right,left,down,up]):
        print(t)
        for row in x:
            print(row)
        print()


#dbcheck()

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

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

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

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

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

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

answer = ((L+R+U+D)*b).max()
  
print(answer+1)

Submission status: Accepted

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

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

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def main ():
    H, W = map(int, input().split())
    MAP = [list('#' for i in range(W + 2)) for j in range(H + 2)]
    for i in range(H):
        line = list(input())
        for j, dot in enumerate(line):
            MAP[i + 1][j + 1] = dot
    L = [[0 for j in range(W + 2)] for i in range(H + 2)]


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


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

    line(MAP)
    column(MAP)
    print(column(MAP))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[]
for i in range(H):
    grid.append(list(input()))

L=list2d(H, W, 0)
R=list2d(H, W, 0)
D=list2d(H, W, 0)
U=list2d(H, W, 0)

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

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

ans=0
for i in range(H):
    for j in range(W):
        if grid[i][j]!='#':
            ans=max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

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

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

s = [list(input()) for i in range(h)]
b = np.array(s)
b = np.where(b == '.', 1, 0)

u = np.zeros((h, w), dtype=np.int)
for i in range(1, h):
    u[i] += (u[i - 1] + 1) * b[i - 1]

d = np.zeros((h, w), dtype=np.int)
for i in range(h - 2, -1, -1):
    d[i] += (d[i + 1] + 1) * b[i + 1]

l = np.zeros((h, w), dtype=np.int)
for j in range(1, w):
    l[:, j] += (l[:, j - 1] + 1) * b[:, j - 1]

r = np.zeros((h, w), dtype=np.int)
for j in range(w - 2, -1, -1):
    r[:, j] += (r[:, j + 1] + 1) * b[:, j + 1]

print(((u + d + l + r) * b).max() + 1)

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq


# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def reduce(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

import random




def main():
    row,col = map(int, input().split())
    grid = [[] for _ in range(row)]
    cnt_grid_row = [[0]*col for _ in range(row)]
    cnt_grid_col = [[0]*col for _ in range(row)]
    # eprint(grid)
    for i in range(row):
        grid[i] = input()
    # eprint(grid)

    for i in range(len(grid)):
        cnt_temp=0
        start_temp=0
        for j in range(len(grid[i])):
            if grid[i][j]=='.':
                cnt_temp+=1
            if grid[i][j]=='#':
                for k in range(start_temp,j):
                    cnt_grid_row[i][k]=cnt_temp
                start_temp=j+1
                cnt_temp=0
                cnt_grid_row[i][j]=0
            elif j==col-1:
                for k in range(start_temp,col):
                    cnt_grid_row[i][k]=cnt_temp




    for i in range(col):
        cnt_temp=0
        start_temp=0
        for j in range(row):
            if grid[j][i]=='.':
                cnt_temp+=1
            if grid[j][i]=='#':
                for k in range(start_temp,j):
                    cnt_grid_col[k][i]=cnt_temp
                start_temp=j+1
                cnt_temp=0
                cnt_grid_col[j][i]=0
            elif j==row-1:
                for k in range(start_temp,row):
                    cnt_grid_col[k][i]=cnt_temp

    # for i in range(row):
    #     for j in range(col):
    #         eprint(cnt_grid_row[i][j],end="")
    #     eprint()

    # eprint()

    # for i in range(row):
    #     for j in range(col):
    #         eprint(cnt_grid_col[i][j],end="")
    #     eprint()

    max=0
    for i in range(row):
        for j in range(col):
            if grid[i][j]!='#':
                if cnt_grid_col[i][j]+cnt_grid_row[i][j]-1>max:
                    max=cnt_grid_col[i][j]+cnt_grid_row[i][j]-1
    print(max)

    return

if __name__ == '__main__':
    main()