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 = []
for i in range(H):
    S.append(input())

k = [ [ 0 for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            k[i][j] = 0
        else:
            if j > 0:
                k[i][j] = k[i][j-1] + 1
            else:
                k[i][j] = 1

for i in range(H):
    t = 0
    for j in range(W):
        t = max(t,k[-i-1][-j-1])
        if S[-i-1][-j-1] == "#":
            t = 0
            continue
        k[-i-1][-j-1] = t


kk = [ [ 0 for i in range(W)] for j in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == "#":
            kk[i][j] = 0
        else:
            if i > 0:
                kk[i][j] = kk[i-1][j] + 1
            else:
                kk[i][j] = 1

for j in range(W):
    t = 0
    for i in range(H):
        t = max(t,kk[-i-1][-j-1])
        if S[-i-1][-j-1] == "#":
            t = 0
            continue
        kk[-i-1][-j-1] = t
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue

        ans = max(ans , k[i][j] + kk[i][j] - 1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

H, W = list(map(int, input().split()))
data = [''] * H

for h in range(H):
    data[h] = input()

lights = [[-1 for _ in range(W)] for _ in range(H)]

for h in range(H):
    w = 0
    while w < W:
        if data[h][w] == '#':
            w += 1
            continue
        try:
            floor_count = data[h][w:].index('#')
        except ValueError:
            floor_count = W - w
        for k in range(floor_count):
            lights[h][w+k] += floor_count
        w += floor_count + 1

for w in range(W):
    h = 0
    while h < H:
        if data[h][w] == '#':
            h += 1
            continue
        floor_count = 1
        for i in range(1, H-h):
            if data[h+i][w] == '#':
                break
            floor_count += 1
        for k in range(floor_count):
            lights[h+k][w] += floor_count
        h += floor_count + 1

ans = -1
for h in range(H):
    m = max(lights[h])
    if ans < max(lights[h]):
        ans = m
print(ans)

Submission status: Accepted

Solution code:
import sys
H,W=map(int, raw_input().split())
S=[ sys.stdin.readline().strip() for i in range(H)] 

LSUM=[  [ 0 for w in range(W) ] for h in range(H) ]
RSUM=[  [ 0 for w in range(W) ] for h in range(H) ]
USUM=[ [ 0 for h in range(H) ] for w in range(W) ]
DSUM=[ [ 0 for h in range(H) ] for w in range(W) ]

for h in range(H):
	for w in range(W):
		if S[h][w]==".":
			if w==0:
				LSUM[h][w]=1
			else:
				LSUM[h][w]=LSUM[h][w-1]+1
		elif S[h][w]=="#":
				LSUM[h][w]=0


for h in range(H):
	for w in range(W-1,-1,-1):
		if S[h][w]==".":
			if w==W-1:
				RSUM[h][w]=1
			else:
				RSUM[h][w]=RSUM[h][w+1]+1
		elif S[h][w]=="#":
				RSUM[h][w]=0


for w in range(W):
	for h in range(H):
		if S[h][w]==".":
			if h==0:
				USUM[w][h]=1
			else:
				USUM[w][h]=USUM[w][h-1]+1
		elif S[h][w]=="#":
				USUM[w][h]=0


for w in range(W):
	for h in range(H-1,-1,-1):
		if S[h][w]==".":
			if h==H-1:
				DSUM[w][h]=1
			else:
				DSUM[w][h]=DSUM[w][h+1]+1
		elif S[h][w]=="#":
				DSUM[w][h]=0



ans=0
for h in range(H):
	for w in range(W):
		ans=max(ans , LSUM[h][w]+RSUM[h][w]+USUM[w][h]+DSUM[w][h]-3 )


print ans

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    field = [[0] * w for _ in range(h)]

    for i, row in enumerate(grid):
        row = row + "#"
        cnt = row.count("#")
        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("#", idx + 1)
            for k in range(idx + 1, idx_next):
                field[i][k] = idx_next - idx - 1
            idx = idx_next

    m = 0
    for i, row in enumerate(zip(*grid)):
        row = "".join(row) + "#"
        cnt = row.count("#")
        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("#", idx + 1)
            for k in range(idx + 1, idx_next):
                field[k][i] += idx_next - idx - 1
                if field[k][i] > m:
                    m = field[k][i]
            idx = idx_next
    print(m - 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
s = []
for i in range(h):
    s.append(input())

u = [ ([-1] * w) for i in range(h) ]
d = [ ([ h] * w) for i in range(h) ]
l = [ ([-1] * w) for i in range(h) ]
r = [ ([ w] * w) for i in range(h) ]
for i in range(h):
    ll = -1
    for j in range(w):
        if s[i][j] == '.':
            l[i][j] = ll
        else:
            ll = j
    rr = w
    for j in range(w-1,-1,-1):
        if s[i][j] == '.':
            r[i][j] = rr
        else:
            rr = j

for j in range(w):
    uu = -1
    for i in range(h):
        if s[i][j] == '.':
            u[i][j] = uu
        else:
            uu = i
    dd = h
    for i in range(h-1,-1,-1):
        if s[i][j] == '.':
            d[i][j] = dd
        else:
            dd = i


mx = -1
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            continue
        x = d[i][j] - u[i][j] + r[i][j] - l[i][j] - 3
        mx = max(mx,x)

print(mx)

Submission status: Accepted

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

ans = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


for i in range(h):
  cur = 0
  b = 0
  e = 0
  flag = 0
  for j in range(w):
    if s[i][j]=="." and j==w-1:
      cur += 1
      e = j
      for k in range(b, e+1):
        yoko[i][k] = cur
      cur = 0
    elif flag and s[i][j]==".":
      cur += 1
    elif not flag and s[i][j]==".":
      cur = 1
      flag = 1
      b = j
    elif flag and s[i][j]=="#":
      flag = 0
      e = j-1
      for k in range(b, e+1):
        yoko[i][k] = cur
      cur = 0
      b = j+1
    elif s[i][j]=="." and j==w-1:
      cur += 1
      e = j-1
      for k in range(b, e+1):
        yoko[i][k] = cur
      cur = 0
    else:
      b = j+1


for j in range(w):
  cur = 0
  b = 0
  e = 0
  flag = 0
  for i in range(h):
    if s[i][j]=="." and i==h-1:
      cur += 1
      e = i
      for k in range(b, e+1):
        tate[k][j] = cur
      cur = 0
    if flag and s[i][j]==".":
      cur += 1
    elif not flag and s[i][j]==".":
      cur = 1
      flag = 1
      b = i
    elif flag and s[i][j]=="#":
      flag = 0
      e = i-1
      for k in range(b, e+1):
        tate[k][j] = cur
      cur = 0
      b = i+1
    elif s[i][j]=="." and i==h-1:
      cur += 1
      e = i-1
      for k in range(b, e+1):
        tate[k][j] = cur
      cur = 0
    else:
      b = i+1

ans = 0
for i in range(h):
  for j in range(w):
    if yoko[i][j]>0 and tate[i][j]>0:
      ans = max(ans, yoko[i][j]+tate[i][j]-1)
    else:
      ans = max(ans, yoko[i][j]+tate[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def main():
    H,W = ints_raw()
    Ss = ["#"+input()[:-1]+"#" for _ in range(H)]
    W = W+2
    H = H+2
    Ss = ["#"*W]+Ss+["#"*W]
    lenHor = [[0]*W for _ in range(H)]
    lenVer = [[0]*W for _ in range(H)]
    for h,S in enumerate(Ss):
        buf = 0
        last_idx = 1
        for idx,c in enumerate(S):
            if c == '#':
                for x in range(last_idx,idx):
                    lenHor[h][x] = buf
                buf =0
                last_idx = idx+1
            else:
                buf+=1
    
    for w in range(W):
        buf = 0
        last_idx = 1
        for idx in range(H):
            c = Ss[idx][w]
            if c == '#':
                for x in range(last_idx, idx):
                    lenVer[x][w] = buf
                buf = 0
                last_idx = idx+1
            else:
                buf += 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, max(lenVer[h][w]-1,0)+max(lenHor[h][w]-1,0)+1)
    return ans

print(main())

Submission status: Accepted

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

Gh=[[0]*W for i in range(H)]
for i in range(H):
    tmp=0
    s=0
    j=0
    while(j!=W):
        if S[i][j]=="#":
            Gh[i][j]==0
            for k in range(s,j):
                Gh[i][k]=tmp
            s=j+1
            j+=1
            tmp=0
        else:
            tmp+=1
            j+=1
    if s!=j:
        for k in range(s,j):
            Gh[i][k]=tmp
Gv=[[0]*W for i in range(H)]
for j in range(W):
    tmp=0
    s=0
    i=0
    while(i!=H):
        if S[i][j]=="#":
            Gv[i][j]==0
            for k in range(s,i):
                Gv[k][j]=tmp
            s=i+1
            i+=1
            tmp=0
        else:
            tmp+=1
            i+=1
    if s!=i:
        for k in range(s,i):
            Gv[k][j]=tmp
ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,Gh[i][j]+Gv[i][j]-1)
print(ans)

Submission status: Accepted

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

ans_C = [[0] * (W+2) for _ in range(H+2)]
ans_R = [[0] * (W+2) for _ in range(H+2)]


for w in range(1,W+1):              
    for h in range(1,H+1):
        if S[h][w] != "#":
            ans_C[h][w] = ans_C[h-1][w] + 1
            ans_R[h][w] = ans_R[h][w-1] + 1
            
for w in range(W,0,-1):
    for h in range(H,0,-1):
        if S[h][w] != "#":
            ans_C[h][w] = max(ans_C[h][w],ans_C[h+1][w])
            ans_R[h][w] = max(ans_R[h][w],ans_R[h][w+1])

ans_max = 0
for w in range(1,W+1):
    for h in range(1,H+1):
        ans_max = max(ans_max, ans_C[h][w]+ans_R[h][w])
        
print(ans_max-1)

Submission status: Accepted

Solution code:
from bisect import bisect
H,W=map(int,input().split())
S=[input() for i in range(H)]
sec_x=[[-1] for i in range(H)]
sec_y=[[-1] for i in range(W)]
for y in range(H):
  for x in range(W):
    if S[y][x]=="#": 
      sec_x[y].append(x)
  sec_x[y].append(W)
for x in range(W):
  for y in range(H):
    if S[y][x]=="#": 
      sec_y[x].append(y)
  sec_y[x].append(H)

ans=0
#print(sec_x)
#print(sec_y)
for y in range(H):
  l=1
  for x in range(W):
    if S[y][x]=="#":
      l+=1
    else:
      b=bisect(sec_y[x],y)
      #print(x,y,l,b,sec_x[y][l]-sec_x[y][l-1]+sec_y[x][b]-sec_y[x][b-1]-3)
      ans=max(ans,sec_x[y][l]-sec_x[y][l-1]+sec_y[x][b]-sec_y[x][b-1]-3)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    return list(map(int, input().split()))

def getlist():
    return list(map(int, input().split()))

h, w = getlist()
hori = [[] for i in range(h)]
valt = [[] for i in range(w)]

for i in range(h):
    inp = input()
    for j, s in enumerate(inp):
        if s == "#":
            hori[i].append(j)
            valt[j].append(i)


def search(hori, w, h):
    board_h = [0 for i in range(h * w)]
    for i, retu in enumerate(hori):
        tmp = -1
        for p in retu:
            wi = p - tmp -1
            for color in range(tmp+1, p):
                board_h[color + w*i] = wi
            tmp = p

        wi = w - tmp - 1
        if retu:
            for color in range(tmp + 1, w):
                board_h[color + w * i] = wi

        else:
            for color in range(w):
                board_h[i * w + color] = w


    return board_h

def search2(hori, w, h):
    board_h = [0 for i in range(h * w)]
    for i, retu in enumerate(hori):
        tmp = -1
        for p in retu:
            wi = p - tmp -1
            for color in range(tmp+1, p):
                board_h[i + color * w] = wi
            tmp = p

        wi = h - tmp - 1
        if retu:
            for color in range(tmp + 1, h):
                board_h[i + color * w] = wi

        else:
            for color in range(h):
                board_h[i + color * w] = h
    return board_h

board_h = search(hori, w, h)
board_v = search2(valt, w, h)
# print(board_h)
# print(board_v)
# print(valt)

ans = 0
for ph, pw in zip(board_h, board_v):
    light = ph + pw - 1
    if ans < light:
        ans = light

print(ans)
"""
4 6
#..#..
......
....#.
#.#...
"""

Submission status: Accepted

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

ST = list(map(''.join, zip(*S)))

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (H+2) for _ in range(W+2)]

final = 0
for y in range(1, H+1):
  Sy = S[y]
  ansXy = ansX[y]
  #ansYy = ansY[y]
  for x in range(1, W+1):
    if Sy[x] == '#':
      continue
    if ansX[y][x] is None:
      t = Sy.find('#', x)
      ansXy[x:t] = [t-x] * (t-x)
    if ansY[x][y] is None:
      t = ST[x].find('#', y)
      ansY[x][y:t] = [t-y] * (t-y)
    a = ansXy[x] + ansY[x][y] - 1
    final = a if a > final else final
print(final)

Submission status: Accepted

Solution code:
def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
    for i in range(h):
        for j in range(1,w):
            t=-1*(j+1)
            if l[i][t]==".":
                x[i][t]=max(x[i][t],x[i][t+1])

    for i in range(w):
        for j in range(h):
            if j==0 and l[j][i]==".":
                y[j][i]=1
            elif l[j][i]==".":
                y[j][i]=y[j-1][i]+1
    for i in range(w):
        for j in range(1,h):
            t=-1*(j+1)
            if l[t][i]==".":
                y[t][i]=max(y[t][i],y[t+1][i])
    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
#print(S)
dpyoko = [[1]*(W) for i in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            dpyoko[i][j] = 0
        else:
            if j != 0:
                dpyoko[i][j] += dpyoko[i][j-1]
dptate = [[1]*(W) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            dptate[i][j] = 0
        else:
            if i != 0:
                dptate[i][j] += dptate[i-1][j]
for j in range(W-1,-1,-1):
    for i in range(H):
        if dpyoko[i][j] == 0:
            continue
        if j == W-1:
            continue
        dpyoko[i][j] = max(dpyoko[i][j],dpyoko[i][j+1])
for i in range(H-1,-1,-1):
    for j in range(W):
        if dptate[i][j] == 0:
            continue
        if i == H-1:
            continue
        dptate[i][j] = max(dptate[i][j],dptate[i+1][j])
dp = [[0]*(W) for i in range(H)]
res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        dp[i][j] = dptate[i][j]+dpyoko[i][j]-1 
        if res < dp[i][j]:
            res = dp[i][j]
print(res)

Submission status: Accepted

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



"""
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 y < H:
        while x < W:
            if grid[y][x] == '#' or res_y[y][x] != 0:
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 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:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

H, W = list(map(int, sys.stdin.readline().split()))

S = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)]) == '.'
ups = np.zeros((H, W), dtype=int)
downs = np.zeros((H, W), dtype=int)
rights = np.zeros((H, W), dtype=int)
lefts = np.zeros((H, W), dtype=int)

for h in range(1, H):
    ups[h] = (ups[h - 1] + 1) * S[h - 1]
for h in reversed(range(H - 1)):
    downs[h] = (downs[h + 1] + 1) * S[h + 1]
for w in range(1, W):
    lefts[:, w] = (lefts[:, w - 1] + 1) * S[:, w - 1]
for w in reversed(range(W - 1)):
    rights[:, w] = (rights[:, w + 1] + 1) * S[:, w + 1]
print(((ups + downs + lefts + rights) * S).max() + 1)

Submission status: Accepted

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

wl = [0]*h*w
hl = [0]*h*w
for j in range(h):
    for i in range(w):
        if s[j][i] == "#":
            continue

        # 横方向
        if i != 0 and wl[w*j+i-1] != 0:
            wl[w*j+i] = wl[w*j+i-1]
        else:
            if "#" in s[j][i:]:
                wl[w*j+i] = s[j][i:].index("#")
            else:
                wl[w*j+i] = w-i

        # 縦方向
        if j != 0 and hl[w*(j-1)+i] != 0:
            hl[w*j+i] = hl[w*(j-1)+i]
        else:
            for y in range(j,h):
                if s[y][i] == "#":
                    break
                hl[w*j+i] = y-j+1
            

res = [x + y for (x, y) in zip(wl, hl)]

print(max(res)-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
ans=[]
for i in range(h):
    s.append(input())
for hi in range(h):
    index=0
    tmpans=[]
    si="#"+s[hi]+"#"
    for wi in range(w+2):
        if si[wi]=="#":
            tmpans+=[wi-index-1]*(wi-index-1)
            index=wi
            tmpans+=[0]
    ans.append(tmpans[1:-1])
for wi in range(w):
    index=0
    tmpans=[]
    si="#"+"".join([s[x][wi] for x in range(h)])+"#"
    for hi in range(h+2):
        if si[hi]=="#":
            tmpans+=[hi-index-1]*(hi-index-1)
            index=hi
            tmpans+=[0]
    for j in range(h):
        tmp=tmpans[j+1]
        ans[j][wi]+=tmp
print(max([max(ans[hi]) for hi in range(h)])-1)

Submission status: Accepted

Solution code:
import sys
 
def solve():
    file = sys.stdin.readline #single: int(file()), line: map(int, file().split())
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    H, W = map(int, file().split())
    S = [None] * H
    for i in range(H):
        S[i] = list(file())
    left, right, up, down = [[0 for i in range(W)] for j in range(H)], [[0 for i in range(W)] for j in range(H)],[[0 for i in range(W)] for j in range(H)],[[0 for i in range(W)] for j in range(H)]
    for h in range(H):
        if S[h][0] == ".": left[h][0] += 1
        if S[h][W-1] == ".": right[h][W-1] += 1
    for w in range(W):
        if S[0][w] == ".": up[0][w] += 1
        if S[H-1][w] == ".": down[H-1][w] += 1

    for h in range(H):
        for w in range(1, W):
            if S[h][w] == ".":
                left[h][w] = left[h][w-1] + 1
            if S[h][W-w-1] == ".":
                right[h][W - w - 1] = right[h][W - w] + 1
    for h in range(1, H):
        for w in range(W):
            if S[h][w] == ".":
                up[h][w] = up[h-1][w] + 1
            if S[H-h-1][w] == ".":
                down[H-h-1][w] = down[H-h][w] + 1

    maxlight = 0
    for h in range(H):
        for w in range(W):
            maxlight = max(maxlight, left[h][w] + right[h][w] + up[h][w] + down[h][w] - 3)
    print(maxlight)   
 
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def solve():
    H, W = map(int, input().split())
    S = [list(input())for _ in range(H)]
    Map = [[0]*W for _ in range(H)]
    Map1 = [[0]*W for _ in range(H)]
    for i in range(H):
        if S[i][0]=='.':
            Map[i][0]=1
        for j in range(1, W):
            if S[i][j]=='.':
                Map[i][j]=Map[i][j-1]+1
        tmp=0
        for j in range(W)[::-1]:
            if Map[i][j]>0:
                if tmp==0:
                    tmp = Map[i][j]
                Map[i][j]=tmp
            else:
                tmp = 0
    for i in range(W):
        if S[0][i]=='.':
            Map1[0][i]=1
        for j in range(1, H):
            if S[j][i]=='.':
                Map1[j][i]=Map1[j-1][i]+1
        tmp = 0
        for j in range(H)[::-1]:
            if Map1[j][i]>0:
                if tmp==0:
                    tmp = Map1[j][i]
                Map1[j][i]=tmp
            else:
                tmp = 0
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, Map[i][j]+Map1[i][j])
    print(ans-1)
        
solve()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
hf=[[0 for i in range(w)]for i in range(h)]
vf=[[0 for i in range(w)]for i in range(h)]
field=[]
for i in range(h):
    field.append(list(input()))
for i in range(h):
    tmp=0
    for j in range(w):
        if field[i][j]=='.':
            tmp+=1
            hf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for j in range(w):
        j=w-j-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=hf[i][j]
            else:
                hf[i][j]=tmp
        else:
            tmp=0
for j in range(w):
    tmp=0
    for i in range(h):
        if field[i][j]=='.':
            tmp+=1
            vf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for i in range(h):
        i=h-i-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=vf[i][j]
            else:
                vf[i][j]=tmp
        else:
            tmp=0
mx=0
for i in range(h):
    for j in range(w):
        if hf[i][j]+vf[i][j]>mx:
            mx=hf[i][j]+vf[i][j]
print(mx-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
L=[[0 for i in range(w)] for i in range(h)]
x=0;ct=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      if ct==0:
        x=j
      ct+=1
    if ct!=0 and (s[i][j]=='#' or j==w-1):
      for k in range(ct):
        L[i][x+k]+=ct
      ct=0

for j in range(w):
  for i in range(h):
    if s[i][j]=='.':
      if ct==0:
        x=i
      ct+=1
    if ct!=0 and (s[i][j]=='#' or i==h-1):
      for k in range(ct):
        L[x+k][j]+=ct
      ct=0
ans=[]
for i in range(len(L)):
  ans.append(max(L[i]))
print(max(ans)-1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


h, w = li()
grid = [lc() for _ in range(h)]


lr = [[0]*w for _ in range(h)]
tb = [[0]*w for _ in range(h)]

for row in range(h):
    for col in range(w):
        if col == 0:
            lr[row][col] = 1 if grid[row][col] == "." else 0

        else:
            if grid[row][col] == "#":
                continue

            else:
                lr[row][col] = lr[row][col-1] + 1

for row in range(h):
    for col in range(w-2, -1, -1):
        if lr[row][col] == 0:
            continue
        else:
            lr[row][col] = max(lr[row][col+1], lr[row][col])

for col in range(w):
    for row in range(h):
        if row == 0:
            tb[row][col] = 1 if grid[row][col] == "." else 0

        else:
            if grid[row][col] == "#":
                continue
            else:
                tb[row][col] = tb[row-1][col] + 1

for col in range(w):
    for row in range(h-2, -1, -1):
        if tb[row][col] == 0:
            continue
        else:
            tb[row][col] = max(tb[row+1][col], tb[row][col])

ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, lr[row][col] + tb[row][col])

print(max(0, ans-1))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l_list=[]
v_list=[]
for i in range(h):
    sub_list=[0]*w
    l_list.append(sub_list)
    sub_list=[0]*w
    v_list.append(sub_list)
s_list=[]
for i in range(h):
    s=input()
    s_list.append(s)
for i in range(h):
    for j in range(w):
        if s_list[i][j]=='#':
            pass
        else:
            l_list[i][j]=l_list[i][j-1]+1
    for j in reversed(range(w)):
        if s_list[i][j]=='#':
            pass
        else:
            if not j==w-1 and not s_list[i][j+1]=='#':
                l_list[i][j]=l_list[i][j+1]
for j in range(w):
    for i in range(h):
        if s_list[i][j]=='#':
            pass
        else:
            v_list[i][j]=v_list[i-1][j]+1
    for i in reversed(range(h)):
        if s_list[i][j]=='#':
            pass
        else:
            if not i==h-1 and not s_list[i+1][j]=='#':
                v_list[i][j]=v_list[i+1][j]
Max=0
for i in range(h):
    for j in range(w):
        if s_list[i][j]=='.':
            Max=max(Max,l_list[i][j]+v_list[i][j]-1)
print(Max)

Submission status: Accepted

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

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


for i in range(H):
    tmp = 0
    for j in range(W):
        if arr[i][j] == ".":
            tmp += 1
            n_arr[i][j] += tmp
        else:
            tmp = 0

for i in range(H):
    tmp = 0
    for j in range(W-1,-1,-1):
        if arr[i][j] == ".":
            tmp += 1
            n_arr[i][j] += tmp - 1
        else:
            tmp = 0


for i in range(W):
    tmp = 0
    for j in range(H):
        if arr[j][i] == ".":
            tmp += 1
            n_arr[j][i] += tmp - 1
        else:
            tmp = 0

ans = 0
for i in range(W):
    tmp = 0
    for j in range(H-1,-1,-1):
        if arr[j][i] == ".":
            tmp += 1
            n_arr[j][i] += tmp - 1
        else:
            tmp = 0
        ans = max(ans, n_arr[j][i])

print(ans)

Submission status: Accepted

Solution code:
H,W=list(map(int,raw_input().strip().split(' ')))
grid=[]
for _ in xrange(H):
    grid+=[raw_input()]

block_h=[]
for i in xrange(H):
    temp=[-1]
    for j in xrange(W):
        if grid[i][j]=="#":
            temp+=[j]
    temp+=[W]
    block_h+=[temp]

block_c=[]
for j in xrange(W):
    temp=[-1]
    for i in xrange(H):
        if grid[i][j]=="#":
            temp+=[i]
    temp+=[H]
    block_c+=[temp]

#print(block_h)
#print(block_c)
import bisect
MAX=0
for i in xrange(H):
    for j in xrange(W):
        #print(i,j)
        ans=0
        if grid[i][j]==".":
            post=bisect.bisect_right(block_c[j],i)
            #print(post)
            a1=block_c[j][post-1]
            a2=block_c[j][post]
            ans+=a2-a1-1

            post=bisect.bisect_right(block_h[i],j)
            #print(post)
            a1=block_h[i][post-1]
            a2=block_h[i][post]
            ans+=a2-a1-1            
            MAX=max(MAX,ans)
print(MAX-1)