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 numpy as np
import bisect 

h, w = list(map(int, input().split()))
d = {".":0, "#":1}
ss = np.array([list(input()) for _ in range(h)])
ss = np.array([[d[x] for x in s] for s in ss])

ans = 0
ws = np.zeros((h, w))
hs = np.zeros((h, w))

i = 0
while i < h:
	j = 0
	while j < w:
		if ss[i, j] == 0:
			end = w
			for k in range(j + 1, w):
				if ss[i, k] == 1:
					end = k
					break
			ws[i, j:end] = end - j
			j = end + 1
		else:
			j += 1
	i += 1

j = 0
while j < w:
	i = 0
	while i < h:
		if ss[i, j] == 0:
			end = h
			for k in range(i + 1, h):
				if ss[k, j] == 1:
					end = k
					break
			hs[i:end, j] = end - i
			i = end + 1
		else:
			i += 1
	j += 1

# print(ss)
# print(ws)
# print(hs)
print(max(int(np.amax(ws + hs) - 1), 0))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d

"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#' or res_y[y][x] != 0:
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from collections import defaultdict
h, w = map(int, input().split())
c = []
bf, bl = defaultdict(list), defaultdict(list)
ans = 0

for i in range(h):
    s = input()
    c.append(s)
    for j in range(w):
        if s[j] == '#':
            bl[i].append(j)
            bf[j].append(i)

for i in range(h):
    for j in range(w):
        tmp = 0
        if c[i][j] == '.':
            vert = bisect_right(bf[j], i)
            horz = bisect_right(bl[i], j)
            #print(bf[j], bl[i], i, j, vert, horz)
            if bf[j] == []:
                tmp += h-1
            elif i < bf[j][0] or bf[j][-1] < i:
                if i < bf[j][0]:
                    tmp += bf[j][0]-1
                else:
                    tmp += h-bf[j][-1]-2
            else:
                tmp += bf[j][vert]-bf[j][vert-1]-2
            if bl[i] == []:
                tmp += w-1
            elif j < bl[i][0] or bl[i][-1] < j:
                if j < bl[i][0]:
                    tmp += bl[i][0]-1
                else:
                    tmp += w-bl[i][-1]-2
            else:
                tmp += bl[i][horz]-bl[i][horz-1]-2
        ans = max(ans, tmp+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from collections import defaultdict
h, w = map(int, input().split())
c = []
bf, bl = defaultdict(list), defaultdict(list)
ans = 0

for i in range(h):
    s = input()
    c.append(s)
    for j in range(w):
        if s[j] == '#':
            bl[i].append(j)
            bf[j].append(i)

for i in range(h):
    for j in range(w):
        tmp = 0
        if c[i][j] == '.':
            vert = bisect_right(bf[j], i)
            horz = bisect_right(bl[i], j)
            #print(bf[j], bl[i], i, j, vert, horz)
            if bf[j] == []:
                tmp += h-1
            elif i < bf[j][0] or bf[j][-1] < i:
                if i < bf[j][0]:
                    tmp += bf[j][0]-1
                else:
                    tmp += h-bf[j][-1]-2
            else:
                tmp += bf[j][vert]-bf[j][vert-1]-2
            if bl[i] == []:
                tmp += w-1
            elif j < bl[i][0] or bl[i][-1] < j:
                if j < bl[i][0]:
                    tmp += bl[i][0]-1
                else:
                    tmp += w-bl[i][-1]-2
            else:
                tmp += bl[i][horz]-bl[i][horz-1]-2
        ans = max(ans, tmp+1)
print(ans)

Submission status: Time Limit Exceeded

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


def main():
    cnt = [[0] * W for _ in range(H)]
    for h in range(H):
        done = [0] * W
        for w in range(W):
            if S[h][w] == '#' or done[w] == 1:
                continue
            c = 0
            while W > w + c:
                if S[h][w + c] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h][w + k] += c
                done[w + k] = 1
    for w in range(W):
        done = [0] * H
        for h in range(H):
            if S[h][w] == '#' or done[h] == 1:
                continue
            c = 0
            while H > h + c:
                if S[h + c][w] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h + k][w] += c
                done[h + k] = 1
    ans = 0
    for r in cnt:
        for c in r:
            ans = max(ans, c - 1)
    print(ans)


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
m=np.empty((h,w),dtype="bool")
c=np.zeros((h,w),dtype="int16")
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=True
        else:
            m[i][j]=False

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]:
                start=j
                count=1
        else:
            if not m[i][j]:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]:
                start=i
                count=1
        else:
            if not m[i][j]:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = map(int,input().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=object)
grid[1:-1,1:-1] = (np.array([list(input()) for _ in range(H)]) == '.')*1

f = np.frompyfunc(lambda x,y: x+1 if y else 0,2,1)

L = f.accumulate(grid,axis=1)
R = f.accumulate(grid[:,::-1],axis=1)[:,::-1]
U = f.accumulate(grid,axis=0)
D = f.accumulate(grid[::-1,:],axis=0)[::-1,:]

answer = (L+R+U+D).max()-3
print(answer)

Submission status: Time Limit Exceeded

Solution code:
res=0
h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                    res=max(res,c[i][k])
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
            res=max(res,c[i][k])
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                    res=max(res,c[k][j])
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
            res=max(res,c[k][j])
print(res)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
grids = np.zeros((H+2,W+2),dtype=np.int32)
grids[1:-1,1:-1][temp == '.'] = 1

def grids_(matrix):
    for i in range(1, len(matrix)-1):
        a = np.where(matrix[i] == 0)[0]
        for j in range(len(a)-1):
            matrix[i][a[j]+1:a[j+1]] = matrix[i][a[j]+1:a[j+1]].sum()
    return matrix

grids = grids_(grids.copy()) + grids_(grids.copy().T).T - 1
    
print(np.max(grids))

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    n,m = LI()
    a = [[c=='#' for c in S()] for _ in range(n)]
    b = [[0] * m for _ in range(n)]
    c = [[0] * m for _ in range(n)]
    for i in range(n):
        j = 0
        ai = a[i]
        while j < m:
            if ai[j]:
                j += 1
                continue
            k = j+1
            while k < m and not ai[k]:
                k += 1
            s = k - j
            for l in range(j,k):
                b[i][l] = s
            j = k

    for i in range(m):
        j = 0
        while j < n:
            if a[j][i]:
                j += 1
                continue
            k = j+1
            while k < n and not a[k][i]:
                k += 1
            s = k - j
            for l in range(j,k):
                c[l][i] = s
            j = k

    r = 1
    for i in range(n):
        for bb,cc in zip(b[i],c[i]):
            if r < bb + cc:
                r = bb + cc

    return r - 1


print(main())

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    n,m = LI()
    a = [[c=='#' for c in S()] for _ in range(n)]
    b = [[0] * m for _ in range(n)]
    c = [[0] * m for _ in range(n)]
    for i in range(n):
        j = 0
        ai = a[i]
        while j < m:
            if ai[j]:
                j += 1
                continue
            k = j+1
            while k < m and not ai[k]:
                k += 1
            s = k - j
            for l in range(j,k):
                b[i][l] = s
            j = k

    for i in range(m):
        j = 0
        while j < n:
            if a[j][i]:
                j += 1
                continue
            k = j+1
            while k < n and not a[k][i]:
                k += 1
            s = k - j
            for l in range(j,k):
                c[l][i] = s
            j = k

    r = 0
    for i in range(n):
        bi = b[i]
        ci = c[i]
        for j in range(m):
            t = bi[j] + ci[j] - 1
            if r < t:
                r = t

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
grids = np.zeros((H+2,W+2),dtype=np.int32)
grids[1:-1,1:-1][temp == '.'] = 1

grids_x = grids.copy()
for i in range(1, len(grids_x)-1):
    a = np.where(grids_x[i] == 0)[0]
    for j in range(len(a)-1):
        grids_x[i][a[j]+1:a[j+1]] = grids_x[i][a[j]+1:a[j+1]].sum()
        
grids_y = grids.copy().T
for i in range(1, len(grids_y)-1):
    a = np.where(grids_y[i] == 0)[0]
    for j in range(len(a)-1):
        grids_y[i][a[j]+1:a[j+1]] = grids_y[i][a[j]+1:a[j+1]].sum()
grids_y = grids_y.T

grids = grids_x + grids_y
    
print(np.max(grids) - 1)

Submission status: Time Limit Exceeded

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

sum_s = [[], []]

for y in range(H):
	count, line = 0, []
	for x in range(W):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[0] += [line]

for x in range(W):
	count, line = 0, []
	for y in range(H):
		if STAGE[y][x] == ".":
			count += 1
		else:
			if 0 < count:
				line += [count] * count
			line += [0]
			count = 0
	else:
		if 0 < count:
			line += [count] * count
	sum_s[1] += [line]
"""
for line in sum_s[0]:
	print(*line)
print()
for line in sum_s[1]:
	print(*line)
"""
max_score = 0
for y in range(H):
	for x in range(W):
		max_score = max(max_score, sum_s[0][y][x] + sum_s[1][x][y] - 1)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1
        else:
            grid[i][j] = 0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]


nums = []
for i in range(h):
    for j in range(w):
        nums.append(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(np.max(L + R + U + D - 3))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1
        else:
            grid[i][j] = 0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]


nums = []
for i in range(h):
    for j in range(w):
        nums.append(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(max(nums))

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
Grid=[]
for _ in range(H):
  Grid.append(list(input()))
tmp=0
ans=0
up=[[0 for _ in range(W)] for _ in range(H)]
down=[[0 for _ in range(W)] for _ in range(H)]
left=[[0 for _ in range(W)] for _ in range(H)]
right=[[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if Grid[i][j]=='.':
      left[i][j]=left[i][j-1]+1
      up[i][j]=up[i-1][j]+1
    if Grid[H-i-1][j]=='.':
      down[H-i-1][j]=down[-i][j]+1
    if Grid[i][W-j-1]=='.':
      right[i][W-j-1]=right[i][-j]+1
      
for i in range(H):
  for j in range(W):
    ans=max(ans,left[i][j]+up[i][j]+down[i][j]+right[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

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

P = [[0 if x == "#" else 1 for x in input()] for _ in range(H)]
C = [[-3*P[x][y] for y in range(W)] for x in range(H)]

import numpy as np
P = np.array(P, dtype=np.int32)
C = np.array(C, dtype=np.int32)

cur = np.ones(P[0].shape, dtype=np.int32)
for i in range(0, H):
    cur *= P[i]
    C[i] += cur
    cur += 1

cur = 1
for i in range(H-1, -1, -1):
    cur *= P[i]
    C[i] += cur
    cur += 1

cur = np.ones(P[:,0].shape, dtype=np.int32)
for i in range(0, W):
    cur *= P[:,i]
    C[:,i] += cur
    cur += 1

cur = 1
for i in range(W-1, -1, -1):
    cur *= P[:,i]
    C[:,i] += cur
    cur += 1

print(max((x for ci in C for x in ci)))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = True
        else:
            grid[i][j] = False

left = [[0 for j in range(w)] for i in range(h)]
right = [[0 for j in range(w)] for i in range(h)]
top = [[0 for j in range(w)] for i in range(h)]
bottom = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        if grid[i][j]:
            if j >= 1:
                left[i][j] = left[i][j - 1] + 1
            else:
                left[i][j] = 1
        else:
            left[i][j] = 0

for i in range(h):
    for j in range(w - 1, -1, -1):
        if grid[i][j]:
            if j < w - 1:
                right[i][j] = right[i][j + 1] + 1
            else:
                right[i][j] = 1
        else:
            right[i][j] = 0


for j in range(w):
    for i in range(h):
        if grid[i][j]:
            if i >= 1:
                top[i][j] = top[i - 1][j] + 1
            else:
                top[i][j] = 1


for j in range(w):
    for i in range(h - 1, -1, -1):
        if grid[i][j]:
            if i < h - 1:
                bottom[i][j] = bottom[i + 1][j] + 1
            else:
                bottom[i][j] = 1


nums = []
for i in range(h):
    for j in range(w):
        nums.append(left[i][j] + right[i][j] + top[i][j] + bottom[i][j] - 3)

print(max(nums))

Submission status: Time Limit Exceeded

Solution code:
def f(h, w):
    t = [input() for _ in range(h)]
    U = [[0] * (w + 2) for _ in range(h + 2)]
    D = [[0] * (w + 2) for _ in range(h + 2)]
    L = [[0] * (w + 2) for _ in range(h + 2)]
    R = [[0] * (w + 2) for _ in range(h + 2)]
    ans = 0
    Ui1 = U[0]
    for i in range(1, 1 + h):
        Ui = U[i]
        Li = L[i]
        ti1 = t[i - 1]
        for j, tk in enumerate(ti1):
            j += 1
            if tk == "#":
                Ui[j] = 0
                Li[j] = 0
            else:
                Ui[j] = Ui1[j] + 1
                Li[j] = Li[j - 1] + 1
        Ui1 = Ui
        Di1 = D[-1]
    for i in range(h, 0, -1):
        Ui = U[i]
        Li = L[i]
        Di = D[i]
        Ri = R[i]
        ti1 = t[i - 1]
        for j in range(w, 0, -1):
            if ti1[j - 1] == "#":
                Di[j] = 0
                Ri[j] = 0
            else:
                Di[j] = Di1[j] + 1
                Ri[j] = Ri[j + 1] + 1
                tmp = Ui[j] + Di[j] + Li[j] + Ri[j]
                if tmp > ans:
                    ans = tmp
        Di1 = Di
    print(ans - 3)

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

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
t = [input() for _ in range(h)]
U = [[0] * (w + 2) for _ in range(h + 2)]
D = [[0] * (w + 2) for _ in range(h + 2)]
L = [[0] * (w + 2) for _ in range(h + 2)]
R = [[0] * (w + 2) for _ in range(h + 2)]
ans = 0
Ui1=U[0]
for i in range(1, 1 + h):
    Ui=U[i]
    Li=L[i]
    ti1=t[i-1]
    for j in range(1, 1 + w):
        if ti1[j - 1] == "#":
            Ui[j] = 0
            Li[j] = 0
        else:
            Ui[j] = Ui1[j] + 1
            Li[j] = Li[j - 1] + 1
    Ui1=Ui
    Di1=D[-1]
for i in range(h, 0, -1):
    Ui=U[i]
    Li=L[i]
    Di=D[i]
    Ri=R[i]
    ti1=t[i-1]
    for j in range(w, 0, -1):
        if ti1[j - 1] == "#":
            Di[j] = 0
            Ri[j] = 0
        else:
            Di[j] = Di1[j] + 1
            Ri[j] = Ri[j + 1] + 1
            tmp = Ui[j] + Di[j] + Li[j] + Ri[j]
            if tmp > ans:
                ans = tmp
    Di1=Di
print(ans - 3)

Submission status: Time Limit Exceeded

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

P = [[0 if x == "#" else 1 for x in input()]+[0] for _ in range(H)]
C = [[-1*P[x][y] for y in range(W)] + [0] for x in range(H)]
W += 1
H += 1
P.append([0] * W)
C.append([0] * W)


for i in range(H):
    cnt = 0
    for j in range(W):
        if P[i][j] == 0:
            for k in range(cnt):
                C[i][j-1-k] += k
            cnt = 0
        else:
            cnt += 1
        C[i][j] += cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if P[i][j] == 0:
            for k in range(cnt):
                C[i-1-k][j] += k
            cnt = 0
        else:
            cnt += 1
        C[i][j] += cnt


print(max((x for ci in C for x in ci)))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
t = [input() for _ in range(h)]
U = [[0] * (w + 2) for _ in range(h + 2)]
D = [[0] * (w + 2) for _ in range(h + 2)]
L = [[0] * (w + 2) for _ in range(h + 2)]
R = [[0] * (w + 2) for _ in range(h + 2)]
ans = 0
for i in range(1, 1 + h):
    for j in range(1, 1 + w):
        if t[i - 1][j - 1] == "#":
            U[i][j] = 0
            L[i][j] = 0
        else:
            U[i][j] = U[i - 1][j] + 1
            L[i][j] = L[i][j - 1] + 1
for i in range(h, 0, -1):
    for j in range(w, 0, -1):
        if t[i - 1][j - 1] == "#":
            D[i][j] = 0
            R[i][j] = 0
        else:
            D[i][j] = D[i + 1][j] + 1
            R[i][j] = R[i][j + 1] + 1
        tmp = U[i][j] + D[i][j] + L[i][j] + R[i][j]
        if tmp > ans:
            ans = tmp
print(ans - 3)

Submission status: Time Limit Exceeded

Solution code:
import fractions #最小公倍数などはこっち
import math
import sys
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
H,W = map(int,input().split())
S = [[] for i in range(H)]
for i in range(H):
    S[i] = list(str(input()))
 
lights = [[(0,0) for j in range(W)] for i in range(H)]
 
 
def count_ver(i,j):
    cnt = 0
    for x in range(i,W):
        if S[j][x] == ".":
            cnt += 1
        else:
            break
    for x in range(i,W):
        if S[j][x] == ".":
            ver,hor = lights[j][x]
            lights[j][x] = (cnt,hor)
        else:
            break
    return cnt
 
 
def count_hor(i,j):
    cnt = 0
    for y in range(j,H):
        if S[y][i] == ".":
            cnt += 1
        else:
            break
    for y in range(j,H):
        if S[y][i] == ".":
            ver,hor = lights[y][i]
            lights[y][i] = (ver,cnt)
        else:
            break
    return cnt
 
ans = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ver,hor = lights[i][j]
            if ver == 0:
                ver = count_ver(j,i)
                # print("ver",ver)
            if hor == 0:
                hor = count_hor(j,i)
                # print("hor",hor)
            ans = max(ans,hor+ver-1)
        # print("y,x:",i,j)
        # print("ver,hor",ver,hor)
 
# print(lights)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

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

def count_ver(i,j):
    cnt = 0
    for x in range(i,W):
        if S[j][x] == ".":
            cnt += 1
        else:
            break
    for x in range(i,W):
        if S[j][x] == ".":
            lights[j][x][0] = cnt
        else:
            break
    return cnt


def count_hor(i,j):
    cnt = 0
    for y in range(j,H):
        if S[y][i] == ".":
            cnt += 1
        else:
            break
    for y in range(j,H):
        if S[y][i] == ".":
            lights[y][i][1] = cnt
        else:
            break
    return cnt

ans = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ver,hor = lights[i][j]
            if ver == 0:
                ver = count_ver(j,i)
            if hor == 0:
                hor = count_hor(j,i)
            ans = max(ans,hor+ver-1)
        # print("y,x:",i,j)
        # print("ver,hor",ver,hor)

# print(lights)
print(ans)