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:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = tuple(input() for _ in range(H))

uf_r = UnionFind(H * W)
for r in range(H - 1):
    for c in range(W):
        if s[r][c] == '.' and s[r + 1][c] == '.':
            uf_r.unite(r * W + c, (r + 1) * W + c)

uf_c = UnionFind(H * W)
for c in range(W - 1):
    for r in range(H):
        if s[r][c] == '.' and s[r][c + 1] == '.':
            uf_c.unite(r * W + c, r * W + (c + 1))

ans = 0
for r in range(H):
    for c in range(W):
        if s[r][c] == '#': continue
        t = uf_r.size(r * W + c) + uf_c.size(r * W + c) - 1
        ans = max(ans, t)
print(ans)

Submission status: Accepted

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

from itertools import accumulate

rxs = []

for row in S:
    si = -1
    xs = [0] * (W + 1)
    for i in range(W + 1):
        if row[i] == "#":
            xs[si + 1] += (i - si - 1)
            xs[i] -= (i - si - 1)
            si = i
    rxs.append(list(accumulate(xs)))

sxs = []


for row in zip(*S):
    si = -1
    xs = [0] * (H + 1)
    for i in range(H + 1):
        if row[i] == "#":
            xs[si + 1] += (i - si - 1)
            xs[i] -= (i - si - 1)
            si = i
    sxs.append(list(accumulate(xs)))

result = 0

for r1, r2 in zip(rxs, zip(*sxs)):
    r = max(c1 + c2 for c1, c2 in zip(r1, r2)) - 1
    result = max(result, r)

print(result)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    s = []
    for i in range(h):
        s.append(input())
    
    yoko = [[0 for i in range(w)] for j in range(h)]
    tate = [[0 for i in range(w)] for j in range(h)]
 
    for i in range(h):
        index = 0
        while(index < w):
            count = 0
            for j in range(index, w):
                if(s[i][j] == "#"):
                    break
                count += 1
            
            if(count == 0):
                yoko[i][index] = 0
                index += 1
 
            else:
                for j in range(index, index + count):
                    yoko[i][j] = count
                index += count
 
    for i in range(w):
        index = 0
        while(index < h):
            count = 0
            for j in range(index, h):
                if(s[j][i] == "#"):
                    break
                count += 1
            
            if(count == 0):
                tate[index][i] = 0
                index += 1
 
            else:
                for j in range(index, index + count):
                    tate[j][i] = count
                index += count
 
    result = 0
 
    for i in range(h):
        for j in range(w):
            result = max(result, yoko[i][j] + tate[i][j] - 1)
 
 
    print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
ans_array = [[0] * W for i in range(H)]
block_array = []
for i in range(H):
    block_str = input().rstrip()

    block_array.append([1 if s == "#" else 0 for s in block_str])
# print(block_array)

for i in range(H):
    start = 0
    count = 0
    for j in range(W):
        if block_array[i][j] == 1:
            for k in range(start, j):
                ans_array[i][k] += count
            start = j + 1
            count = 0
        else:
            count += 1
    else:
        for k in range(start, W):
            ans_array[i][k] += count

# print(ans_array)

for i in range(W):
    start = 0
    count = 0
    for j in range(H):
        if block_array[j][i] == 1:
            for k in range(start, j):
                ans_array[k][i] += count
            start = j + 1
            count = 0
        else:
            count += 1
    else:
        for k in range(start, H):
            ans_array[k][i] += count

# print(ans_array)

ans = 0
for ar in ans_array:
    ans = max(ans, max(ar) - 1)
print(ans)

Submission status: Accepted

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

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
S = np.array([[int(t == ".") for t in s] for s in S])

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)

best_count = 0

for w in range(W):
    if w == 0:
        L[:, w] = S[:, w]
    else:
        L[:, w] = (L[:, w-1] + 1) * S[:, w]

for w in range(W-1, -1, -1):
    if w == W-1:
        R[:, w] = S[:, w]
    else:
        R[:, w] = (R[:, w+1] + 1) * S[:, w]

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

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

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

Submission status: Accepted

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

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(1, w):
    if not s[i][j] == '#' and s[i][j-1] == '.':
      l[i][j] = l[i][j-1] + 1

for i in range(h):
  for j in range(w-2, -1, -1):
    if not s[i][j] == '#' and s[i][j+1] == '.':
      r[i][j] = r[i][j+1] + 1

for j in range(w):
  for i in range(1, h):
    if not s[i][j] == '#' and s[i-1][j] == '.':
      u[i][j] = u[i-1][j] + 1

for j in range(w):
  for i in range(h-2, -1, -1):
    if not s[i][j] == '#' and s[i+1][j] == '.':
      d[i][j] = d[i+1][j] + 1

ret = 0
for i in range(h):
  for j in range(w):
    if not s[i][j] == '#':
      t = l[i][j] + r[i][j] + u[i][j] + d[i][j]
      if ret < t:
        ret = t

print(ret+1)

Submission status: Accepted

Solution code:
import numpy as np

h, w = [int(i) for i in input().split()]
grid = []
for i in range(h):
    grid.append(list(input()))
grid = (np.array(grid) == ".") * 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)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]

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

Submission status: Accepted

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

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

ans = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if sq[i - 1][j - 1] == '#':
            left[i][j] = 0
            up[i][j] = 0
        else:
            left[i][j] = left[i][j - 1] + 1
            up[i][j] = up[i - 1][j] + 1
for _i in range(h, 0, -1):
    for _j in range(w, 0, -1):
        if sq[_i - 1][_j - 1] == '#':
            right[_i][_j] = 0
            down[_i][_j] = 0
        else:
            right[_i][_j] = right[_i][_j + 1] + 1
            down[_i][_j] = down[_i + 1][_j] + 1

            temp = up[_i][_j] + down[_i][_j] + left[_i][_j] + right[_i][_j] 
            if temp > ans:
                ans = temp

print(ans - 3)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d

"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while x < W:
        while y < H:
            if grid[y][x] == '#':
                y += 1
                continue
            ry = y
            while ry < H and grid[ry][x] != '#':
                ry += 1
            for yy in range(y, ry):
                res_y[yy][x] = ry-y
            y = ry
        y = 0
        x += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import defaultdict


H, W = map(int, input().split())
mass = list()
for i in range(H):
    mass.append(input())

values_col = defaultdict(int)
values_row = defaultdict(int)

ind_row = [[0 for i in range(W)] for j in range(H)]
ind_col = [[0 for i in range(W)] for j in range(H)]

ind = 0
for i, m_row in enumerate(mass):
    ind += 1
    for j, chr in enumerate(mass[i]):
        if chr == '#':
            ind += 1
        else:
            values_row[ind] += 1
            ind_row[i][j] = ind

# print('ROW')
# for i in range(H):
#     for j in range(W):
#         print(values_row[ind_row[i][j]], end=' ')
#     print()

ind = 0
for j in range(W):
    ind += 1
    for i in range(H):
        chr = mass[i][j]
        if chr == '#':
            ind += 1
        else:
            values_col[ind] += 1
            ind_col[i][j] = ind

# print('COL')
# for i in range(H):
#     for j in range(W):
#         print(values_col[ind_col[i][j]], end=' ')
#     print()

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, values_row[ind_row[i][j]] + values_col[ind_col[i][j]] - 1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split(" "))
# True or False
SL = 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) * SL[i]
    D[-i-1] = (D[-i] + 1) * SL[-i-1]
for i in range(W):
    L[:, i] = (L[:, i-1] + 1) * SL[:, i]
    R[:, -i-1] = (R[:, -i] + 1) * SL[:, -i-1]   
print(np.max(L+R+U+D) - 3)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
u = [[0]*w for _ in range(h)]
d = [[0]*w for _ in range(h)]
l = [[0]*w for _ in range(h)]
r = [[0]*w for _ in range(h)]
for i in range(h):
  l[i][0] = int(s[i][0] != "#")
  for j in range(1,w):
    if s[i][j] == "#":
      l[i][j] = 0
    else:
      l[i][j] = l[i][j-1] + 1
  r[i][w-1] = int(s[i][w-1] != "#")
  for j in range(w-2,-1,-1):
    if s[i][j] == "#":
      r[i][j] = 0
    else:
      r[i][j] = r[i][j+1] + 1 
for i in range(w):
  d[0][i] = int(s[0][i] != "#")
  for j in range(1,h):
    if s[j][i] == "#":
      d[j][i] = 0
    else:
      d[j][i] = d[j-1][i] + 1
  u[h-1][i] = int(s[h-1][i] != "#")
  for j in range(h-2,-1,-1):
    if s[j][i] == "#":
      u[j][i] = 0
    else:
      u[j][i] = u[j+1][i] + 1
ans = 0
for i in range(h):
  for j in range(w):
    cur = l[i][j] + r[i][j] + u[i][j] + d[i][j]
    if cur>ans:
      ans = cur
print(ans - 3)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

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

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

for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -(w + 1)] = (R[:, -w] + 1) * S[:, -(w + 1)]

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

Submission status: Accepted

Solution code:
#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            if i > 0:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            if j > 0:
                L[i][j] = L[i][j - 1] + 1
                
for i in range(H - 1, -1, -1):
    for j in range(W - 1, -1, -1):
        if S[i][j] == '.':
            if i == H - 1:
                D[i][j] = 1
            if i < H - 1:
                D[i][j] = D[i + 1][j] + 1
            if j == W - 1:
                R[i][j] = 1
            if j < W - 1:
                R[i][j] = R[i][j + 1] + 1                
        
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            tmp = U[i][j]  + D[i][j] + L[i][j] + R[i][j] - 3
            ans = max(ans, tmp)
            
print(ans)

Submission status: Accepted

Solution code:
H,W =list(map(int,input().split(" ")))
mass  = []
for _ in range(H):
    mass.append(input() + "#")

mass.append((W+1)*"#")
tate = [[0 for _ in range(W+1)] for _ in range(H+1)]
yoko = [[0 for _ in range(W+1)] for _ in range(H+1)]
co = 0
for w in range(W+1):
    st = 0
    for h in range(H+1):
        c = mass[h][w]
        if c == "#":
            for temp in range(st,h):
                tate[temp][w] = co
            st = h + 1
            co = 0
        else:
            co += 1

co = 0
for h in range(H+1):
    st = 0
    for w in range(W+1):
        c = mass[h][w]
        if c == "#":
            for temp in range(st,w):
                yoko[h][temp] = co
            st = w + 1
            co = 0
        else:
            co += 1



ans = 0
for h in range(H):
    for w in range(W):
        cand = tate[h][w] + yoko[h][w]
        if tate[h][w] > 0 and yoko[h][w] > 0:
            cand -= 1
        if cand > ans and mass[h][w] != "#":
            ans =  cand


print(ans)

Submission status: Accepted

Solution code:
import copy
H, W = [int(_) for _ in input().split()]
S = []
for _ in range(H):
    S += [1 if _ == '.' else 0 for _ in list(input())]
S += [0] * W
SL = copy.copy(S)
SR = copy.copy(S)
SU = copy.copy(S)
SD = copy.copy(S)
for h in range(H):
    for i in range(W * h + 1, W * (h + 1)):
        if SL[i]:
            SL[i] = SL[i - 1] + 1
        else:
            SL[i] = 0
for h in range(H):
    for i in range(W * h - 2, W * (h - 1) - 1, -1):
        if SR[i]:
            SR[i] = SR[i + 1] + 1
        else:
            SR[i] = 0
for w in range(W):
    for i in range(W + w, W * H + w, W):
        if SU[i]:
            SU[i] = SU[i - W] + 1
        else:
            SU[i] = 0
for w in range(W):
    for i in range(W * (H - 2) + w - 1, -1, -W):
        if SD[i]:
            SD[i] = SD[i + W] + 1
        else:
            SD[i] = 0
score = 0
print(max((SL[_] + SR[_] + SU[_] + SD[_] - 3 for _ in range(H * W))))

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)
s = 0
for i in range(H):
    #print(S[i])
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]
    s+=1
    #print(up[i])

for i in range(W):
    left[:, i] = (left[:, i-1] + 1) * S[:, i]
    right[:, -i-1] = (right[:, -i] + 1) * S[:, -i-1]
#count the 
print(np.max(up+down+left+right)-3)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9 + 7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    n,m = LI()
    a = [[c!='.' for c in l] for l in sys.stdin.readlines()] + [[True] * m]
    b = [[None] * n for _ in range(m)]
    for i in range(n):
        j = 0
        ai = a[i] + [True]
        while j < m:
            if ai[j]:
                j += 1
            else:
                k = j+1
                while not ai[k]:
                    k += 1
                s = k - j
                b[j][i] = s
                if k < m:
                    b[k][i] = 0
                j = k

    r = 0
    c = [0] * n
    for j in range(m):
        bj = b[j]
        for i in range(n):
            if bj[i] is None:
                continue
            c[i] = bj[i]
        i = 0
        while i < n:
            if a[i][j]:
                i += 1
            else:
                k = i+1
                while not a[k][j]:
                    k += 1
                t = max(c[i:k]) + k - i
                if r < t:
                    r = t
                i = k

    return r - 1


print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W = (int(i) for i in input().split())
#e = [[i for i in input().split()] for i in range(H)]
e = []
for x in range(H):
    e.append(list(input()))

L = [[0] * W for i in [1] * H]
R = [[0] * W for i in [1] * H]
D = [[0] * W for i in [1] * H]
U = [[0] * W for i in [1] * H]
totalmax = 0

for i in range(H):
    for j in range(W):
        if e[i][j] == ".":
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        if e[i][W-1-j] == ".":
            #print(i, W-1-j)
            if W-1-j == W-1:
                R[i][W-1-j] = 1
            else:
                R[i][W-1-j] = R[i][W-j] + 1
                #print(R[i][W-j-2])
            #print(R[i][W-j-1])
        if e[i][j] == ".":
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
        if e[H-1-i][j] == ".":
            if H-1-i == H-1:
                D[H-1-i][j] = 1
            else:
                D[H-1-i][j] = D[H-i][j] + 1

for i in range(H):
    #print("")
    for j in range(W):
        totalmax = max(totalmax, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
        #print(L[i][j],R[i][j], D[i][j], U[i][j], end="/")



print(totalmax)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [list(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)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    if s[i][0] == '.':
        L[i][0] = 1
    for j in range(1, w):
        if s[i][j] == '.':
            L[i][j] = L[i][j-1] + 1
    if s[i][w-1] == '.':
        R[i][w-1] = 1
    for j in range(w-2, -1, -1):
        if s[i][j] == '.':
            R[i][j] = R[i][j+1] + 1

for j in range(w):
    if s[0][j] == '.':
        U[0][j] = 1
    for i in range(1, h):
        if s[i][j] == '.':
            U[i][j] = U[i-1][j] + 1
    if s[h-1][j] == '.':
        D[h-1][j] = 1
    for i in range(h-2, -1, -1):
        if s[i][j] == '.':
            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:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
up =    [[0]*(W+2) for _ in range(H+2)]
down =  [[0]*(W+2) for _ in range(H+2)]
left =  [[0]*(W+2) for _ in range(H+2)]
right = [[0]*(W+2) for _ in range(H+2)]
 
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i-1][j-1] == '.':
            up[i][j] = up[i-1][j] + 1
            left[i][j] = left[i][j-1] + 1
        
        if S[-i][-j] == '.':
            down[-1-i][-1-j] = down[-i][-1-j] + 1
            right[-1-i][-1-j] = right[-1-i][-j] + 1
 
ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        ans = max(ans, up[i][j]+down[i][j]+left[i][j]+right[i][j]-3)
print(ans)