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:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

H, W = mi()
S = []
#周りを囲う
S.append('#'*(W+2))
for _ in range(H):
  S.append(''.join(('#',input(),'#')))
S.append('#'*(W+2))

#まずは行を走査
#各行各セルの横向きに繋がったマスを入れる配列を作る
hnum = [[0]*(W+2) for _ in range(H+2)] #添字を揃えるためにダミーを入れる

for i in range(1, H+2): #1～H以外はダミーだが、H+1も走査しないと障害物にぶつからず、処理されない。iはその時の行番号を示す
  noww = 0 #今見ている列の番号
  tmphnum = 0 #現状繋がっているセルの数を入れていく
  tmphnumstartidx = -1 #繋がり始めたセルの列番号。最初は「未発見」の意を表す-1を入れておく
  for cell in S[i]: #行の各セルを走査
    if cell=='#': #hnumは元々0が入っているので今回いじらなくていい
      #ただし、連結が途切れた場合の処理が必要
      if tmphnumstartidx != -1:
        #連結部分のhnumに、tmphnumを代入する
        for j in range(tmphnumstartidx, noww): #1つ前まで全て
          hnum[i][j] = tmphnum
        tmphnumstartidx = -1 #フラグを兼ねているので、-1にリセット
        tmphnum = 0 #連結セル数も、途切れたので0にリセット
    else: #セルが'.'だった場合
      #繋がるセルの中で一番左端なら、繋がり始めの処理をする
      if tmphnumstartidx == -1:
        tmphnum = 1
        tmphnumstartidx = noww
      else: #左のセルに連結したなら
        tmphnum += 1 #連結セルが1個増えた
    #なんにせよ、noww+=1して次のセル番号に変える
    noww += 1

#今度は列を走査して、ansを最大値で更新していく
ans = 0
#列は文字列になっていないので、計算は遅いかもしれないが、直接S[][]で読んでいくことにする

#今度はiが列番号を表しているので注意！！
for i in range(1, W+2): #1～W以外はダミーだが、W+1も処理しないと障害物にぶつからず処理されないから困る。iはその時の列番号を示す
  tmpwnum = 0 #現状繋がっているセルの数を入れていく
  tmpwnumstartidx = -1 #繋がり始めたセルの行番号。最初は「未発見」の意を表す-1を入れておく
  #今度はjが行番号を表しているので注意！！
  for j in range(1, H+2): #列の各セルを走査
    cell = S[j][i] #わかりやすくするためcellに代入
    if cell=='#': #hnumは元々0が入っているので今回いじらなくていい
      #ただし、連結が途切れた場合の処理が必要
      #ちなみに、#の場合が答えになるはずはないので、答えの判定はしなくていい
      if tmpwnumstartidx != -1:
        #連結が途切れた場合の処理、つまり一つ前のセルまでの答え判定
        #pは、遡って見ているセルの行番号を示す
        for p in range(tmpwnumstartidx, j): #1つ前まで全て
          ans = max(tmpwnum + hnum[p][i] - 1, ans)
        tmpwnumstartidx = -1 #フラグを兼ねているので、-1にリセット
        tmpwnum = 0 #連結セル数も、途切れたので0にリセット
    else: #セルが'.'だった場合
      #繋がるセルの中で一番上なら、繋がり始めの処理をする
      if tmpwnumstartidx == -1:
        tmpwnum = 1
        tmpwnumstartidx = j
      else: #左のセルに連結したなら
        tmpwnum += 1 #連結セルが1個増えた

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(H: int, W: int, S: "List[List[str]]"):
    arr_s = np.array(S)
    arr_s = np.where(arr_s == ".", 1, 0)
    arr_v = np.zeros((H, W), dtype=int)
    arr_h = np.zeros((H, W), dtype=int)
    arr_v[0, :] = arr_s[0, :]
    arr_h[:, 0] = arr_s[:, 0]

    for i in range(H-1):
        arr_v[i+1, :] = (arr_v[i, :] + 1) * arr_s[i+1, :]
    
    for i in range(H-2, -1, -1):
        arr_v[i, :] = np.where(arr_v[i, :] > 0, np.maximum(arr_v[i+1, :], arr_v[i, :]), 0)

    for i in range(W-1):
        arr_h[:, i+1] = (arr_h[:, i] + 1) * arr_s[:, i+1]
    
    for i in range(W-2, -1, -1):
        arr_h[:, i] = np.where(arr_h[:, i] > 0, np.maximum(arr_h[:, i+1], arr_h[:, i]), 0)
    
    print(np.max(arr_v + arr_h) - 1)

    return


# Generated by 1.1.4 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 = [ [c for c in next(tokens)] for _ in range(H) ]  # type: "List[List[str]]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

row_blocks = []
for r in range(H):
    t = []
    x = 0
    for c in range(W):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(W - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = []
    x = 0
    for r in range(H):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(H - 1, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = row_blocks[r][c] + col_blocks[c][r] - 1
        ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron, log
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys

#sys.stdin=open("./testfile1.py","r")
raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()
f5=lambda : raw_input().split()


def main():
    
    h,w=f1()
    a1=[[0]*w for i in xrange(h)]
    a2=[[0]*w for i in xrange(h)]
    a=[]

    inf=-10**1
    for i in xrange(h):
        a.append(f4())

    for i in xrange(h):
        oc=1
        m=inf
        for j in xrange(w):
            if a[i][j]=='#':
                k=j-1
                while k>-1 and a[i][k]!='#':
                    a1[i][k]=oc-1
                    k=k-1
                oc=1
                a1[i][j]=inf
            else:
                a1[i][j]=oc
                oc=oc+1
        if a[i][j]!='#':
            k=j-1
            while k>-1 and a[i][k]!='#':
                a1[i][k]=oc-1
                k=k-1

    for i in xrange(w):
        oc=1
        for j in xrange(h):
            if a[j][i]=='#':
                k=j-1
                while k>-1 and a[k][i]!='#':
                    a2[k][i]=oc-1
                    k=k-1
                oc=1
                a2[j][i]=inf
            else:
                a2[j][i]=oc
                oc=oc+1
        
        if a[j][i]!='#':
            k=j-1
            while k>-1 and a[k][i]!='#':
                a2[k][i]=oc-1
                k=k-1
        
    ans=inf
    for i in xrange(h):
        for j in xrange(w):
            #if i==j==1:
            #    #print a1[i][j],a2[i][j], a[i][j]
            if a[i][j]!='#':
                oc=a1[i][j]+a2[i][j]-1
                #print oc
                if oc>ans:
                    ans=oc

    # for i in xrange(h):
    #    print a1[i], a2[i]
    print ans


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# import numpy as np

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

S = [None] * H
# ans = np.zeros((H, W))
ans = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    s_tmp = [-1] * W
    s = input()
    for j, c in enumerate(s):
        if c == "#":
            s_tmp[j] = 1
        else:
            s_tmp[j] = 0
    S[i] = s_tmp

max_tmp = 0
coord = (-1, -1)
for i in range(H):
    # 左から右
    tmp = 0
    for j in range(W):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        # ans[i, j] += tmp
        ans[i][j] += tmp
    # 右から左
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        # ans[i, j] += tmp
        ans[i][j] += tmp

# 右から左
for i in range(W):
    # 上から下
    tmp = 0
    for j in range(H):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        # ans[j, i] += tmp
        ans[j][i] += tmp
    # 下から上
    tmp = 0
    for j in reversed(range(H)):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        # ans[j, i] += tmp
        ans[j][i] += tmp
        # if ans[j, i] > max_tmp:
        if ans[j][i] > max_tmp:
            # max_tmp = ans[j, i]
            max_tmp = ans[j][i]
            coord = (j, i)

score = 1

tmp_x = coord[1]
while True:
    tmp_x -= 1
    if tmp_x < 0:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_x = coord[1]
while True:
    tmp_x += 1
    if tmp_x >= W:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y -= 1
    if tmp_y < 0:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y += 1
    if tmp_y >= H:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break

print(score)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)

Submission status: Accepted

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

m = list()
mv = list()
mh = list()

for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)

for i in range(h):
    m.append(input())

for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c

for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c

res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)

Submission status: Accepted

Solution code:

# s = input()
# n = int(input())
# A = list(map(int, input().split()))
H, W = map(int, input().split())
S = []
vertical = []
horizontal = []

for _ in range(H):
    s = input()
    S.append(s)
    vertical.append([-1]*W)
    horizontal.append([-1]*W)

def search_vertical(i, j, current):
    i2 = i

    while not (i2 == H-1 or S[i2+1][j] == '#'):
        i2 += 1
        current += 1

    for i3 in range(i, i2+1):
        vertical[i3][j] = current

def search_horizontal(i, j, current):
    j2 = j

    while  not (j2 == W-1 or S[i][j2+1] == '#'):
        j2 += 1
        current += 1

    for j3 in range(j, j2+1):
        horizontal[i][j3] = current


res = -2
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        if vertical[i][j] == -1:
            search_vertical(i, j, 1)
        if horizontal[i][j] == -1:
            search_horizontal(i, j, 1)
        res = max(res, vertical[i][j] + horizontal[i][j] -1)

# print(vertical)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = numpy.array([[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)])
  g = numpy.array([g, g])

  for x in range(1, c):
    g[0, :, x] += g[0, :, x] * g[0, :, x - 1]

  for x in range(c - 2, -1, -1):
    g[0, :, x] = (g[0, :, x] != 0) * numpy.maximum(g[0, :, x], g[0, :, x + 1])

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

  for y in range(r - 2, -1, -1):
    g[1, y] = (g[1, y] != 0) * numpy.maximum(g[1, y], g[1, y + 1])

  g = g[0] + g[1]

  print(numpy.max(g) - 1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


H,W=rl()
S=[]
for i in range(H):
    S.append(input())
#M = [[0 for w in range(W)] for h in range(H)]
wM = [[0 for w in range(W)] for h in range(H)]
hM = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    cnt = 0
    for w in range(W):
        if S[h][w] == '#':
            #M[h][w] = 1
            wM[h][w-1] = cnt
            cnt = 0
        else:
            wM[h][w] = -1
            cnt += 1
    if cnt != 0:
        wM[h][W-1] = cnt

for h in range(H):
    cnt = 0
    for w in range(W-1,-1,-1):
        if wM[h][w] > 0:
            cnt = wM[h][w]
        elif wM[h][w] == -1:
            wM[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if S[h][w] == "#":
        #if M[h][w] == 1:
            hM[h-1][w] = cnt 
            cnt = 0
        else:
            hM[h][w] = -1
            cnt += 1
    if cnt != 0:
        hM[H-1][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H-1,-1,-1):
        if hM[h][w] > 0:
            cnt = hM[h][w]
        elif hM[h][w] == -1:
            hM[h][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        ret1 = wM[h][w]
        ret2 = hM[h][w]
        ret = ret1 + ret2
        if ret1 != 0 and ret2 != 0:
            ret -= 1
        ans = max(ans,ret)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
rows,cols = list(map(int,raw_input().split()))
grid=[]
up=[]
# down=[]
# left=[]
# right=[]
for i in range(rows):
	grid.append(raw_input())
	up.append([0 for j in range(cols)])
	# down.append([-1 for j in range(cols)])
	# left.append([-1 for j in range(cols)])
	# right.append([-1 for j in range(cols)])
#up
for c in range(cols):
	count = 1
	for r in range(rows-1,-1,-1):
		if(grid[r][c]=='#'):
			count=1
		else:
			up[r][c]+=count
			count+=1

#down

for c in range(cols):
	count = 1
	for r in range(rows):
		if(grid[r][c]=='#'):
			count=1
		else:
			up[r][c]+=count
			count+=1

#left

for c in range(rows):
	count = 1
	for r in range(cols-1,-1,-1):
		if(grid[c][r]=='#'):
			count=1
		else:
			up[c][r]+=count
			count+=1

#right

for c in range(rows):
	count = 1
	for r in range(cols):
		if(grid[c][r]=='#'):
			count=1
		else:
			up[c][r]+=count
			count+=1
ans = 1
for x in range(rows):
	for y in range(cols):
		if(grid[x][y]=='.'):
			ans=max(ans,(up[x][y]-3))
print(ans)

Submission status: Accepted

Solution code:

class UnionFind:

    # n is element num
    def __init__(self, n):
        self.n = n
        self.parent = [-1] * (n + 1)
        self.rnk = [0]*(n+1)

    # find root of x node
    def find_root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]

    # union disjoint sets of x and y
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)

        if x == y:
            return

        elif self.rnk[x] > self.rnk[y]:
            self.parent[x] += self.parent[y]  # update num of nodes in united tree
            self.parent[y] = x

        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y

            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # check x and y are in same tree
    def is_same_tree(self, x, y):
        return self.find_root(x) == self.find_root(y)

    # count nodes in tree what x belong to
    def count_nodes(self, x):
        return -self.parent[self.find_root(x)]


def read_input():
    h, w = map(int, input().split())

    board = []
    for i in range(h):
        board.append([0 if c == '.' else 1 for c in input()])

    return h, w, board


def union(vec):
    u = UnionFind(len(vec))

    for i, (v1, v2) in enumerate(zip(vec, vec[1:])):
        if v1 == v2 == 0:
            u.unite(i, i + 1)

    return u

def submit():
    h, w, board = read_input()

    hunions = []
    for i in range(h):
        hunions.append(union(board[i]))

    wunions = []
    for j in range(w):
        v = [board[i][j] for i in range(h)]
        wunions.append(union(v))


    max_lit = 0
    for i in range(h):
        for j in range(w):
            if board[i][j] == 0:
                hv = hunions[i].count_nodes(j)
                wv = wunions[j].count_nodes(i)

                if max_lit < hv + wv - 1:
                    max_lit = hv + wv - 1


    print(max_lit)



if __name__ == '__main__':
    submit()

Submission status: Accepted

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

for i in range(h):
    f = 0
    j = 0
    m = 0
    while j < w:
        if s[i][j] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    yoko[i][p] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            yoko[i][p] = j - f

for i in range(w):
    f = 0
    j = 0
    m = 0
    while j < h:
        if s[j][i] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    tate[p][i] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            tate[p][i] = j - f
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q = yoko[i][j] + tate[i][j] - 1
            if q > ans:
                ans = q
print(ans)

Submission status: Accepted

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

S=[input() for i in range(H)]
color1 = -1
color_list1 = [[-1 for j in range(W)] for i in range(H)]
color_num1 = [0 for i in range(H*W)]
flag=True
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            flag=True
        else:
            if j==0:
                flag=True
            if flag:
                color1+=1
                color_list1[i][j]=color1
                color_num1[color1]+=1
                flag=False
            else:
                color_list1[i][j]=color1
                color_num1[color1]+=1

color2 = -1
color_list2 = [[-1 for j in range(W)] for i in range(H)]
color_num2 = [0 for i in range(H*W)]
flag=True
for j in range(W):
    for i in range(H):
        if S[i][j]=="#":
            flag=True
        else:
            if i==0:
                flag=True
            if flag:
                color2+=1
                color_list2[i][j]=color2
                color_num2[color2]+=1
                flag=False
            else:
                color_list2[i][j]=color2
                color_num2[color2]+=1
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            ans=max(color_num1[color_list1[i][j]]+color_num2[color_list2[i][j]]-1,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
g=[["#"]*(w+1)]+[["#"]+list(input())+["#"]for _ in range(h)]+[["#"]*(w+1)]
gg=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  k=1
  for j in range(1,w+1):
    if g[i][j]==".":
      gg[i-1][j-1]=k;k+=1
    else:k=1
  d=gg[i-1][-1]
  for j in range(1,w+1):
    if gg[i-1][-j]!=0:gg[i-1][-j]=d
    elif j!=w:d=gg[i-1][-j-1]
ggg=[[0]*w for _ in range(h)]
for j in range(1,w+1):
  k=1
  for i in range(1,h+1):
    if g[i][j]==".":
      ggg[i-1][j-1]=k;k+=1
    else:k=1
  d=ggg[-1][j-1]
  for i in range(1,h+1):
    if ggg[-i][j-1]!=0:ggg[-i][j-1]=d
    elif i!=h:d=ggg[-i-1][j-1]
ans=0
for i in range(h):
  for j in range(w):ans=max(ans,gg[i][j]+ggg[i][j])
print(ans-1)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    S = [["#"] * W ]+ ["#"+ST()+"#" for _ in range(H)]
    up = [[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)]
    down = [[0] * (W + 2) for _ in range(H + 2)]
    
    for h in range(1, H+1):
        for w in range(1, W + 1):
            if S[h][w] == "#":
                continue
            else:
                up[h][w] = up[h-1][w] + 1
                left[h][w] = left[h][w-1] + 1
    for h in range(1, H+1)[::-1]:
        for w in range(1, W+1)[::-1]:
            if S[h][w] == "#":
                continue
            else:
                down[h][w] = down[h+1][w] + 1
                right[h][w] = right[h][w + 1] + 1
                
    ans = 0
    for h in range(1, H+1):
        for w in range(1, W + 1):
            if S[h][w] == ".":
                ans = max(ans, (left[h][w-1] + right[h][w+1]) + (up[h-1][w] + down[h+1][w])+1)
                #print(ans,h,w , left[h][w] , right[h][w]) , (up[h][w] , down[h][w])
                
    print(ans)

    """
    cumsum1 = [[] for _ in range(H)]
    cumsum2 = [[] for _ in range(W)]
    
    for h in range(H):
        for w in range(W):
            if w == 0:
                cumsum1[h].append(int(S[h][w] == "#"))
            else:
                cumsum1[h].append(cumsum1[h][-1] + (S[h][w] == "#"))
            if h == 0:
                cumsum2[w].append(int(S[h][w] == "#"))
            else:
                cumsum2[w].append(cumsum2[w][-1] + (S[h][w] == "#"))
    #print(*cumsum2,sep="\n") 
    left_right = [[0] * W for _ in range(H)]
    up_down = [[0] * H for _ in range(W)]
    sharp = False:
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                sharp = True

            else:

    ans=0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            else:
                c1 = cumsum1[h][w]
                c2 = cumsum2[w][h]
                #print((h, w), cumsum1[h], cumsum2[w], sep="\n")
                b1,b2,b3,b4 = bisect_right(cumsum1[h], c1) ,bisect_left(cumsum1[h], c1) , bisect_right(cumsum2[w], c2) , bisect_left(cumsum2[w], c2)
                num = b1 - b2 + b3 - b4 -3 +(b2==0) + (b4 == 0) 
                #num = bisect_right(cumsum1[h], c1) - bisect_left(cumsum1[h], c1) + bisect_right(cumsum2[w], c2) - bisect_left(cumsum2[w], c2)-1 + (h==0)+(w==0)
                #print(num,b1,b2,b3,b4)
                ans=max(ans,num)
    print(ans)"""
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

h,w = get_nums_l()

lines = sys.stdin.readlines()

xtable = [ [-1]*w for _ in range(h) ]
ytable = [ [-1]*w for _ in range(h) ]
yoko = [0] * (h*w)
tate = [0] * (h*w)

cur = 0
for y in range(h):
    for x in range(w):

        c = lines[y][x]

        if c == ".":
            yoko[cur] += 1
            xtable[y][x] = cur

            if x == (w-1):
                cur += 1
        else:
            cur += 1

cur = 0
for x in range(w):
    for y in range(h):

        c = lines[y][x]

        if c == ".":
            tate[cur] += 1
            ytable[y][x] = cur

            if y == (h-1):
                cur += 1
        else:
            cur += 1
        
ans = 0
for y in range(h):
    for x in range(w):
        if xtable[y][x] != -1:
            v = yoko[xtable[y][x]] + tate[ytable[y][x]] - 1
            
            if ans < v:
                ans = v

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)] + ['#' * (w + 1)]
l1 = [[0] * (w + 1) for i in range(h + 1)]
l2 = [[0] * (w + 1) for i in range(h + 1)]
for i in range(h):
    tmps = 0
    for j in range(w + 1):
        if s[i][j] == '#':
            l1[i][tmps] += j - tmps
            l1[i][j] -= j - tmps
            tmps = j + 1
for i in range(h):
    for j in range(w):
        l1[i][j + 1] += l1[i][j]
for j in range(w):
    tmps = 0
    for i in range(h + 1):
        if s[i][j] == '#':
            l2[tmps][j] += i - tmps
            l2[i][j] -= i - tmps
            tmps = i + 1
for j in range(w):
    for i in range(h):
        l2[i + 1][j] += l2[i][j]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, l1[i][j] + l2[i][j])
print(ans - 1)

Submission status: Accepted

Solution code:
sizeI, sizeJ = map(int, input().split())
a = [input().strip() for _ in range(sizeI)]

rowVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for i in range(sizeI):
    for j in range(sizeJ):
        if j == 0:
            rowVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                rowVal[i][j] = rowVal[i][j - 1] + 1
            else:
                rowVal[i][j] = 0
    for j in range(sizeJ - 2, -1, -1):
        if rowVal[i][j] and rowVal[i][j + 1]:
            rowVal[i][j] = rowVal[i][j + 1]

colVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for j in range(sizeJ):
    for i in range(sizeI):
        if i == 0:
            colVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                colVal[i][j] = colVal[i - 1][j] + 1
            else:
                colVal[i][j] = 0
    for i in range(sizeI - 2, -1, -1):
        if colVal[i][j] and colVal[i + 1][j]:
            colVal[i][j] = colVal[i + 1][j]

ret = 0
for i in range(sizeI):
    for j in range(sizeJ):
        ret = max(ret, rowVal[i][j] + colVal[i][j] - 1)
print(ret)

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:
#!/usr/bin/env python3
import sys

def solve(H: int, W: int, S: "List[str]"):
    tab = [0 for i in range(H*W)]
    for i in range(W):
        acc0, acc1 = 0, 0
        for j in range(H):
            j2 = H-1-j
            tab[W*j+i] += acc0
            tab[W*j2+i] += acc1
            acc0 = 0 if S[j][i] == "#" else acc0+1
            acc1 = 0 if S[j2][i] == "#" else acc1+1
    for j in range(H):
        acc2, acc3 = 0, 0
        for i in range(W):
            i2 = W-1-i
            tab[W*j+i] += acc2
            tab[W*j+i2] += acc3
            if S[j][i] == "#":
                tab[W*j+i] = -10**10
            else:
                tab[W*j+i] += 1
            acc2 = 0 if S[j][i] == "#" else acc2+1
            acc3 = 0 if S[j][i2] == "#" else acc3+1
    
    print(max(max(tab), 0))

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 = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()