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: Time Limit Exceeded

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

h,w=map(int,input().split())
s=[[]*w for i in range(h)]
for i in range(h):
    s[i]=list(input())

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                for jj in range(jst,jed+1):
                    ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            if isum!=0:
                for ii in range(ist,ied+1):
                    hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Time Limit Exceeded

Solution code:

h,w=map(int,input().split())
s=[[]*w for i in range(h)]
for i in range(h):
    s[i]=list(input())

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                for jj in range(jst,jed+1):
                    ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            if isum!=0:
                for ii in range(ist,ied+1):
                    hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Time Limit Exceeded

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

#h,w=4,6
#s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Time Limit Exceeded

Solution code:

h,w=map(int,input().split())
s=[[]*w for i in range(h)]
for i in range(h):
    s[i]=list(input())

#h,w=4,6
#s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
from copy import copy

HS = [[0 for w in range(W)] for h in range(H)]
VS = [[0 for w in range(W)] for h in range(H)]

# 横方向の連続を見る
for lix in range(len(S)):
    con = 0
    l = S[lix]
    for cix in range(len(l)):
        if l[cix] != '#':
            con += 1
        else:
            score = con
            while con > 0:
                # print(cix, con)
                HS[lix][cix-con] = score
                con -= 1
            HS[lix][cix] = 0

    if con > 0:
        score = con 
        while con > 0:
            HS[lix][cix-con+1] = score
            con -= 1
# print(HS)

# 縦方向の連続を見る
for ix in range(W):
    con = 0
    for iy in range(H):
        # print(iy, ix, S[iy][ix])
        if S[iy][ix] == '#':
            # print(iy, ix, con)
            # refresh
            score = con
            while con > 0:
                VS[iy-con][ix] = score
                con -= 1
            VS[iy][ix] = 0
        else:
            con += 1
    # last
    while con > 0:
        score = con
        while con > 0:
            VS[iy-con+1][ix] = score
            con -= 1

# print(VS)

# 最大値を求める
ans = 0
for iy in range(H):
    for ix in range(W):
        ans = max(HS[iy][ix] + VS[iy][ix] - 1, ans)

print(ans)


# 3 * H * Wでいけるのでは?

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
left=[[0]*w for _ in range(h)]
right=[[0]*w for _ in range(h)]
up=[[0]*w for _ in range(h)]
down=[[0]*w for _ in range(h)]
for i in range(h):
    temp=1
    for j in range(w):
        if s[i][j]==".":
            left[i][j]+=temp
            temp+=1
        else:
            temp=1
for i in range(h):
    temp=1
    for j in range(w)[::-1]:
        if s[i][j]==".":
            right[i][j]+=temp
            temp+=1
        else:
            temp=1
for i in range(w):
    temp=1
    for j in range(h):
        if s[j][i]==".":
            down[j][i]+=temp
            temp+=1
        else:
            temp=1
for i in range(w):
    temp=1
    for j in range(h)[::-1]:
        if s[j][i]==".":
            up[j][i]+=temp
            temp+=1
        else:
            temp=1
ans=1
for i in range(h):
    for j in range(w):
        ans=max(ans,up[i][j]+down[i][j]+left[i][j]+right[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
s=["#"*(w+2)]
for i in range(h):
    s.append("#"+input()+"#")
s.append("#"*(w+2))
ans=[[0]*(w+2) for i in range(h+2)]

for i in range(h+2):
    ran=[]
    c=1
    for j in range(1,w+2):
        if s[i][j]==s[i][j-1]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[i][p]+=ran[j]
            p+=1

for i in range(w+2):
    ran=[]
    c=1
    for j in range(1,h+2):
        if s[j][i]==s[j-1][i]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[p][i]+=ran[j]
            p+=1
print(max(sum(ans,[]))-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
yoko = [[0] * W for _ in range(H)]
tate = [[0] * W for _ in range(H)]

for h in range(H):
    d = []
    for w in range(W):
        if S[h][w] == ".":
            d.append([h, w])
            if W != w+1: continue
        for h, w in d:
            yoko[h][w] = len(d)
        d = []

for w in range(W):
    d = []
    for h in range(H):
        if S[h][w] == ".":
            d.append([h, w])
            if H != h+1: continue
        for h, w in d:
            tate[h][w] = len(d)
        d = []
        
ans = 0
for h in range(H):
    for w in range(W):
        if ans < yoko[h][w]+tate[h][w]-1:
            ans = yoko[h][w]+tate[h][w]-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="#" else 0)
  m.append(mm)

wl=[[0 for i in range(w)]for j in range(h)]
for i in range(h):
  s=0
  t=0
  while t<w:
    while t<w and m[i][t]==0:
      t+=1
    for j in range(s,t):
      wl[i][j]=t-s
    s=t+1
    t=t+1
mx=0
for i in range(w):
  s=0
  t=0
  while t<h:
    while t<h and m[t][i]==0:
      t+=1
    for j in range(s,t):
      k=wl[j][i]
      if mx<k+t-s:
        mx=k+t-s
    s=t+1
    t=t+1


print(mx-1)

Submission status: Time Limit Exceeded

Solution code:
h , w = map(int,input().split())
s = [input() for i in range(h)]
coulef = [[0 for i in range(w)] for j in range(h)]
courig = [[0 for i in range(w)] for j in range(h)]
coudow = [[0 for i in range(w)] for j in range(h)]
couup = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    cou = 0
    for j in range(w):
        if s[i][j] == ".":
            cou += 1
            courig[i][j] = cou
        elif s[i][j] == "#":
            cou = 0
for i in range(h):
    cou = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            cou += 1
            coulef[i][j] = cou
        elif s[i][j] == "#":
            cou = 0
for i in range(w):
    cou = 0
    for j in range(h):
        if s[j][i] == ".":
            cou += 1
            coudow[j][i] = cou
        elif s[j][i] == "#":
            cou = 0
for i in range(w):
    cou = 0
    for j in reversed(range(h)):
        if s[j][i] == ".":
            cou += 1
            couup[j][i] = cou
        elif s[j][i] == "#":
            cou = 0

ans = 0
for i in range(h):
    for j in range(w):
        now = couup[i][j]+coudow[i][j]+coulef[i][j]+courig[i][j]
        ans = max(ans,now-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        ans = 1
        dist = [[-1]*W for _ in range(H)]
        dist[h][w] = 0
        for dir in range(4):
            que = deque([])
            que.append([h,w])
            while que != deque([]):
                u,v = que.popleft()
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W) or (field[nu][nv] == "#") or (dist[nu][nv] != -1):
                    ans += dist[u][v]
                    continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
        if ans > mx:
            mx = ans
    
print(mx)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        ans = 1
        for dir in range(4):
            dist = [[-1]*W for _ in range(H)]
            dist[h][w] = 0
            que = deque([])
            que.append([h,w])
            while que != deque([]):
                u,v = que.popleft()
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W):
                    continue
                if field[nu][nv] == "#":
                    continue
                if dist[nu][nv] != -1:
                    continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
                ans += 1
        if ans > mx:
            mx = ans
    
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
grid = [0] * H
for i in range(H):
    grid[i] = input()
right = [[0]*W for _ in range(H)]
left = [[0]*W for _ in range(H)]
up = [[0]*W for _ in range(H)]
down = [[0]*W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if grid[y][x] == '.':
            r = 0
            while True:
                if x+r+1 == W or grid[y][x+r+1] == '#':
                    break
                r += 1
            right[y][x] = r
            l = 0
            while True:
                if x-l-1 == -1 or grid[y][x-l-1] == '#':
                    break
                l += 1
            left[y][x] = l
            u = 0
            while True:
                if y-u-1 == -1 or grid[y-u-1][x] == '#':
                    break
                u += 1
            up[y][x] = u
            d = 0
            while True:
                if y+d+1 == H or grid[y+d+1][x] == '#':
                    break
                d += 1
            down[y][x] = d
ans = 0
for y in range(H):
    for x in range(W):
        if grid[y][x] == '.':
            can = 1 + right[y][x] + left[y][x] + up[y][x] + down[y][x]
            ans = max(ans,can)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
    D = list(input())
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h = [ [0] * W  for h in range(H) ]

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_h[d_h][o] = o_ed-1 - o_st
    
Lamp_w =  [ [0] * H  for w in range(W) ]
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_w[d_w][o] = o_ed-1 - o_st
    
ans = 0
for h in range(H):
    for w in range(W):
        ans_ = Lamp_h[h][w] + Lamp_w[w][h] 
        if ans < ans_:
            ans =ans_
        
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

# H,W = [3,4]
H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
    D = list(input())
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h =  np.zeros((H,W))

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_h[d_h][o_st+1:o_ed] = o_ed-1 - o_st
    
Lamp_w =  np.zeros((W,H))
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_w[d_w][o_st+1:o_ed] = o_ed-1 - o_st
        
Lamp = Lamp_w.T + Lamp_h

print(int(Lamp.max()-1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = list(map(int,input().split()))

D=[]
for h in range(H):
    D.append(list(input()))
    
D = np.array(D) # D[h][w]
Lamp_h =  np.zeros(D.shape)

for d_h,d in enumerate(D):
    obst =[-1]
    
    for d_idx in range(len(d)):
        if d[d_idx] == '#':
            obst.append(d_idx)
            
    obst.append(W)
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_h[d_h][o_st+1:o_ed] = o_ed-1 - o_st

D_ = D.T # D[h][w]
Lamp_w =  np.zeros(D_.shape)

for d_h,d in enumerate(D_):
    obst =[-1]
    
    for d_idx in range(len(d)):
        if d[d_idx] == '#':
            obst.append(d_idx)
            
    obst.append(H)
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_w[d_h][o_st+1:o_ed] = o_ed-1 - o_st
        
Lamp_w.T

Lamp = Lamp_w.T + Lamp_h

print(int(Lamp.max()-1))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "#" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["#", input().rstrip(), "#"])

    U = [[-1] * (W + 2) for _ in range(H + 2)]
    D = [[-1] * (W + 2) for _ in range(H + 2)]
    L = [[-1] * (W + 2) for _ in range(H + 2)]
    R = [[-1] * (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
            if U[h][w] == -1:
                U[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if S[h + d][w] == "#":
                        break
                    U[h + d][w] = d
            if L[h][w] == -1:
                L[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if S[h][w + d] == "#":
                        break
                    L[h][w + d] = d

    for h in reversed(range(1, H + 1)):
        for w in reversed(range(1, W + 1)):
            if S[h][w] == "#":
                continue
            if D[h][w] == -1:
                D[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if S[h - d][w] == "#":
                        break
                    D[h - d][w] = d
            if R[h][w] == -1:
                R[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if S[h][w - d] == "#":
                        break
                    R[h][w - d] = d

    ans = 0
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dist = U[h][w] + D[h][w] + L[h][w] + R[h][w] + 1
            if ans < dist:
                ans = dist

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
import heapq
w=[[0 for i in range(W)]for j in range(H)]
for i in range(H):
  S=input()
  for j in range(W):
    w[i][j]=S[j]
    
L=[[0 for i in range(W)] for j in range(H)]
R=[[0 for i in range(W)] for j in range(H)]
U=[[0 for i in range(W)] for j in range(H)]
D=[[0 for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      L[i][j]=0
    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(W-1,-1,-1):
    if w[i][j]=='#':
      R[i][j]=0
    elif j==W-1:
      R[i][j]=1
    else:
      R[i][j]=R[i][j+1]+1
for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      D[i][j]=0
    elif i==0:
      D[i][j]=1
    else:
      D[i][j]=D[i-1][j]+1  
for i in range(H-1,-1,-1):
  for j in range(W):
    if w[i][j]=='#':
      U[i][j]=0
    elif i==H-1:
      U[i][j]=1
    else:
      U[i][j]=U[i+1][j]+1
m=0

for i in range(H):
  for j in range(W):
    x=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    m=max(x,m)
print(m)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
w=[[]for i in range(H)]
for i in range(H):
  S=input()
  for j in range(W):
    w[i].append(S[j])
    
L=[[0 for i in range(W)] for j in range(H)]
R=[[0 for i in range(W)] for j in range(H)]
U=[[0 for i in range(W)] for j in range(H)]
D=[[0 for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      L[i][j]=0
    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(W-1,-1,-1):
    if w[i][j]=='#':
      R[i][j]=0
    elif j==W-1:
      R[i][j]=1
    else:
      R[i][j]=R[i][j+1]+1
for i in range(H):
  for j in range(W):
    if w[i][j]=='#':
      D[i][j]=0
    elif i==0:
      D[i][j]=1
    else:
      D[i][j]=D[i-1][j]+1  
for i in range(H-1,-1,-1):
  for j in range(W):
    if w[i][j]=='#':
      U[i][j]=0
    elif i==H-1:
      U[i][j]=1
    else:
      U[i][j]=U[i+1][j]+1
ans=[]
for i in range(H):
  for j in range(W):
    x=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    ans.append(x)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = lamp(s)
    yoko = lamp(trans(s))
    ans=0
    for hh in range(h):
        for ww in range(w):
            ans=max(ans,tate[hh][ww]+yoko[ww][hh]-1)
    print(ans)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = list(chain.from_iterable(lamp(s)))
    yoko = list(chain.from_iterable(trans(lamp(trans(s)))))
    ans=0
    for a,b in zip(tate,yoko):
        ans=max(ans,a+b-1)
    print(ans)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()


def lamp(arr):
    count = np.zeros_like(arr,dtype = int)
    for i in range(arr.shape[0]):
        lamp = []
        for key, value in groupby(arr[i]):
            n=int(len(list(value)))
            if key == '.':
                lamp+=[n]*n
            else:
                lamp+=[0]*n
        count[i]=np.array(lamp)
    return count



def main():
    h, w = map(int, input().split())
    s = np.array([list(input()) for i in range(h)])
    print(np.max(lamp(s)+lamp(s.T).T)-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = list(map(int, input().split()))

s = [list(input()) for _ in range(h)]

yoko = [[0] * w for _ in range(h)]
#tate = [[0] * w for _ in range(h)]

q = deque([])
c = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1
        
        if s[i][j] == "#" or j == w-1:
            while len(q) > 0:
                x, y = q.pop()
                yoko[x][y] = c
            c = 0



m = 0

#print(yoko)

c = 0
for j in range(w):
    for i in range(h):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1

        if s[i][j] == "#" or i == h-1:
            while len(q) > 0:
                x, y = q.pop()
                m = max(m, yoko[x][y] + c - 1)
            c = 0


print(m)

Submission status: Time Limit Exceeded

Solution code:

def make_mat(grid):
    H = len(grid)
    W = len(grid[0])
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if grid[h][w] == "#":
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if grid[h][w] == ".":
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append(list(input().rstrip()))

A = make_mat(grid)
grid_t = list(zip(*grid))
B = list(zip(*make_mat(grid_t)))
res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[h][w], res)

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.':continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0:continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.':
            continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0:
            continue

        if xs[i][j+1]>0:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]>0:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        ans=max(ans,x+y-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

xs=[[0]*(W) for _ in range(H)]
ys=[[0]*(W) for _ in range(H)]

for i,ln in enumerate(sys.stdin):
    for j,c in enumerate(ln):
        if c!='.':
            continue
        if j==0:
            xs[i][j]=1
        else:
            xs[i][j]+=1+xs[i][j-1]
        if i==0:
            ys[i][j]=1
        else:
            ys[i][j]+=1+ys[i-1][j]
        


#from pprint import pprint
#pprint(xs,width=60)
#print()
#pprint(ys,width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue

        if j+1<W and xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if i+1<H and ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

H,W=map(int,next(sys.stdin).split())
xs=[[0+(c!='#') for c in ln] for ln in map(str.strip,sys.stdin)]

#xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W) for _ in range(H)]


for i in range(H):
    for j in range(W):
        if xs[i][j]!=0:
            if j>0:
                xs[i][j]+=xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

#from pprint import pprint
#pprint(xs,width=60)
#print()
#pprint(ys,width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue

        if j+1<W and xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if i+1<H and ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)