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:
[h,w] = [int(i) for i in input().split()]
s = []
tate = [[0] * (h+2) for i in range(w+2)]
yoko = [[0] * (w+2) for i in range(h+2)]
s.append("#"*(w+2))
for i in range(h):
    tmp = input()
    s.append(tmp.join(["#","#"]))
s.append("#"*(w+2))

#横
for i in range(1,h+1):
    tmp = 1
    before = 1
    while tmp < w+2:
        if s[i][tmp] == "#":
            before += 1
            tmp += 1
        else:
            while s[i][tmp] != "#":
                tmp += 1
                if tmp == w+2:
                    break
            yoko[i][before:tmp] = [tmp-before] * (tmp - before)
            before = tmp

for i in range(1,w+1):
    tmp = 1
    before = 1
    while tmp < h+2:
        if s[tmp][i] == "#":
            before += 1
            tmp += 1
        else:
            while s[tmp][i] != "#":
                tmp += 1
                if tmp == h+2:
                    break
            tate[i][before:tmp] = [tmp-before] * (tmp - before)
            before = tmp
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        ans = max(ans,tate[j][i]+yoko[i][j]-1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    LW = [[0] * W for _ in range(H)]
    LH = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LW[h][w-i] = cnt
                LW[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LW[h][w-i] = cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LH[h-i][w] = cnt
                LH[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LH[h-i][w] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            if g[h][w] != '#':
                ans = max(ans, LH[h][w] + LW[h][w] - 1)
    print(ans)
main()

Submission status: Accepted

Solution code:
import numpy as np
h, w = map(int, input().split())
arr = 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) * arr[i]
    d[- i - 1] = (d[- i] + 1) * arr[- i - 1]

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
H,W = map(int,input().split())
grid = []
for _ in range(H):
  grid.append(list(input()))

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

for i in range(H):
  for j in range(W):
    if j-1 >= 0:
      L[i][j] = L[i][j-1]
    if i-1 >= 0:
      D[i][j] = D[i-1][j]

    if grid[i][j] == ".":
      L[i][j] += 1
      D[i][j] += 1
    else:
      L[i][j] = 0
      D[i][j] = 0

for i in range(H-1,-1,-1):
  for j in range(W-1,-1,-1):
    if j+1 < W:
      R[i][j] = R[i][j+1] 
    if i+1 < H:
      U[i][j] = U[i+1][j]
    if grid[i][j] == ".":
      R[i][j] += 1
      U[i][j] += 1
    else:
      R[i][j] = 0
      U[i][j] = 0

res = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == ".":
      res = max(res, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()


def light_count(light, H, W, h, w, count, wr=-1, hr=-1):

    if wr != -1:
        for i in range(h * W + wr, h * W + w):
            light[i] += count
    elif hr != -1:
        for i in range(hr * W + w, h * W + w, W):
            light[i] += count


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = [0 for _ in range(H * W)]
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light_count(light, H, W, h, w, count, wr=wr)
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light_count(light, H, W, h, w + 1, count, wr=wr)
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light_count(light, H, W, h, w, count, hr=hr)
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light_count(light, H, W, h + 1, w, count, hr=hr)
                hr = -1
                count = 0

    print(max(light) - 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
matrix = [list(raw_input()) for _ in range(n)]
dpleft = [[0 for j in range(m)] for i in range(n)]
dpright = [[0 for j in range(m)] for i in range(n)]
dpup = [[0 for j in range(m)] for i in range(n)]
dpdown = [[0 for j in range(m)] for i in range(n)]

for i in range(n):
	cumul = 0
	for j in range(m):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpleft[i][j] = cumul
			cumul +=1

	cumul = 0
	for j in range(m-1,-1,-1):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpright[i][j] = cumul
			cumul +=1

for j in range(m):
	cumul = 0
	for i in range(n):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpup[i][j] = cumul
			cumul +=1

	cumul = 0
	for i in range(n-1,-1,-1):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpdown[i][j] = cumul
			cumul +=1
r = 0
for i in range(len(matrix)):
	for j in range(len(matrix[0])):
		if matrix[i][j] != '#':
			r = max(r, 1 + dpleft[i][j] + dpright[i][j] + dpdown[i][j] + dpup[i][j])

print r

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input()+'#' for i in range(h)]
s.append('#'*(w+1))
h1=[[0]*(w+1) for i in range(h+1)]
w1=[[0]*(w+1) for i in range(h+1)]
for j in range(h):
  r=0
  for i in range(w+1):
    if s[j][i]=='#':
      for k in range(i-r,i+1):
        h1[j][k]=r
      r=0
      h1[j][i]=0
    else:
      r+=1
for j in range(w):
  r=0
  for i in range(h+1):
    if s[i][j]=='#':
      for k in range(i-r,i+1):
        w1[k][j]=r
      r=0
      w1[i][j]=0
    else:
      r+=1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,h1[i][j]+w1[i][j]-1)
print(ans)

Submission status: Accepted

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

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

ret_mtx1 = [[0] * w for _ in range(h)]
ret_mtx2 = [[0] * w for _ in range(h)]
ret_mtx3 = [[0] * w for _ in range(h)]
ret_mtx4 = [[0] * w for _ in range(h)]

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == '.':
            ret_mtx1[i][j] = 1 if i == 0 else ret_mtx1[i-1][j] + 1
            ret_mtx2[i][j] = 1 if j == 0 else ret_mtx2[i][j-1] + 1
        if mtx[-1-i][-1-j] == '.':
            ret_mtx3[-1-i][-1-j] = 1 if i == 0 else ret_mtx3[-i][-1-j] + 1
            ret_mtx4[-1-i][-1-j] = 1 if j == 0 else ret_mtx4[-1-i][-j] + 1

ret = 0

for i in range(h):
    for j in range(w):
        tmp = ret_mtx1[i][j] + ret_mtx2[i][j] + \
            ret_mtx3[i][j] + ret_mtx4[i][j] - 3
        ret = max(ret, tmp)

print(ret)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    h, w = map(int, input().split())
    col = [[0, w + 1] for _ in range(h)]
    row = [[0, h + 1] for _ in range(w)]
    for i in range(h):
        s = list(input()[:-1].decode())
        for j in range(w):
            if s[j] == '#':
                col[i].append(j + 1)
                row[j].append(i + 1)

    cc = [[0] * (w + 2) for _ in range(h)]
    rc = [[0] * (h + 2) for _ in range(w)]

    for i in range(h):
        col[i].sort()
        for j in range(len(col[i]) - 1):
            cc[i][col[i][j] + 1:col[i][j + 1]] = [col[i][j + 1] - col[i][j] - 1] * (col[i][j + 1] - col[i][j] - 1)

    for i in range(w):
        row[i].sort()
        for j in range(len(row[i]) - 1):
            rc[i][row[i][j] + 1:row[i][j + 1]] = [row[i][j + 1] - row[i][j] - 1] * (row[i][j + 1] - row[i][j] - 1)

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

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

tile = [0 for i in range(H)]
cnt = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    done = [False for _ in range(W)]
    for j in range(W):
        if tile[i][j] == '#':
            continue
        if done[j]:
            continue
        l = 0
        while (j + l < W):
            if tile[i][j + l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j + k] += l
            done[j + k] = True

for j in range(W):
    done = [False for _ in range(H)]
    for i in range(H):
        if tile[i][j] == '#':
            continue
        if done[i]:
            continue
        l = 0
        while (i + l < H):
            if tile[i + l][j] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i + k][j] += l
            done[i + k] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(cnt[i][j] - 1, ans)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
mp = ['#'*(W+2)]
for _ in range(H):
  mp.append('#'+input()+'#')
mp.append('#'*(W+2))

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

rlt = 0
for i in range(H+1):
  for j in range(W+1):
    if mp[i+1][j] == '#':
      D[i+1][j] = 0
    else:
      D[i+1][j] = D[i][j] + 1
    if mp[H-i][j] == '#':
      U[H-i][j] = 0
    else:
      U[H-i][j] = U[H-i+1][j] + 1 
    if mp[i][j+1] == '#':
      R[i][j+1] = 0
    else:
      R[i][j+1] = R[i][j] + 1
    if mp[i][W-j] == '#':
      L[i][W-j] = 0
    else:
      L[i][W-j] = L[i][W-j+1] + 1 

for i in range(1,H+1):
  for j in range(1,W+1):
    tmp = L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
    if tmp > rlt:
      rlt = tmp
      
print(rlt)

Submission status: Accepted

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

l_list = [[0 for i in range(w)] for i in range(h)]
r_list = [[0 for i in range(w)] for i in range(h)]
u_list = [[0 for i in range(w)] for i in range(h)]
d_list = [[0 for i in range(w)] for i in range(h)]

for i in range(h):
  for j in range(w):
    if maps[i][j] == "#":
      l_list[i][j] = 0
    elif j == 0:
      l_list[i][j] = 1
    else:
      l_list[i][j] = l_list[i][j-1] + 1
      
for i in range(h):
  for j in range(w-1,-1,-1):
    if maps[i][j] == "#":
      r_list[i][j] = 0
    elif j == w-1:
      r_list[i][j] = 1
    else:
      r_list[i][j] = r_list[i][j+1] + 1
      
for i in range(h):
  for j in range(w):
    if maps[i][j] == "#":
      u_list[i][j] = 0
    elif i == 0:
      u_list[i][j] = 1
    else:
      u_list[i][j] = u_list[i-1][j] + 1  
      
for i in range(h-1,-1,-1):
  for j in range(w):
    if maps[i][j] == "#":
      d_list[i][j] = 0
    elif i == h-1:
      d_list[i][j] = 1
    else:
      d_list[i][j] = d_list[i+1][j] + 1  

result = []
for i in range(h):
  for j in range(w):
    result.append(l_list[i][j] + u_list[i][j] + d_list[i][j] + r_list[i][j] - 3)
  
print(max(result))

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    h,w=map(int,readline().split())
    grid=[readline().strip() for _ in range(h)]
    grid=[[1 if grid[i][j]=="." else 0 for j in range(w)] for i in range(h)]
    grid=np.array(grid,dtype=np.int64)

    up=np.zeros((h,w),dtype="int64")
    up[0]=grid[0]
    for i in range(1,h):
        up[i]=(up[i-1]+1)*grid[i]
    
    down=np.zeros((h,w),dtype="int64")
    down[-1]=grid[-1]
    for i in range(h-2,-1,-1):
        down[i]=(down[i+1]+1)*grid[i]
    
    left=np.zeros((h,w),dtype="int64")
    left[:,0]=grid[:,0]
    for i in range(1,w):
        left[:,i]=(left[:,i-1]+1)*grid[:,i]
    
    right=np.zeros((h,w),dtype="int64")
    right[:,-1]=grid[:,-1]
    for i in range(w-2,-1,-1):
        right[:,i]=(right[:,i+1]+1)*grid[:,i]

    ans=(up+down+left+right-3).max()
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(i,j,dx,dy,kum):
    visited[i][j] = 1
    if grid[i][j]!="#" and visited[i][j]!=1:
        num[i][j]=max(num[i][j],dfs(i+dx,j+dy,dx,dy,kum+1))
    num[i][j] = max(num[i][j],kum)
    return kum
def main():
    h,w = map(int, input().split())
    grid = []
    for i in range(h):
        s = list(input().rstrip())
        grid.append(s)
    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 grid[i][j]!="#":
                if j==0:
                    l[i][j]=1
                else:
                    l[i][j]=l[i][j-1]+1
            if grid[i][j]=="#":
                l[i][j]=0
            if grid[i][j]!="#":
                if i==0:
                    d[i][j]=1
                else:
                    d[i][j]=d[i-1][j]+1
            if grid[i][j]=="#":
                d[i][j]=0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if grid[i][j]!="#":
                if j==w-1:
                    r[i][j]=1
                else:
                    r[i][j]=r[i][j+1]+1
            if grid[i][j]=="#":
                r[i][j]=0

    for i in range(h-1,-1,-1):
        for j in range(w):
            if grid[i][j]!="#":
                if i==h-1:
                    u[i][j]=1
                else:
                    u[i][j]=u[i+1][j]+1
            if grid[i][j]=="#":
                u[i][j]=0
    tmp = 0

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



    print(tmp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
## code borrowed from "maspy"

import numpy as np
import sys
buf = sys.stdin.buffer
 
H,W = map(int,buf.readline().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'.').reshape((H,W+1))
 
# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = np.where(x,0,-np.arange(L)) # 左の壁のindexの-1倍
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.where(x[::-1],0,np.arange(L)) # 逆順ソートした上で左の壁のindex
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w = map(int,ipt().split())
    s = [""]*h+["#"*(w+1)]
    for i in range(h):
        s[i] = input()+"#"
    l = [[0]*(w+1) for _ in [0]*(h+1)]
    r = [[0]*(w+1) for _ in [0]*(h+1)]
    u = [[0]*(w+1) for _ in [0]*(h+1)]
    d = [[0]*(w+1) for _ in [0]*(h+1)]
    sm = [[-3]*(w+1) for _ in [0]*(h+1)]
    for i in range(h):
        si = sm[i]
        li = l[i]
        ui = u[i]
        for j in range(w):
            if s[i][j] == "#":
                continue
            else:
                li[j] = l[i-1][j]+1
                ui[j] = ui[j-1]+1
                si[j] += li[j]+ui[j]
    ma = 0
    for i in range(h):
        ri = r[h-i-1]
        si = sm[h-i-1]
        di = d[h-i-1]
        for j in range(w):
            if s[h-i-1][w-j-1] == "#":
                continue
            else:
                ri[w-j-1] = r[h-i][w-j-1]+1
                di[w-j-1] = di[w-j]+1
                si[w-j-1] += ri[w-j-1]+di[w-j-1]
                if ma < si[w-j-1]:
                    ma = si[w-j-1]
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve(H: int, W: int, S: "List[int]"):
    # print(S)

    hcnts = [[0]*W for _ in range(H)]
    for h in range(H):
        hcnts[h][0] = S[h][0]
        for t in range(1,W):
            hcnts[h][t] = (S[h][t]+hcnts[h][t-1])*S[h][t]
    for h in range(H):
        for t in range(W-2,-1,-1):
            hcnts[h][t] = max(hcnts[h][t],hcnts[h][t+1])*bool(hcnts[h][t])

    wcnts = [[0]*W for _ in range(H)]
    for h in range(W):
        wcnts[0][h] = S[0][h]
        for t in range(1,H):
            wcnts[t][h] = (S[t][h]+wcnts[t-1][h])*S[t][h]
    for h in range(W):
        for t in range(H-2,-1,-1):
            wcnts[t][h] = max(wcnts[t][h],wcnts[t+1][h])*bool(wcnts[t][h])
    # print(hcnts)
    # print(wcnts)
    a = [hcnts[h][w]+wcnts[h][w]-1 for h in range(H) for w in range(W)]
    print(max(a))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [[ int(_.replace(".", "1").replace("#", "0")) for _ in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
grid=[]
for _ in range(h):
    s=input()
    g=[0 if i=='#' else 1 for i in s]
    grid.append(g)
toL=[]
toR=[]
toU=[]
toD=[]
for i in range(h):
    tmpL=[]
    tmpR=[]
    tmpU=[]
    tmpD=[]
    for j in range(w):
        if grid[i][j]==0:
            tmpU.append(0)
        elif i==0:
            tmpU.append(1)
        else:
            tmpU.append(toU[i-1][j]+1)
        if grid[-i-1][j]==0:
            tmpD.append(0)
        elif i==0:
            tmpD.append(1)
        else:
            tmpD.append(toD[i-1][j]+1)
        if grid[i][j]==0:
            tmpL.append(0)
        elif j==0:
            tmpL.append(1)
        else:
            tmpL.append(tmpL[-1]+1)
        if grid[i][-j-1]==0:
            tmpR.append(0)
        elif j==0:
            tmpR.append(1)
        else:
            tmpR.append(tmpR[-1]+1)
    toL.append(tmpL)
    toR.append(tmpR[::-1])
    toU.append(tmpU)
    toD.append(tmpD)
toD=toD[::-1]
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, toU[i][j]+toD[i][j]+toR[i][j]+toL[i][j]-3)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
S = SLs(H)

YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  

TATE = []
for i in range(W):
  prev = None
  yoko = []
  count = 0
  for j in range(H):
    item = S[j][i]
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  TATE.append(yoko)


print(max(max(TATE[j][i]+YOKO[i][j] for j in range(W)) for i in range(H))-1)

Submission status: Accepted

Solution code:
#numpy使い、ループが2→１にする
import numpy as np
#初期入力
H,W = (int(x) for x in input().split())
map1 =[ list(input()) for i in range(H)]
map_np =(np.array(map1)==".")*1

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)

L[:,0] =map_np[:,0]
for i in range(1,W): # if map_np[i,j] ==1: ⇒ *map_npで１or０をかけてるから不要
    L[:,i] = (L[:,i-1] +1) *map_np[:,i]

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

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

D[H-1,:] =map_np[H-1,:]
for i in range(H-1-1,-1,-1):
    D[i,:] = (D[i+1,:] +1) *map_np[i,:]
    
ans =L +R +U +D -3
print(np.max(ans))

Submission status: Accepted

Solution code:
import numpy as np

H,W=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(1,H):
    ups[i,:]=(ups[i-1,:]+1)*S[i-1,:]

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

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

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

ans=((ups+downs+lefts+rights)*S).max()+1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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(1, h):
    ups[i, :] = (ups[i-1]+1)*s[i-1]

for i in reversed(range(h-1)):
    downs[i, :] = (downs[i+1]+1)*s[i+1]

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

for i in reversed(range(w-1)):
    lefts[:, i] = (lefts[:, i+1]+1)*s[:, i+1]

ans = (((ups+downs+lefts+rights)*s).max()+1)
print(ans)


# data_w = []
# data_w_index = []
# data_h = []
# data_h_index = []

# for i in range(h):
#     count = 0
#     index = 0
#     data_w_index_tmp = []
#     data_w_tmp = []
#     for j in range(len(s[i])):
#         # print(s[i][j][0])
#         # print(count)
#         # print(index)
#         if s[i][j] == ".":
#             count += 1
#             data_w_index_tmp.append(index)
#         else:
#             data_w_tmp.append(count)
#             data_w_index_tmp.append(-1)
#             count = 0
#             index += 1
#     data_w_tmp.append(count)
#     # data_w_index_tmp.append(index)

#     data_w_index.append(data_w_index_tmp)
#     data_w.append(data_w_tmp)

# print(data_w)
# print(data_w_index)

# for i in range(w):
#     count = 0
#     index = 0
#     data_h_index_tmp = []
#     data_h_tmp = []
#     for j in range(len(s)):
#         # print(s[i][j][0])
#         # print(count)
#         # print(index)
#         if s[j][i] == ".":
#             count += 1
#             data_h_index_tmp.append(index)
#         else:
#             data_h_tmp.append(count)
#             data_h_index_tmp.append(-1)
#             count = 0
#             index += 1
#     data_h_tmp.append(count)
#     # data_h_index_tmp.append(index)

#     data_h_index.append(data_h_index_tmp)
#     data_h.append(data_h_tmp)

# # print(data_h)
# # print(data_h_index)

# ans = 0
# for i in range(w):
#     for j in range(h):
#         index_h = data_h_index[i][j]
#         index_w = data_w_index[j][i]
#         if index_h != 1:
#             ans_tmp = data_h[i][index_h]+data_w[j][index_w]-1
#             ans = max(ans, ans_tmp)
# print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

h, w = map(int, input().split())
notwall = []
for _ in range(h):
    s = input()
    notwall.append([int(c == '.') for c in s])

notwall = np.array(notwall)


def getll():
    ls = np.zeros((h, w + 1), dtype=int)

    for i in range(w):
        ls[:, i + 1] = (ls[:, i] + 1) * notwall[:, i]

    ls = ls[:, 1:]
    return ls


def getlr():
    ls = np.zeros((h, w + 1), dtype=int)

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

    ls = ls[:, :-1]
    return ls


def getlu():
    ls = np.zeros((h + 1, w), dtype=int)

    for i in range(h):
        ls[i + 1, :] = (ls[i, :] + 1) * notwall[i, :]

    ls = ls[1:, :]
    return ls


def getld():
    ls = np.zeros((h + 1, w), dtype=int)

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

    ls = ls[:-1, :]
    return ls


ll = getll()
lr = getlr()
lu = getlu()
ld = getld()

m = max([0, np.max(ll + lr + lu + ld) - 3])

print(m)