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 = map(int,input().split())
S = [input() for _ in range(h)]
C = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    new = []
    flag = False
    cnt = 0
    for j in range(w):
        if flag:
            if S[i][j] == "#":
                for k in new:
                    C[i][k] += cnt
                cnt = 0
                new = []
                flag = False
            else:
                cnt += 1
                new.append(j)
        else:
            if S[i][j] == ".":
                cnt = 1
                flag = True
                new.append(j)
    else:
        if flag:
            for k in new:
                C[i][k] += cnt
            cnt = 0
            flag = False
for j in range(w):
    new = []
    flag = False
    cnt = 0
    for i in range(h):
        if flag:
            if S[i][j] == "#":
                for k in new:
                    C[k][j] += cnt
                cnt = 0
                new = []
                flag = False
            else:
                cnt += 1
                new.append(i)
        else:
            if S[i][j] == ".":
                cnt = 1
                flag = True
                new.append(i)
    else:
        if flag:
            for k in new:
                C[k][j] += cnt
            cnt = 0
            flag = False
ans = -1
for i in range(h):
    ans = max(ans,max(C[i]))
print(ans-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    # L[i][j]: このマスが光る時に左方向に照らされるマスの個数
    L = [[0]*W for _ in range(H)]
    R = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    # U[i][j]: このマスが光る時に上方向に照らされるマスの個数
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H, W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(input()) for i in range(H)) #改行行列

    cnt=[[[0]*W for _ in range(H)] for _ in range(4)]
    for i in range(0,H):
        mj=-1
        for j in range(0,W):
            if S[i][j]=="#":
                mj=j
                continue
            cnt[0][i][j]=(j-mj-1)
    for i in range(0,H):
        mj=W
        for j in range(W-1,-1,-1):
            if S[i][j]=="#":
                mj=j
                continue
            cnt[1][i][j]=(mj-j-1)

    for i in range(0,W):
        mj=-1
        for j in range(0,H):
            if S[j][i]=="#":
                mj=j
                continue
            #printe(j,i)
            cnt[2][j][i]=(j-mj-1)
    for i in range(0,W):
        mj=H
        for j in range(H-1,-1,-1):
            if S[j][i]=="#":
                mj=j
                continue
            cnt[3][j][i]=(mj-j-1)
    
    ans=0
    for i in range(0,H):
        for j in range(0,W):
            if S[i][j]=="#":
                continue
            x=cnt[0][i][j]+cnt[1][i][j]+cnt[2][i][j]+cnt[3][i][j]+1    
            ans=max(x,ans)
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
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):
    for j in range(W):
        if S[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] += 1
        else:
            L[i][j] += L[i][j-1] + 1
for i in range(H):
    for j in range(-1,-W-1,-1):
        if S[i][j] == '#':
            continue
        elif j == -1:
            R[i][j] += 1
        else:
            R[i][j] += R[i][j+1] + 1
for i in range(W):
    for j in range(H):
        if S[j][i] == '#':
            continue
        elif j == 0:
            U[j][i] += 1
        else:
            U[j][i] += U[j-1][i] + 1
for i in range(W):
    for j in range(-1,-H-1,-1):
        if S[j][i] == '#':
            continue
        elif j == -1:
            D[j][i] += 1
        else:
            D[j][i] += D[j+1][i] + 1
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    H, W = LI()
    maze = SR(H)
    # top, right, bottom, left
    info = [[0 for _ in range(W)] for _ in range(H)]

    # from top to bottom
    for w in range(W):
        current = 0
        for h in range(H):
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from right to left
    for h in range(H):
        current = 0
        for w in range(W)[::-1]:
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from bottom to top
    for w in range(W):
        current = 0
        for h in range(H)[::-1]:
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    # from  left to right
    for h in range(H):
        current = 0
        for w in range(W):
            if maze[h][w] == "#":
                current = 0
            else:
                info[h][w] += current
                current += 1

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == ".":
                ans = max(ans, info[h][w] + 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [0]*h
for i in range(h):
    s[i] = list(input())
ver = [[0 for j in range(w)] for i in range(h)]
hol = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            pass
        elif j >= 1 and hol[i][j-1] != 0:
            hol[i][j] = hol[i][j-1]
        else:
            for k in range(2000):
                if j+k+1 >= w:
                    break
                if s[i][j+k+1] == "#":
                    break
            hol[i][j] = k+1
            
for j in range(w):
    for i in range(h):
        if s[i][j] == "#":
            pass
        elif ver[i][j] == 0 and i >= 1 and ver[i-1][j] != 0:
            ver[i][j] = ver[i-1][j]
        else:
            for k in range(2000):
                if i+k+1 >= h:
                    break
                elif s[i+k+1][j] == "#":
                    break
            ver[i][j] = k+1

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

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4 6
#..#..
.....#
....#.
#.#...
'''

def transpose(m):
	rez = [[m[j][i] for j in range(len(m))] for i in range(len(m[0]))] 
	return rez

def giveLightIntervals(L,h,w):
	l = [[] for i in range(h)]
	for i in range(h):
		s,e,c = '','',0
		for j in range(w):
			if(L[i][j] == '#'):
				if(c > 0):
					e = j
					l[i].append([s,e-1])
					c = 0
				s,e = '',''
			else:
				if(s == ''):
					s = j
				c += 1
		if(L[i][-1] == '.'):
			l[i].append([s,w-1])
	return l

def solve(L,h,w):
	T = transpose(L)
	l = giveLightIntervals(L,h,w)
	t = giveLightIntervals(T,w,h)

	H = [[0 for i in range(w)] for j in range(h)]
	W = [[0 for i in range(h)] for j in range(w)]

	for i in range(h):
		zz = 0
		for j in range(w):
			if(len(l[i]) > zz):
				s,e = l[i][zz]
				val = e - s + 1
				if(s <= j <= e):
					H[i][j] = val
				if(j == e):
					zz += 1
			else:
				break

	for i in range(w):
		zz = 0
		for j in range(h):
			if(len(t[i]) > zz):
				s,e = t[i][zz]
				val = e - s + 1
				if(s <= j <= e):
					W[i][j] = val
				if(j == e):
					zz += 1
			else:
				break

	ans = 0

	for i in range(h):
		for j in range(w):
			curr = H[i][j] + W[j][i] - 1
			ans = max(ans,curr)

	return ans


H,W = list(map(int, stdin.readline().rstrip().split()))
L = []
for m in range(H):
	L.append(list(input()))
ans = solve(L,H,W)
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4 6
#..#..
.....#
....#.
#.#...

6 4
#..#
....
...#
#...
..#.
.#..

0 -> [[1,2][4,5]]
1 -> [[0,4]]
2 -> [[0,3],[5,5]]
3 -> [[1,1],[3,5]]

0 -> [[1,2]]
1 -> [[0,3]]
2 -> [[0,2]]
3 -> [[1,3]]
4 -> [[0,2],[3,3]]
5 -> [[0,0],[2,3]]

'''

def transpose(m):
	rez = [[m[j][i] for j in range(len(m))] for i in range(len(m[0]))] 
	return rez

def giveLightIntervals(L,h,w):
	l = [[] for i in range(h)]
	for i in range(h):
		s,e,c = '','',0
		for j in range(w):
			if(L[i][j] == '#'):
				if(c > 0):
					e = j
					l[i].append([s,e-1])
					c = 0
				s,e = '',''
			else:
				if(s == ''):
					s = j
				c += 1
		if(L[i][-1] == '.'):
			l[i].append([s,w-1])
	return l

def solve(L,h,w):
	T = transpose(L)
	l = giveLightIntervals(L,h,w)
	t = giveLightIntervals(T,w,h)

	H = [[0 for i in range(w)] for j in range(h)]
	W = [[0 for i in range(h)] for j in range(w)]

	for i in range(h):
		zz = 0
		for j in range(w):
			if(len(l[i]) > zz):
				s,e = l[i][zz]
				val = e - s + 1
				if(s <= j <= e):
					H[i][j] = val
				if(j == e):
					zz += 1
			else:
				break

	for i in range(w):
		zz = 0
		for j in range(h):
			if(len(t[i]) > zz):
				s,e = t[i][zz]
				val = e - s + 1
				if(s <= j <= e):
					W[i][j] = val
				if(j == e):
					zz += 1
			else:
				break

	ans = 0

	for i in range(h):
		for j in range(w):
			curr = H[i][j] + W[j][i] - 1
			ans = max(ans,curr)

	return ans


H,W = list(map(int, stdin.readline().rstrip().split()))
L = []
for m in range(H):
	L.append(list(input()))
ans = solve(L,H,W)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]

imos1 = [[0 for j in range(w + 1)] for i in range(h)]
imos2 = [[0 for j in range(w)] for i in range(h + 1)]

cnt1 = 0
start1 = None
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j == 0 or s[i][j - 1] == "#":
                start1 = j
                cnt1 = 1
            else:
                cnt1 += 1
        elif j == 0 or s[i][j - 1] == "#":
            continue
        else:
            imos1[i][start1] = cnt1
            imos1[i][j] = -cnt1
            cnt1 = 0
    if s[i][-1] == ".":
        imos1[i][start1] = cnt1
        imos1[i][-1] = -cnt1
    start1 = None
    cnt1 = 0
for i in range(h):
    for j in range(1, w):
        imos1[i][j] += imos1[i][j - 1]
# for i in range(h):
    # print(*imos1[i][:-1])
# print(imos1)
# print()

cnt2 = 0
start2 = None
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            if j == 0 or s[j - 1][i] == "#":
                start2 = j
                cnt2 = 1
            else:
                cnt2 += 1
        elif j == 0 or s[j - 1][i] == "#":
            continue
        else:
            imos2[start2][i] = cnt2
            imos2[j][i] = -cnt2
            cnt2 = 0
    if s[h - 1][i] == ".":
        imos2[start2][i] = cnt2
        imos2[h][i] -= cnt2
    start2 = None
    cnt2 = 0
for i in range(w):
    for j in range(1, h):
        imos2[j][i] += imos2[j - 1][i]
# for i in range(h):
    # print(*imos2[i])
# print(imos2)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        ans = max(ans, imos1[i][j] + imos2[i][j] - 1)
print(ans)

Submission status: Accepted

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

    g = [list("#" * (w + 2))]
    for _ in range(h):
        g.append(["#"] + list(input()) + ["#"])
    g += [list("#" * (w + 2))]
    area = [[0] * (w + 2) for _ in range(h + 2)]

    for i in range(h + 2):
        cnt = 0
        for j in range(w + 2):
            if g[i][j] == "#":
                for k in range(j - cnt, j):
                    area[i][k] += cnt
                cnt = 0
            else:
                cnt += 1

    for i in range(w + 2):
        cnt = 0
        for j in range(h + 2):
            if g[j][i] == "#":
                for k in range(j - cnt, j):
                    area[k][i] += cnt
                cnt = 0
            else:
                cnt += 1

    res = 0
    for i in range(h + 2):
        for j in range(w + 2):
            res = max(res, area[i][j])
    print(res - 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
g = []
for _ in range(h):
  g.append(input())
l = [[0 for i in range(w)] for j in range(h)]
r = [[0 for i in range(w)] for j in range(h)]
d = [[0 for i in range(w)] for j in range(h)]
u = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if g[i][j] == '.':
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1]+1
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j]+1
for i in reversed(range(h)):
  for j in reversed(range(w)):
    if g[i][j] == '.':
      if j == w-1:
        r[i][j] = 1
      else:
        r[i][j] = r[i][j+1]+1
      if i == h-1:
        d[i][j] = 1
      else:
        d[i][j] = d[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(l[i][j]+r[i][j]+u[i][j]+d[i][j]-3,ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    h,w = map(int, input().split())
    sl = []
    for _ in range(h):
        sl.append(list(input()))

    left_cnts = []
    for hi, row in enumerate(sl):
        curr_left_cnts = []
        curr_cnt = 0
        for i, s in enumerate(row):
            if s == '.':
                curr_left_cnts.append(curr_cnt)
                curr_cnt += 1
            else:
                curr_left_cnts.append(-1)
                curr_cnt = 0
        left_cnts.append(curr_left_cnts)


    right_cnts = []
    for hi, row in enumerate(sl):
        curr_right_cnts = []
        curr_cnt = 0
        for i, s in enumerate(row[::-1]):
            if s == '.':
                curr_right_cnts.append(curr_cnt)
                curr_cnt += 1
            else:
                curr_right_cnts.append(-1)
                curr_cnt = 0
        curr_right_cnts = curr_right_cnts[::-1]
        right_cnts.append(curr_right_cnts)


    sl_t = [list(x) for x in zip(*sl)]
    left_cnts_t = []
    for hi, row in enumerate(sl_t):
        curr_left_cnts = []
        curr_cnt = 0
        for i, s in enumerate(row):
            if s == '.':
                curr_left_cnts.append(curr_cnt)
                curr_cnt += 1
            else:
                curr_left_cnts.append(-1)
                curr_cnt = 0
        left_cnts_t.append(curr_left_cnts)


    right_cnts_t = []
    for hi, row in enumerate(sl_t):
        curr_right_cnts = []
        curr_cnt = 0
        for i, s in enumerate(row[::-1]):
            if s == '.':
                curr_right_cnts.append(curr_cnt)
                curr_cnt += 1
            else:
                curr_right_cnts.append(-1)
                curr_cnt = 0
        curr_right_cnts = curr_right_cnts[::-1]
        right_cnts_t.append(curr_right_cnts)


    ans = 0
    for hi in range(h):
        for wi in range(w):
            if sl[hi][wi] == '#':continue
            cnt = left_cnts[hi][wi] + right_cnts[hi][wi] + left_cnts_t[wi][hi] + right_cnts_t[wi][hi]
            ans = max(ans, cnt)

    print(ans+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

h, w  = map(int,input().split())
sn = [[0]*w for i in range(h)]
 
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            sn[i][j] = 1
sn = np.array(sn)
score = np.zeros_like(sn)
total = np.zeros_like(sn)

score[0] += sn[0]
for i in range(1, h):
    score[i] = (score[i-1] + sn[i]) * sn[i]
total += score

score[h-1] = sn[h-1]
for i in range(h-2, -1, -1):
    score[i] = (score[i+1] + sn[i]) * sn[i]
total += score

score[:,0] = sn[:,0]
for i in range(1, w):
    score[:,i] = (score[:,i-1] + sn[:,i]) * sn[:,i]
total += score

score[:,w-1] = sn[:,w-1]
for i in range(w-2, -1, -1):
    score[:,i] = (score[:,i+1] + sn[:,i]) * sn[:,i]
total += score
    
print(total.max()-3)

Submission status: Accepted

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

grid0 = [[0] * (W + 1) for _ in range(H + 1)]

# L -> R
for i in range(H):
    for j in range(W):
        if X[i][j] == ".":
            grid0[i + 1][j + 1] = grid0[i + 1][j] + 1
        
# L <- R
for i in range(H):
    for j in reversed(range(W)):
        if grid0[i + 1][j] > 0:
            grid0[i + 1][j] = max(grid0[i + 1][j], grid0[i + 1][j + 1])

grid1 = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        if X[i][j] == ".":
            grid1[i + 1][j + 1] = grid1[i][j + 1] + 1

for i in reversed(range(H)):
    for j in range(W):
        if grid1[i][j + 1] > 0:
            grid1[i][j + 1] = max(grid1[i][j + 1], grid1[i + 1][j + 1])

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
H, W = MAP()
S = [input() for _ in range(H)]

w = [[-1]*W for _ in range(H)]
h = [[-1]*W for _ in range(H)]

for i in range(H):
	cnt = 0
	for j in range(W):
		if S[i][j] == ".":
			cnt += 1
			w[i][j] = cnt
		else:
			cnt = 0
	for j in range(W-2, -1, -1):
		if S[i][j] == ".":
			w[i][j] = max(w[i][j], w[i][j+1])


for i in range(W):
	cnt = 0
	for j in range(H):
		if S[j][i] == ".":
			cnt += 1
			h[j][i] = cnt
		else:
			cnt = 0

	for j in range(H-2, -1, -1):
		if S[j][i] == ".":
			h[j][i] = max(h[j][i], h[j+1][i])


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