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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[S() for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if s[i][j]=='#':
        continue

      _ans=-1
      for a in range(i)[::-1]:
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(i,h):
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(j)[::-1]:
        if s[i][a]=='.':
          _ans+=1
        else:
          break
      for a in range(j,w):
        if s[i][a]=='.':
          _ans+=1
        else:
          break

      ans=max(ans,_ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[list(S()) for _ in range(h)]

  ans=0
  for i in range(h):
    for j in range(w):
      if s[i][j]=='#':
        continue

      _ans=-1
      for a in range(i)[::-1]:
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(i,h):
        if s[a][j]=='.':
          _ans+=1
        else:
          break
      for a in range(j)[::-1]:
        if s[i][a]=='.':
          _ans+=1
        else:
          break
      for a in range(j,w):
        if s[i][a]=='.':
          _ans+=1
        else:
          break

      ans=max(ans,_ans)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split()]

S = []
for _ in range(H):
    S.append(input())

TATE = [[0 for i in range(W + 1)] for j in range(H + 1)]
YOKO = [[0 for i in range(W + 1)] for j in range(H + 1)]


for j in range(1, H + 1):
    for i in range(1, W + 1):
        if S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i - 1] + 1
        if S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j - 1][i] + 1


for j in range(H, 0, -1):
    for i in range(W, 0, -1):
        if i != W and YOKO[j][i + 1] != 0 and S[j - 1][i - 1] == '.':
            YOKO[j][i] = YOKO[j][i + 1]
        if j != H and TATE[j + 1][i] != 0 and S[j - 1][i - 1] == '.':
            TATE[j][i] = TATE[j + 1][i]
ans = 0
for j in range(1, H + 1):
    for i in range(1, W + 1):
        ans = max(ans, TATE[j][i] + YOKO[j][i] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def calculate(arr):
    h = arr.shape[0]
    w = arr.shape[1]

    res = []

    for i in range(h):
        ret = []
        for j in range(w):
            ret.append({'l': 0, 'r': 0, 'u': 0, 'd': 0})
        res.append(ret)

    for i in range(h):
        for j in range(w):

            if arr[i][j] == 1:
                res[i][j]['l'] = 0
                res[i][j]['r'] = 0
                res[i][j]['u'] = 0
                res[i][j]['d'] = 0
            else:
                if j == 0:
                    res[i][j]['l'] = 1
                else:
                    res[i][j]['l'] = res[i][j - 1]['l'] + 1

                if i == 0:
                    res[i][j]['u'] = 1
                else:
                    res[i][j]['u'] = res[i - 1][j]['u'] + 1

    for i in range(h - 1, -1, -1):
        for j in range(w - 1, -1, -1):
            if arr[i][j] == 1:
                res[i][j]['l'] = 0
                res[i][j]['r'] = 0
                res[i][j]['u'] = 0
                res[i][j]['d'] = 0
            else:
                if j == w - 1:
                    res[i][j]['r'] = 1
                else:
                    res[i][j]['r'] = res[i][j+1]['r'] + 1


                if i == h - 1:
                    res[i][j]['d'] = 1
                else:
                    res[i][j]['d'] = res[i + 1][j]['d'] + 1
    max = 0
    for i in range(h):
        for j in range(w):
            val = (res[i][j]['d'] + res[i][j]['u'] + res[i][j]['r'] + res[i][j]['l']) - 3
            if val > max:
                max = val
    return max



S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    s = input()
    ret = []
    for item in s:
        if item == "#":
            ret.append(1)
        else:
            ret.append(0)
    arr.append(ret)

arr2 = np.array(arr)

res = calculate(arr2)

print(res)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
  S.append(list(input()))

dp = [[0] * W for h in range(H)]
dp1 = [[[0, 0] for w in range(W+1)] for h in range(H+1)]
for h in range(H):
  for w in range(W):
    if S[h][w] == '#':
      continue
    
    dp1[h+1][w+1] = [dp1[h][w+1][0]+1, dp1[h+1][w][1]+1]
    dp[h][w] = sum(dp1[h+1][w+1])


ans = 0
dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H-1, -1, -1):
  for w in range(W-1, -1, -1):
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]
    dp[h][w] += sum(dp2[h][w])
    ans = max(ans, dp[h][w]-3)

print(ans)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
  S.append(list(input()))

dp = [[0] * W for h in range(H)]
dp1 = [[[0, 0] for w in range(W+1)] for h in range(H+1)]
for h in range(H):
  for w in range(W):
    if S[h][w] == '#':
      continue
    
    dp1[h+1][w+1] = [dp1[h][w+1][0]+1, dp1[h+1][w][1]+1]
    dp[h][w] = sum(dp1[h+1][w+1])


ans = 0
dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H-1, -1, -1):
  for w in range(W-1, -1, -1):
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]
    dp[h][w] += sum(dp2[h][w])
    ans = max(ans, dp[h][w]-3)

print(ans)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
  S.append(list(input()))

dp = [[0] * W for h in range(H)]
dp1 = [[[0, 0] for w in range(W+1)] for h in range(H+1)]
for h in range(H):
  for w in range(W):
    if S[h][w] == '#':
      continue
    
    dp1[h+1][w+1] = [dp1[h][w+1][0]+1, dp1[h+1][w][1]+1]
    dp[h][w] = sum(dp1[h+1][w+1])


ans = 0
dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H)[::-1]:
  for w in range(W)[::-1]:
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]
    dp[h][w] += sum(dp2[h][w])
    ans = max(ans, dp[h][w]-3)

print(ans)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
  S.append(list(input()))

dp1 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h-1][w-1] == '#':
      continue
    
    dp1[h][w] = [dp1[h-1][w][0]+1, dp1[h][w-1][1]+1]


dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H)[::-1]:
  for w in range(W)[::-1]:
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(sum(dp1[h+1][w+1] + dp2[h][w])-3, ans)

print(ans)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
  S.append(list(input()))

dp1 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h-1][w-1] == '#':
      continue
    
    dp1[h][w] = [dp1[h-1][w][0]+1, dp1[h][w-1][1]+1]


dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H)[::-1]:
  for w in range(W)[::-1]:
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(sum(dp1[h+1][w+1] + dp2[h][w])-3, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

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

Map = []
for i in range(H):
    s = input()
    Map.append(s)

L = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        if Map[i][j]=="#":
           L[i][j] = -1
           cnt = 0
        else:
            L[i][j] = cnt
            cnt += 1

R = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in reversed(range(W)):
        if Map[i][j]=="#":
           R[i][j] = -1
           cnt = 0
        else:
            R[i][j] = cnt
            cnt += 1

U = [[0]*W for _ in range(H)]
for j in range(W):
    cnt = 0
    for i in range(H):
        if Map[i][j]=="#":
           U[i][j] = -1
           cnt = 0
        else:
            U[i][j] = cnt
            cnt += 1

D = [[0]*W for _ in range(H)]
for j in range(W):
    cnt = 0
    for i in reversed(range(H)):
        if Map[i][j]=="#":
           D[i][j] = -1
           cnt = 0
        else:
            D[i][j] = cnt
            cnt += 1

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L,U,R,D=[[[0]*(w+2) for _ in range(h+2)] for _ in range(4)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

import sys
input=sys.stdin.readline

def main():
    h,w=map(int,input().split())
    s=[list('#'*(w+2))]
    for _ in range(h):
        s+=[list('#'+input()+'#')]
    s+=[list('#'*(w+2))]

    G=[]
    for i in range(h+2):
        g=[]
        for j in range(w+2):
            g.append([0,0,0,0])
        G.append(g)
    L,U,R,D=list(range(4))

    for i in range(1,h+1):
        for j in range(1,w+1):
            if s[i][j]=="#":continue
            G[i][j][L]=G[i][j-1][L]+1
            G[i][j][U]=G[i-1][j][U]+1
            
    ans=0

    for i in range(h,0,-1):
        for j in range(w,0,-1):
            if s[i][j]=="#":continue
            G[i][j][R]=G[i][j+1][R]+1
            G[i][j][D]=G[i+1][j][D]+1
            lit=G[i][j][L]+G[i][j][U]+G[i][j][R]+G[i][j][D]-3
            ans=max(ans,lit)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

import sys
input=sys.stdin.readline

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

G=[]
for i in range(h+2):
    g=[]
    for j in range(w+2):
        g.append([0,0,0,0])
    G.append(g)
L,U,R,D=list(range(4))

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        G[i][j][L]=G[i][j-1][L]+1
        G[i][j][U]=G[i-1][j][U]+1
        
ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        G[i][j][R]=G[i][j+1][R]+1
        G[i][j][D]=G[i+1][j][D]+1
        lit=G[i][j][L]+G[i][j][U]+G[i][j][R]+G[i][j][D]-3
        ans=max(ans,lit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

import sys
input=sys.stdin.readline

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

G=[]
for i in range(h+2):
    g=[]
    for j in range(w+2):
        g.append([0,0,0,0])
    G.append(g)
L,U,R,D=list(range(4))

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        G[i][j][L]=G[i][j-1][L]+1
        G[i][j][U]=G[i-1][j][U]+1
        
ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        G[i][j][R]=G[i][j+1][R]+1
        G[i][j][D]=G[i+1][j][D]+1
        lit=sum(G[i][j])-3
        ans=max(ans,lit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

# G=[[[0]*4]*(w+2) for _ in range(h+2)] #[L,U,R,D]
G=[]
for i in range(h+2):
    g=[]
    for j in range(w+2):
        g.append([0,0,0,0])
    G.append(g)
L,U,R,D=list(range(4))

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        G[i][j][L]=G[i][j-1][L]+1
        G[i][j][U]=G[i-1][j][U]+1
        
ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        G[i][j][R]=G[i][j+1][R]+1
        G[i][j][D]=G[i+1][j][D]+1
        lit=sum(G[i][j])-3
        ans=max(ans,lit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

L=[[0]*(w+2) for _ in range(h+2)]
U=[[0]*(w+2) for _ in range(h+2)]
R=[[0]*(w+2) for _ in range(h+2)]
D=[[0]*(w+2) for _ in range(h+2)]


for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

col_cnt = [[0 for _ in range(W)]for _ in range(H)]
for i in range(W):
  tmp_cnt = 0
  prvjj = 0
  for j in range(H):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      col_cnt[j][i] = 0
      for jj in range(prvjj,j):
        col_cnt[jj][i] = tmp_cnt
      prvjj = j+1
      tmp_cnt = 0
  for jj in range(prvjj,H):
    col_cnt[jj][i] = tmp_cnt

row_cnt = [[0 for _ in range(W)]for _ in range(H)]
for j in range(H):
  tmp_cnt = 0
  prvii = 0
  for i in range(W):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      row_cnt[j][i] = 0
      for ii in range(prvii,i):
        row_cnt[j][ii] = tmp_cnt
      prvii = i+1
      tmp_cnt = 0
  for ii in range(prvii,W):
    row_cnt[j][ii] = tmp_cnt

print(max([row_cnt[j][i]+col_cnt[j][i]-1 for i in range(W) for j in range(H)]))

Submission status: Time Limit Exceeded

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

col_cnt = [[0 for _ in range(W)]for _ in range(H)]
for i in range(W):
  tmp_cnt = 0
  prvjj = 0
  for j in range(H):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      col_cnt[j][i] = 0
      for jj in range(prvjj,j):
        col_cnt[jj][i] = tmp_cnt
      prvjj = j+1
      tmp_cnt = 0
  for jj in range(prvjj,H):
    col_cnt[jj][i] = tmp_cnt

row_cnt = [[0 for _ in range(W)]for _ in range(H)]
for j in range(H):
  tmp_cnt = 0
  prvii = 0
  for i in range(W):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      row_cnt[j][i] = 0
      for ii in range(prvii,i):
        row_cnt[j][ii] = tmp_cnt
      prvii = i+1
      tmp_cnt = 0
  for ii in range(prvii,W):
    row_cnt[j][ii] = tmp_cnt

print(max([row_cnt[j][i]+col_cnt[j][i]-1 for i in range(W) for j in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][0] = cnt
for i in range(H):
    for j in range(W-2,-1,-1):
        A[i][j][0] = 0 if A[i][j][0]==0 else max(A[i][j][0],A[i][j+1][0])
for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][1] = cnt
for j in range(W):
    for i in range(H-2,-1,-1):
        A[i][j][1] = 0 if A[i][j][1]==0 else max(A[i][j][1],A[i+1][j][1])
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cur = 0
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            A[i][j-1][0] = cnt
            cur = j+1
            cnt = 0
        else:
            cnt += 1
        A[i][W-1][0] = cnt
for i in range(H):
    for j in range(W-1,-1,-1):
        if A[i][j][0]>0:
            cnt = A[i][j][0]
        elif S[i][j]!="#":
            A[i][j][0] = cnt
        else:
            cnt = 0
for j in range(W):
    cur = 0
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            A[i-1][j][1] = cnt
            cur = i+1
            cnt = 0
        else:
            cnt += 1
    A[H-1][j][1] = cnt
for j in range(W):
    for i in range(H-1,-1,-1):
        if A[i][j][1]>0:
            cnt = A[i][j][1]
        elif S[i][j]!="#":
            A[i][j][1] = cnt
        else:
            cnt = 0
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cur = 0
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            A[i][j-1][0] = cnt
            cur = j+1
            cnt = 0
        else:
            cnt += 1
        A[i][W-1][0] = cnt
for i in range(H):
    for j in range(W-1,-1,-1):
        if A[i][j][0]>0:
            cnt = A[i][j][0]
        else:
            if S[i][j]!="#":
                A[i][j][0] = cnt
            else:
                cnt = 0
for j in range(W):
    cur = 0
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            A[i-1][j][1] = cnt
            cur = i+1
            cnt = 0
        else:
            cnt += 1
    A[H-1][j][1] = cnt
for j in range(W):
    for i in range(H-1,-1,-1):
        if A[i][j][1]>0:
            cnt = A[i][j][1]
        else:
            if S[i][j]!="#":
                A[i][j][1] = cnt
            else:
                cnt = 0
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cur = 0
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            for k in range(cur,j):
                A[i][k][0] = cnt
            cur = j+1
            cnt = 0
        else:
            cnt += 1
    for k in range(cur,W):
        A[i][k][0] = cnt
for j in range(W):
    cur = 0
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            for k in range(cur,i):
                A[k][j][1] = cnt
            cur = i+1
            cnt = 0
        else:
            cnt += 1
    for k in range(cur,H):
        A[k][j][1] = cnt
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(A[i][j]))
print(cmax-1)

Submission status: Time Limit Exceeded

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

enemy_matrix = []
for i in range(H):
  line = input()
  enemy = []
  for k in range(W):
    if line[k] == '#':
      enemy.append(1)
    else:
      enemy.append(0)
  enemy_matrix.append(enemy)
      
L = []
R = []
U = []
D = []

for i in range(H):
  Ls = []
  for k in range(W):
    if enemy_matrix[i][k] == 1:
      Ls.append(0)
    elif k == 0:
      Ls.append(1)
    else:
      Ls.append(Ls[-1] + 1)
      
  L.append(Ls)
  
for i in range(H):
  Rs = []
  for k in range(W-1,-1,-1):
    if enemy_matrix[i][k] == 1:
      Rs.append(0)
    elif k == W-1:
      Rs.append(1)
    else:
      Rs.append(Rs[-1] + 1)
  Rs.reverse()
  R.append(Rs)
  
for i in range(H):
  Us = []
  for k in range(W):
    if enemy_matrix[i][k] == 1:
      Us.append(0)
    elif i == 0:
      Us.append(1)
    else:
      Us.append(U[i-1][k] + 1)
  U.append(Us)
  
for i in range(H-1,-1,-1):
  Ds = []
  for k in range(W):
    if enemy_matrix[i][k] == 1:
      Ds.append(0)
    elif i == H-1:
      Ds.append(1)
    else:
      Ds.append(D[H - i - 2][k] + 1)
  D.append(Ds)
D.reverse()
  
ans = 0

for i in range(H):
  for k in range(W):
    right = L[i][k] + R[i][k] + U[i][k] + D[i][k] - 3
    if ans < right:
      ans = right
      
print(ans)

Submission status: Time Limit Exceeded

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

enemy_list = []
mas_list = []
for i in range(H):
  line = input()
  enemy = [-1]
  for k in range(W):
    if line[k] == '#':
      enemy.append(k)
    else:
      mas_list.append((i, k))
  enemy.append(W)
  enemy_list.append(enemy)

ans = 0
for i in range(len(mas_list)):
  visible = 0
  line_enemies = enemy_list[mas_list[i][0]]
  for k in range(len(line_enemies)):
    if mas_list[i][1] > line_enemies[k] and mas_list[i][1] < line_enemies[k + 1]:
      visible += line_enemies[k+1] - line_enemies[k] - 1
      break
      
  row_enemies = [-1]
  for j in range(len(enemy_list)):
    if mas_list[i][1] in enemy_list[j]:
      row_enemies.append(j)
  row_enemies.append(H)
  
  for l in range(len(row_enemies)):
    if mas_list[i][0] > row_enemies[l] and mas_list[i][0] < row_enemies[l + 1]:
      visible += row_enemies[l+1] - row_enemies[l] - 1
      break
      
  if visible > ans:
    ans = visible
    
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
# これ愚直じゃダメなのかな
# 上下左右それぞれのテーブルを用意し、いまいるところより上/下/左/右にいくつあるかをセーブする（自分は含まない）
# ↑ この4方向累積和方針はあってるっぽいけど愚直に4方向のテーブルを作ってみたいな方針でやったらTLEなった。あとは頼む
# ↑ やりました（4ヶ月ぶり）
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))

toR, toL = (
    [[0 for _ in range(w + 1)] for _ in range(h)],
    [[0 for _ in range(w + 1)] for _ in range(h)],
)
toU, toD = (
    [[0 for _ in range(w)] for _ in range(h + 1)],
    [[0 for _ in range(w)] for _ in range(h + 1)],
)


for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            toR[y][x + 1] += toR[y][x] + 1
            toD[y + 1][x] += toD[y][x] + 1
        else:
            toR[y][x + 1] = 0
            toD[y + 1][x] = 0

        if grid[y][w - x - 1] == ".":
            toL[y][w - x - 1] += toL[y][w - x] + 1
        else:
            toL[y][w - x - 1] = 0

        if grid[h - y - 1][x] == ".":
            toU[h - y - 1][x] += toU[h - y][x] + 1
        else:
            toU[h - y - 1][x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        tmp = toR[y][x + 1] + toL[y][x] + toD[y + 1][x] + toU[y][x] - 3
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    cnt=1
    a=i
    b=j
    if S[a][b]=='.':
      while a+1 < H and S[a+1][b]=='.':
        cnt+=1
        a+=1
      a=i
      while 0 <= a-1 and S[a-1][b]=='.':
        cnt+=1
        a-=1
      a=i
      while b+1 < W and S[a][b+1]=='.':
        cnt+=1
        b+=1
      b=j
      while 0 <= b-1 and S[a][b-1]=='.':
        cnt+=1
        b-=1
      b=j
    ans=max(cnt,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    H, W = LI()
    S = [SI() for _ in range(H)]
    width = [[0]*W for _ in range(H)]
    height = [[0]*W for _ in range(H)]
    for i in range(H):
        cur = 0; keep = []
        for j in range(W):
            if S[i][j]==".":
                cur +=1
                keep.append(j)
            else:
                for k in keep:
                    width[i][k] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                width[i][k] = cur
    for j in range(W):
        cur = 0; keep = []
        for i in range(H):
            if S[i][j]==".":
                cur +=1
                keep.append(i)
            else:
                for k in keep:
                    height[k][j] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                height[k][j] = cur
    ans = 0
    for i in range(H):
        for j in range(W):
            cur = width[i][j] + height[i][j]
            if ans<cur:
                ans = cur
    print(ans-1)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":

    U = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    for col in range(W):
        for row in range(H):
            if grid[row][col] != '#':
                if row == 0:
                    U[row][col] = 1
                else:
                    U[row][col] = U[row-1][col]+1
            if grid[(H-1)-row][col] != '#':
                if (H-1)-row == H-1:
                    D[(H-1)-row][col] = 1
                else:
                    D[(H-1)-row][col] = D[(H-1)-row+1][col]+1
    for row in range(H):
        for col in range(W):
            if grid[row][col] != '#':
                if col == 0:
                    L[row][col] = 1
                else:
                    L[row][col] = L[row][col-1]+1
            if grid[row][(W-1)-col] != '#':
                if (W-1)-col == W-1:
                    R[row][(W-1)-col] = 1
                else:
                    R[row][(W-1)-col] = R[row][(W-1)-col+1]+1
    
    ans = 0
    for row in range(H):
        for col in range(W):
            if grid[row][col] == '#':
                continue
            score = U[row][col]+D[row][col]+L[row][col]+R[row][col]-3
            if ans < score:
                ans = score
    print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":

    U = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    for col in range(W):
        for row in range(0, H, 1):
            if grid[row][col] == '#':
                continue
            if row == 0:
                U[row][col] = 1
            else:
                U[row][col] = U[row-1][col]+1
    for col in range(W):
        for row in range(H-1, -1, -1):
            if grid[row][col] == '#':
                continue
            if row == H-1:
                D[row][col] = 1
            else:
                D[row][col] = D[row+1][col]+1
    for row in range(H):
        for col in range(0, W, 1):
            if grid[row][col] == '#':
                continue
            if col == 0:
                L[row][col] = 1
            else:
                L[row][col] = L[row][col-1]+1
    for row in range(H):
        for col in range(W-1, -1, -1):
            if grid[row][col] == '#':
                continue
            if col == W-1:
                R[row][col] = 1
            else:
                R[row][col] = R[row][col+1]+1
    
    ans = 0
    for row in range(H):
        for col in range(W):
            if grid[row][col] == '#':
                continue
            score = U[row][col]+D[row][col]+L[row][col]+R[row][col]-3
            if ans < score:
                ans = score
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
H, W = map(int, input().split())
S = [input() for _ in range(H)]
S_ = list(map(list, zip(*S)))
H = [sum([[l] * l if s == "." else [0] * l for s, l in map(lambda t: (t[0], len(list(t[1]))), groupby(row))], []) for row in S]
W = [sum([[l] * l if s == "." else [0] * l for s, l in map(lambda t: (t[0], len(list(t[1]))), groupby(row))], []) for row in S_]
W_ = list(map(list, zip(*W)))
print(max(h+w for h,w in zip(sum(H,[]),sum(W_,[])))-1)