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:
H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = []
    i = 0
    while True:
        if i == W:
            break
        if S[y][i] == ".":
            n = 0
            while i < W and S[y][i] == '.':
                i += 1
                n += 1
            Hor[y] += [n] * n
        else:
            Hor[y] += [0]
            i += 1
    y += 1

Ver = [0]*W
x = 0
while x != W:
    Ver[x] = []
    i = 0
    while True:
        if i == H:
            break
        if S[i][x] == ".":
            n = 0
            while i < H and S[i][x] == '.':
                i += 1
                n += 1
            Ver[x] += [n] * n
        else:
            Ver[x] += [0]
            i += 1
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=''
for i in range(h):
  s+=input()
n=len(s)
def check(k):
  num=1
  K=k
  while K+w<n:
    if s[K+w]=='.':
      num+=1
      K=K+w
    else:
      break
  K=k
  while K-w>=0:
    if s[K-w]=='.':
      num+=1
      K=K-w
    else:
      break
  K=k
  while K%w!=0:
    if s[K-1]=='.':
      num+=1
      K=K-1
    else:
      break
  K=k
  while K%w!=w-1:
    if s[K+1]=='.':
      num+=1
      K=K+1
    else:
      break
  return num
ans=0
for j in range(n):
  if s[j]=='.':
    ans=max(ans,check(j))
print(ans)

Submission status: Time Limit Exceeded

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

yoko = []
for h in range(H):
  yoko.extend(S[h].split("#"))

ans = 0
for hw in zip(*S):
  hw = "".join(hw)
  t = len(max(hw.split("#")))
  ans = max(len(max(yoko))+t-1, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
m = [[0] * W for _ in range(H)]
for h in range(H):
    i = None
    for j in range(W + 1):
        if j < W and S[h][j] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[h][k] += j - i
                i = None
for w in range(W):
    i = None
    for j in range(H + 1):
        if j < H and S[j][w] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[k][w] += j - i
                i = None
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        ans = max(ans, m[h][w] - 1)
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[]
for i in range(H):
    grid.append(list(input()))

L=list2d(H, W, 0)
R=list2d(H, W, 0)
D=list2d(H, W, 0)
U=list2d(H, W, 0)

for i in range(H):
    cnt=0
    for j in range(W):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        L[i][j]=cnt
for i in range(H):
    cnt=0
    for j in range(W-1, -1, -1):
        if grid[i][j]=='#':
            cnt=0
        else:
            cnt+=1
        R[i][j]=cnt
for i in range(W):
    cnt=0
    for j in range(H):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        D[j][i]=cnt
for i in range(W):
    cnt=0
    for j in range(H-1, -1, -1):
        if grid[j][i]=='#':
            cnt=0
        else:
            cnt+=1
        U[j][i]=cnt

ans=0
for i in range(H):
    for j in range(W):
        if grid[i][j]!='#':
            ans=max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

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

L = [[0 for x in range(W)] for y in range(H)]
R = [[0 for x in range(W)] for y in range(H)]
U = [[0 for x in range(W)] for y in range(H)]
D = [[0 for x in range(W)] for y in range(H)]

for i in range(H) :
    for j in range(1,W) :
        if (A[i][j] == "#") or (A[i][j-1] == "#") :
            L[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
    
    for j in range(W-2,-1,-1) :
        if (A[i][j] == "#") or (A[i][j+1] == "#") :
            R[i][j] = 0
        else :
            R[i][j] = R[i][j+1] + 1

for j in range(W) :
    for i in range(1,H) :
        if (A[i][j] == "#") or (A[i-1][j] == "#") :
            U[i][j] = 0
        else :
            U[i][j] = U[i-1][j] + 1

    for i in range(H-2,-1,-1) :
        if (A[i][j] == "#") or (A[i+1][j] == "#") :
            D[i][j] = 0
        else :
            D[i][j] = D[i+1][j] + 1

ans = 0

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

ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)
    
L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh=Lh+[a]
    L.append(Lh)

R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh=[a]+Rh
    R.append(Rh)

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw=Uw+[a]
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]
    
D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw=[a]+Dw
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    s1=[]
    for j in range(len(s)):
        if s[j]=='.':
            s1+=[1]
        else:
            s1+=[0]
    S+=[s1]
S=np.array(S)
T1=[]
for i in range(S.shape[0]):
    s=S[i]
    t2=s[0]
    if t2==1:
        t1=1
    else:
        t1=0
    t=[]
    k=0
    for j in range(1,len(s)):
        if s[j]==t2:
            if t2==1:
                t1+=1
        else:
            t2=s[j]
            t+=[t1]*(j-k)
            k=j
            if t2==1:
                t1=1
            else:
                t1=0
    else:
        t+=[t1]*(len(s)-k)
    T1+=[t]
T1=np.array(T1)


T2=[]
for i in range(S.T.shape[0]):
    s=S.T[i]
    t2=s[0]
    if t2==1:
        t1=1
    else:
        t1=0
    t=[]
    k=0
    for j in range(1,len(s)):
        if s[j]==t2:
            if t2==1:
                t1+=1
        else:
            t2=s[j]
            t+=[t1]*(j-k)
            k=j
            if t2==1:
                t1=1
            else:
                t1=0
    else:
        t+=[t1]*(len(s)-k)
    T2+=[t]
T2=np.array(T2).T
print(np.max(T1+T2)-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = [input() for _ in range(h)]
yoko = []
tate = []
for i in range(h):
    l = []
    k = s[i][0]
    m = 1
    for j in range(1,w):
        if s[i][j]!=k:
            if k=='.':
                l += [m]*m
            else:
                l += [0]*m
            m = 1
            k = s[i][j]
        else:
            m += 1
    if k=='.':
        l += [m]*m
    else:
        l += [0]*m
    yoko.append(l)

for i in range(w):
    l = []
    k = s[0][i]
    m = 1
    for j in range(1,h):
        if s[j][i]!=k:
            if k=='.':
                l += [m]*m
            else:
                l += [0]*m
            m = 1
            k = s[j][i]
        else:
            m += 1
    if k=='.':
        l += [m]*m
    else:
        l += [0]*m
    tate.append(l)
ans = 0
for i in range(h):
    for j in range(w):
        if yoko[i][j] and tate[j][i]:
            ans = max(ans,yoko[i][j]+tate[j][i]-1)
print(ans)

Submission status: Time Limit Exceeded

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

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = ""
for i in range(H):
    S += input()

vert = [0] * (H*W)
horz = [0] * (H*W)

for i in range(H*W):
    if S[i] == '.':
        if i - W >= 0:
            if S[i - W] == '.':
                vert[i] = vert[i - W]
                continue
        j = i
        L = 0
        while S[j] == '.':
            L += 1
            j += W
            if j >= H * W:
                break
        vert[i] = L

for i in range(H*W):
    if S[i] == '.':
        if i % W > 0:
            if S[i - 1] == '.':
                horz[i] = horz[i - 1]
                continue
        j = i
        L = 0
        while S[j] == '.':
            L += 1
            j += 1
            if j % W == 0:
                break
        horz[i] = L

light = [0] * (H*W)
for i in range(H * W):
    light[i] = horz[i] + vert[i]
print(max(light) - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)

L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh.append(a)
    L.append(Lh)
    
R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh.append(a)
    Rh.reverse()
    R.append(Rh)

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw.append(a)
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]

D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw.append(a)
    Dw.reverse()
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]
    
maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_d

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

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

    h_path = [[] for _ in range(H)]
    for h in range(H):
        c = 0
        for w in range(W):
            if grid[h][w] == '#':
                if c > 0:
                    h_path[h].append(c)
                    c = 0
                h_path[h].append(0)
            else:
                c += 1
        if c > 0:
            h_path[h].append(c)
    # print(h_path)

    h_query = [[0] * W for _ in range(H)]
    for h in range(H):
        path = h_path[h]
        index = 0
        for p in path:
            l = p if p > 0 else 1
            while l > 0:
                h_query[h][index] = p
                l -= 1
                index += 1

    # print(h_query)

    w_path = [[] for _ in range(W)]
    for w in range(W):
        c = 0
        for h in range(H):
            if grid[h][w] == '#':
                if c > 0:
                    w_path[w].append(c)
                    c = 0
                w_path[w].append(0)
            else:
                c += 1
        if c > 0:
            w_path[w].append(c)
    # print(w_path)

    w_query = [[0] * W for _ in range(H)]
    for w in range(W):
        path = w_path[w]
        index = 0
        for p in path:
            l = p if p > 0 else 1
            while l > 0:
                w_query[index][w] = p
                l -= 1
                index += 1

    # print(h_query)
    # print(w_query)
    def count(i, j):
        h_val = h_query[i][j]
        w_val = w_query[i][j]
        val = h_val + w_val
        if h_val > 0 and w_val > 0:
            val -= 1
        return val

    ans = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] != '#':
                # print('h = {}, w = {}, count = {}'.format(h, w, count(h, w)))
                ans = max(ans, count(h, w))
                pass
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def tranpose(arr):
    return [list(i) for i in zip(*arr)]


def set_values(marr, harr):
    for i in range(len(harr)):
        value = 0
        for j in range(len(harr[i])):
            if marr[i][j]:
                value += 1
                harr[i][j] = value
            else:
                value = 0

    for i in range(len(harr)):
        for j in range(len(harr[i]) - 2, -1, -1):
            if marr[i][j]:
                harr[i][j] = max(harr[i][j], harr[i][j+1])


def solve():
    h, w = [int(x) for x in input().split()]
    marr = []
    harr = []
    varr = []

    for i in range(h):
        line = str(input())
        marr.append([True] * w)
        harr.append([0] * w)
        varr.append([0] * w)

        for j in range(w):
            if line[j] == '#':
                marr[i][j] = False

    set_values(marr, harr)

    t_marr = tranpose(marr)
    t_varr = tranpose(varr)
    set_values(t_marr, t_varr)
    varr = tranpose(t_varr)

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, harr[i][j] + varr[i][j])

    print(ans - 1)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int, input().split())

s = [input() for i in range(h)]
l = [[0 for j in range(w)] for i in range(h)]
r = [[0 for j in range(w)] for i in range(h)]
u = [[0 for j in range(w)] for i in range(h)]
d = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        l[i][j] = 0 if s[i][j] == '#' else 1 + (0 if j == 0 else l[i][j - 1])
    for j in range(w - 1, -1, -1):
        r[i][j] = 0 if s[i][j] == '#' else 1 + (0 if j == w - 1 else r[i][j + 1])

for j in range(w):
    for i in range(h):
        u[i][j] = 0 if s[i][j] == '#' else 1 + (0 if i == 0 else u[i - 1][j])
    for i in range(h - 1, -1, -1):
        d[i][j] = 0 if s[i][j] == '#' else 1 + (0 if i == h - 1 else d[i + 1][j])

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] - 3)
print(ans)

Submission status: Time Limit Exceeded

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
            if i==0 and l[i][j]==".":
                y[i][j]=1
            elif l[i][j]==".":
                y[i][j]=y[i-1][j]+1
    for i in range(h):
        for j in range(w):
            a=-1*(i+1)
            b=-1*(j+1)
            if i==j==0: continue
            if l[a][b]=="#": continue
            x[a][b]=max(x[a][b],x[a][b+1])
            if i>0: y[a][b]=max(y[a][b],y[a+1][b])

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

Solution code:
h, w = map(int, input().split())
 
m = list()
mv = list()
mh = list()
 
for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)
 
for i in range(h):
    m.append(input())
 
for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "#":
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c
 
for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "#":
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c
 
res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)

Submission status: Time Limit Exceeded

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

yoko = [[0] * W for _ in range(H)]
tate = [[0] * H for _ in range(W)]


for i in range(H):
    S = s_list[i]
    for j in range(W):
        s = S[j]
        if s == "#":
            continue
        else:
            yoko[i][j] += 1
    for j in range(W):
        if yoko[i][j] == 1 and j > 0:
            yoko[i][j] += yoko[i][j - 1]
    for j in range(W - 1, -1, -1):
        if yoko[i][j] != 0 and j - 1 >= 0 and yoko[i][j - 1] != 0:
            yoko[i][j - 1] = yoko[i][j]
for j in range(W):
    for i in range(H):
        s = s_list[i][j]
        if s == "#":
            continue
        else:
            tate[j][i] += 1
    for i in range(H):
        if tate[j][i] == 1 and i > 0:
            tate[j][i] += tate[j][i - 1]
    for i in range(H - 1, -1, -1):
        if tate[j][i] != 0 and i - 1 >= 0 and tate[j][i - 1] != 0:
            tate[j][i - 1] = tate[j][i]

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = ""
for i in range(H):
    S += input()

vert = [0] * (H*W)
horz = [0] * (H*W)

for i in range(H*W):
    if S[i] == '.':
        if i - W >= 0:
            if S[i - W] == '.':
                vert[i] = vert[i - W]
                continue
        j = i
        L = 0
        while True:
            if j >= H * W:
                vert[i] = L
                break
            if S[j] == '.':
                L += 1
            else:
                vert[i] = L
                break
            j += W

for i in range(H*W):
    if S[i] == '.':
        if i % W > 0:
            if S[i - 1] == '.':
                horz[i] = horz[i - 1]
                continue
        j = i
        L = 0
        while True:
            if S[j] == '.':
                L += 1
            else:
                horz[i] = L
                break
            j += 1
            if j % W == 0:
                horz[i] = L
                break

light = [0] * (H*W)
for i in range(H * W):
    light[i] = horz[i] + vert[i]
print(max(light) - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
MAP = [list('#' for i in range(W + 2)) for j in range(H + 2)]
for i in range(H):
    line = list(input())
    for j, dot in enumerate(line):
        MAP[i + 1][j + 1] = dot
L = [[0 for j in range(W + 2)] for i in range(H + 2)]


def line(MAP):
    for i in range(1, H + 2):
        before = 0
        for j in range(1, W + 2):
            if MAP[i][j] == '#':
                for x in range(before + 1, j):
                    L[i][x] = j - before - 1
                before = j


def column(MAP2):
    for j in range(1, W + 2):
        before = 0
        for i in range(1, H + 2):
            if MAP2[i][j] == '#':
                for y in range(before + 1, i):
                    global ans
                    ans = max(ans, i - before - 1 + L[y][j])
                before = i


line(MAP)
ans = 0
column(MAP)
print(ans - 1)

Submission status: Time Limit Exceeded

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

L_cnt = [[0]*(W+2) for i in range(H+2)]
R_cnt = [[0]*(W+2) for i in range(H+2)]
U_cnt = [[0]*(W+2) for i in range(H+2)]
D_cnt = [[0]*(W+2) for i in range(H+2)]

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

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

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

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

ans = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        ans = max(ans,L_cnt[h][w]+R_cnt[h][w]+U_cnt[h][w]+D_cnt[h][w])

print(ans-3)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import bisect


def solve(H: int, W: int, S: "List[str]"):
    L = [[0 for _ in range(W)] for _ in range (H)]
    R = [[0 for _ in range(W)] for _ in range (H)]
    D = [[0 for _ in range(W)] for _ in range (H)]
    U = [[0 for _ in range(W)] for _ in range (H)]

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

        for j in range(W-1,-1,-1):
            if S[i][j] == "#":
                R[i][j] = 0
            elif j < W-1:
                R[i][j] = R[i][j+1] + 1
            else:
                R[i][j] = 1

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

        for i in range(H-1,-1,-1):
            if S[i][j] == "#":
                D[i][j] = 0
            elif i < H-1:
                D[i][j] = D[i+1][j] + 1
            else:
                D[i][j] = 1

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

    print(res)





# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
for y in range(H):
    Hor[y] = aaa(S[y])

Ver = [0]*W
for x in range(W):
    Ver[x] = aaa([S[_][x] for _ in range(H)])

ans = 1
for x,y in itertools.product(range(W),range(H)):
    h = Hor[y][x]
    v = Ver[x][y]
    ans = max(ans,h+v-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = ""
for i in range(H):
    S += input()

vert = [0] * (H*W)
horz = [0] * (H*W)

for i in range(H*W):
    if S[i] == '.':
        if i - W >= 0:
            if S[i - W] == '.':
                vert[i] = vert[i - W]
                continue
        j = i
        while True:
            if j >= H * W:
                break
            if S[j] == '.':
                vert[i] += 1
            else:
                break
            j += W

for i in range(H*W):
    if S[i] == '.':
        if i % W > 0:
            if S[i - 1] == '.':
                horz[i] = horz[i - 1]
                continue
        j = i
        while True:
            if S[j] == '.':
                horz[i] += 1
            else:
                break
            j += 1
            if j % W == 0:
                break

light = [0] * (H*W)
for i in range(H * W):
    light[i] = horz[i] + vert[i]
print(max(light) - 1)

Submission status: Time Limit Exceeded

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

s = [input() for i in range(h)]

board = [[[0 for _ in range(2)] for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board[i][j][0] = cnt_continue
    for j in reversed(range(w-1)):
        if board[i][j][0] == 0:
            continue
        board[i][j][0] = max(board[i][j][0], board[i][j+1][0])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board[j][i][1] = cnt_continue

    for j in reversed(range(h-1)):
        if board[j][i][1] == 0:
            continue
        board[j][i][1] = max(board[j][i][1], board[j+1][i][1])


ans = 0

for i in range(h):
    for j in range(w):
        v = sum(board[i][j]) - 1
        ans = max(ans, v)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)
def dmatprint(mat):

    if debug == True:
        for row in mat:
            for col in row:
                print("{0:2d} ".format(col), end="")
            print("")
        print("")

def solve():
    H, W = map(int, input().split())
    s_arr = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        s_row = input()
        for w in range(W):
            if s_row[w] == ".":
                s_arr[h][w] = 0
            else:
                s_arr[h][w] = 1

    h_count = [[-1 for w in range(W)] for h in range(H)]
    w_count = [[-1 for w in range(W)] for h in range(H)]

    # w_countを埋める
    for h in range(H):
        row = s_arr[h]
        clearFlag = True
        for w, s in enumerate(row):
            if clearFlag:
                start = w
                end = w
            if s == 0:
                end = w
                clearFlag = False
            else:
                if clearFlag:
                    h_count[h][w] = -1
                else:
                    for iw in range(start, end+1):
                        w_count[h][iw] = end - start + 1
                clearFlag = True
        if clearFlag == False:
            for iw in range(start, max(end + 1, W)):
                w_count[h][iw] = end - start + 1

    # h_countを埋める
    for w in range(W):
        col = [row[w] for row in s_arr]
        clearFlag = True
        for h, s in enumerate(col):
            if clearFlag:
                start = h
                end = h
            if s == 0:
                end = h
                clearFlag = False
            else:
                if clearFlag:
                    h_count[h][w] = -1
                else:
                    for ih in range(start, end+1):
                        h_count[ih][w] = end - start + 1
                clearFlag = True
        if clearFlag == False:
            for ih in range(start, max(end+1, H)):
                h_count[ih][w] = end - start + 1

    dmatprint(h_count)
    dmatprint(w_count)
    mx_ans = 0
    for h in range(H):
        for w in range(W):
            if s_arr[h][w] == 0:
                ans = h_count[h][w] + w_count[h][w] - 1
                if ans >= mx_ans:
                    mx_ans = ans

    print(mx_ans)
    dmatprint(s_arr)
solve()