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 = [input() for _ in range(H)]


def f(h, w):
    c = 0
    for hh in range(h, -1, -1):
        if S[hh][w] == '#':
            break
        c += 1
    for hh in range(h, H):
        if S[hh][w] == '#':
            break
        c += 1
    for ww in range(w, -1, -1):
        if S[h][ww] == '#':
            break
        c += 1
    for ww in range(w, W):
        if S[h][ww] == '#':
            break
        c += 1
    return c - 3


def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            ans = max(ans, f(h, w))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
nl = lambda: list(map(int, input().split()))
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())


yoko = np.zeros((H, W), dtype=np.uint64)
for row in range(H):
    count = 0
    for col in range(W):
        if grid[row][col] == '.':
            count += 1
            yoko[row][col] = count
        else:
            count = 0

    count = 0
    for col in range(W-1, -1, -1):
        if yoko[row][col] > 0:
            count = max(count, yoko[row][col])
            yoko[row][col] = count
        else:
            count = 0

tate = np.zeros((H, W), dtype=np.uint64)
for col in range(W):
    count = 0
    for row in range(H):
        if grid[row][col] == '.':
            count += 1
            tate[row][col] = count
        else:
            count = 0

    count = 0
    for row in range(H-1, -1, -1):
        if tate[row][col] > 0:
            count = max(count, tate[row][col])
            tate[row][col] = count
        else:
            count = 0

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, yoko[row][col] + tate[row][col] - 1)

print(int(res))

Submission status: Time Limit Exceeded

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

# def print_map(mp):
#     for r in mp:
#         print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]

# True = なし、 False = 障害物
for h in range(H):
    mp[h] = [True if c == "." else False for c in input()]

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。
# このプログラムはO(HW)だがTLE

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] is False:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] is False:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        # 重なっている中央を引くのを忘れずに
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
rows,cols = list(map(int,input().split()))
grid=[]
up=[]
# down=[]
# left=[]
# right=[]
for i in range(rows):
	grid.append(input())
	up.append([0 for j in range(cols)])
	# down.append([-1 for j in range(cols)])
	# left.append([-1 for j in range(cols)])
	# right.append([-1 for j in range(cols)])
#up
for c in range(cols):
	count = 1
	for r in range(rows-1,-1,-1):
		if(grid[r][c]=='#'):
			count=1
		else:
			up[r][c]+=count
			count+=1

#down

for c in range(cols):
	count = 1
	for r in range(rows):
		if(grid[r][c]=='#'):
			count=1
		else:
			up[r][c]+=count
			count+=1

#left

for c in range(rows):
	count = 1
	for r in range(cols-1,-1,-1):
		if(grid[c][r]=='#'):
			count=1
		else:
			up[c][r]+=count
			count+=1

#right

for c in range(rows):
	count = 1
	for r in range(cols):
		if(grid[c][r]=='#'):
			count=1
		else:
			up[c][r]+=count
			count+=1
ans = 1
for x in range(rows):
	for y in range(cols):
		if(grid[x][y]=='.'):
			ans=max(ans,(up[x][y]-3))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
S = []
for i in range(h):
    S.append(input())

sw = []

for i in range(h):
    c = []
    for j in range(w):
        if S[i][j] == '#':
            c.append(j)
    c.append(w)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sw.append(k[0:-1])

sh =[]

for i in range(w):
    c = []
    for j in range(h):
        if S[j][i] == '#':
            c.append(j)
    c.append(h)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sh.append(k[0:-1])

sw = np.array(sw)
sh = np.array(sh)
sh = sh.T

x = sw + sh

print(np.amax(x) - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())  # 複数数値入力

li = list()
for i in range(H):
    li.append(list(input()))  # 1文字区切りでリスト格納

ans = 0
for h in range(H):
    for w in range(W):
        akarukunarutoko = 1
        # print("------")
        if li[h][w] == "#":
            continue

        n = 1
        while True:
            if h + n >= H:
                break
            if li[h + n][w] == "#":
                break
            n += 1
        akarukunarutoko += n-1

        n = 1
        while True:
            if h - n < 0:
                break
            if li[h - n][w] == "#":
                break
            n += 1
        akarukunarutoko += n-1
        # print(akarukunarutoko)

        n = 1
        while True:
            if w + n >= W:
                break
            if li[h][w+n] == "#":
                break
            n += 1
        akarukunarutoko += n-1
        # print(akarukunarutoko)

        n = 1
        while True:
            if w - n < 0:
                break
            if li[h][w-n] == "#":
                break
            n += 1
        akarukunarutoko += n-1
        # print(akarukunarutoko)
        if ans < akarukunarutoko:
            ans = akarukunarutoko

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


class UnionFind:

    # n is element num
    def __init__(self, n):
        self.n = n
        self.parent = [-1] * (n + 1)
        self.rnk = [0]*(n+1)

    # find root of x node
    def find_root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]

    # union disjoint sets of x and y
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)

        if x == y:
            return

        elif self.rnk[x] > self.rnk[y]:
            self.parent[x] += self.parent[y]  # update num of nodes in united tree
            self.parent[y] = x

        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y

            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # check x and y are in same tree
    def is_same_tree(self, x, y):
        return self.find_root(x) == self.find_root(y)

    # count nodes in tree what x belong to
    def count_nodes(self, x):
        return -self.parent[self.find_root(x)]


def read_input():
    h, w = map(int, input().split())

    board = []
    for i in range(h):
        board.append(np.array([0 if c == '.' else 1 for c in input()]))

    return h, w, np.array(board)


def union(vec):
    u = UnionFind(len(vec))

    for i, (v1, v2) in enumerate(zip(vec, vec[1:])):
        if v1 == v2 == 0:
            u.unite(i, i+1)

    return u

def submit():
    h, w, board = read_input()

    hunions = []
    for i in range(h):
        hunions.append(union(board[i]))

    wunions = []
    for j in range(w):
        wunions.append(union(board[:, j]))

    max_lit = 0
    for i in range(h):
        for j in range(w):
            if board[i, j] == 0:
                hv = hunions[i].count_nodes(j)
                wv = wunions[j].count_nodes(i)

                if max_lit < hv + wv - 1:
                    max_lit = hv + wv - 1


    print(max_lit)



if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

H,W = map(int, sys.stdin.readline().rstrip().split(" "))
maze = []
for i in range(H):
    S = sys.stdin.readline().rstrip()
    maze.append(S)


results = [[0 for _x in range(W)] for _y in range(H)]
# print(maze)
# right
for y in range(H):
    voids = 0
    for x in range(W):
        # print(y, x)
        if maze[y][x] == "#":
            voids = 0
        else:
            results[y][x] += voids
            voids += 1

# left
for y in range(H):
    voids = 0
    for x in range(W-1, -1, -1):
        if maze[y][x] == "#":
            voids = 0
        else:
            results[y][x] += voids
            voids += 1

# down
for x in range(W):
    voids = 0
    for y in range(H):
        if maze[y][x] == "#":
            voids = 0
        else:
            results[y][x] += voids
            voids += 1

# up
for x in range(W):
    voids = 0
    for y in range(H-1, -1, -1):
        if maze[y][x] == "#":
            voids = 0
        else:
            results[y][x] += voids
            voids += 1

print(max(max(results[y]) for y in range(H)) + 1)



exit(0)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
H, W = map(int, input().split())
s = [input() for i in range(H)]

def length(index, block_idx, full_length):
    if len(block_idx) == 0:
        return full_length
    idx = bisect_left(block_idx, index)
    if idx == len(block_idx):
        return full_length - index
    return block_idx[idx] - index

rows = []

for i in range(H):
    row = []
    block_idx = []
    for k in range(len(s[i])):
        if s[i][k] == "#":
            block_idx.append(k)

    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                l = length(0, block_idx, W)
                row.append(l)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    l = length(j, block_idx, W)
                    row.append(l)
    rows.append(row)

columns = []

for i in range(W):
    column = []

    _s = ""
    block_idx = []
    for k in range(H):
        _s += s[k][i]
        if s[k][i] == "#":
            block_idx.append(k)

    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                l = length(0, block_idx, H)
                column.append(l)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    l = length(j, block_idx, H)
                    column.append(l)
    columns.append(column)

res = []
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        res.append(r+c-1)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
h, w = (int(i) for i in input().split())
s = [str(input()) for i in range(h)]
t_s = [x for x in zip(*s)]
torch = 0
for r,row in enumerate(s):
    for c, center in enumerate(row):
        if center == "#":
            light = 0
        else:
            vertical = list(t_s[c][:])
            vertical[r] = "C"
            horizontal = list(s[r][:])
            horizontal[c] = "C"

            v_list = ''.join(vertical).split("#")
            for v in v_list:
                if "C" in v:
                    v_length = len(v)
            h_list = ''.join(horizontal).split("#")
            for h in h_list:
                if "C" in h:
                    h_length = len(h)
            light = v_length + h_length - 1
        if torch < light:
            torch = light
print(torch)

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

H,W=map(int,input().split())
S=list()
for h in range(H):
	S.append(input())

# print(S)
WWork = np.zeros((H,W),dtype='int32')
HWork = np.zeros((W,H),dtype='int32')

for h in range(H):
	wRangeStart = 0
	for w in range(W):
		# print(h,w)
		if S[h][w] == "#":
			WWork[h][wRangeStart:w] = w - wRangeStart
			wRangeStart = w+1

	if wRangeStart != W:
		WWork[h][wRangeStart:W] = W - wRangeStart


for w in range(W):
	hRangeStart = 0
	for h in range(H):
		if S[h][w] == "#":
			HWork[w][hRangeStart:h] = h - hRangeStart
			hRangeStart = h+1

	if hRangeStart != H:
		HWork[w][hRangeStart:H] = H - hRangeStart


# print(WWork)
# print(HWork)

ans = 0

for h in range(H):
	for w in range(W):
		# 必ずクロスするとみなして良い。。。？
		tmp = HWork[w][h] + WWork[h][w] - 1
		# if HWork[w][h] != 0 and WWork[h][w] != 0:
		# 	tmp -= 1


		ans = max( ans, tmp )

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(h):
    f = 0
    j = 0
    m = 0
    while j < w:
        if s[i][j] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    yoko[i][p] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            yoko[i][p] = j - f

for i in range(w):
    f = 0
    j = 0
    m = 0
    while j < h:
        if s[j][i] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    tate[p][i] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            tate[p][i] = j - f
ans = 0
for i in range(h):
    for j in range(w):
        q = yoko[i][j] + tate[i][j] - 1
        if q > ans:
            ans = q
print(ans)

Submission status: Time Limit Exceeded

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


def right(y, x):
    ret = 0
    xx = x
    while xx + 1 <= W - 1 and S[y][xx + 1] == '.':
        ret += 1
        xx += 1
    return ret


def left(y, x):
    ret = 0
    xx = x
    while 0 <= xx - 1 and S[y][xx - 1] == '.':
        ret += 1
        xx -= 1
    return ret


def up(y, x):
    ret = 0
    yy = y
    while 0 <= yy - 1 and S[yy - 1][x] == '.':
        ret += 1
        yy -= 1
    return ret


def down(y, x):
    ret = 0
    yy = y
    while yy + 1 <= H - 1 and S[yy + 1][x] == '.':
        ret += 1
        yy += 1
    return ret


ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        ans = max(ans, (right(y, x) + left(y, x) + up(y, x) + down(y, x)))
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy


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


H, W = inpl()
S = [input() + '#' for i in range(H)]
S.append("#" * (W + 1))

vertical = [0 for i in range(W + 1)]
side = [0 for i in range(W + 1)]
past_side = [0 for i in range(W + 1)]
ans = 0

for h in range(H + 1):
    start = 0
    keep = 0
    for w in range(W + 1):
        if S[h][w] == '#':
            for i in range(start, w):
                side[i] = max(side[i], keep)
            ans = max(ans, past_side[w] + vertical[w] - 1)

            keep = 0
            start = w + 1
            vertical[w] = 0
            side[w] = 0
        else:
            keep += 1
            vertical[w] += 1
    past_side = copy(side)
    # print(h, ans)
    # print(side)
    # print(vertical)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(v) for v in input().split()]
s_s = [input() for _ in range(h)]

field = []
for s in s_s:
  line = []  
  for i in range(w):
    if s[i: i+1] == '.':
      cell = 0
    else:
      cell = 1
    line.append(cell)
  field.append(line)
  
hori_score = [[0 for _ in range(w)] for _ in range(h)]
vert_score = [[0 for _ in range(w)] for _ in range(h)]
all_score = [[0 for _ in range(w)] for _ in range(h)]

#横方向
for i in range(h):
  #連続領域のスコアリング
  #まずカウントアップ
  score = 0
  for j in range(w):
    if field[i][j] == 0:
      score += 1
    else:
      score = 0
    hori_score[i][j] = score

  #当該マスと右マスが空きなら右マスのスコアをコピー
  for j in range(w - 2, -1, -1):
    if field[i][j] == 0 and field[i][j + 1] == 0:
      hori_score[i][j] = hori_score[i][j+1]
    
#縦方向
for j in range(w):
  score = 0
  #連続領域のスコアリング
  #まずカウントアップ
  for i in range(h):
    if field[i][j] == 0:
      score += 1
    else:
      score = 0
    vert_score[i][j] = score

  #当該マスと下マスが空きなら右マスのスコアをコピー
  for i in range(h - 2, -1, -1):
    if field[i][j] == 0 and field[i + 1][j] == 0:
      vert_score[i][j] = vert_score[i + 1][j]
    

max_score = 0
for i in range(h):
  for j in range(w):
    if field[i][j] == 0:
      all_score[i][j] = hori_score[i][j] + vert_score[i][j]
      max_score = max(max_score, all_score[i][j])

#print(hori_score)
#print(vert_score)
print(max_score-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
class Data:
    def __init__(self):
        self.n = 0
    def __repr__(self):
        return str(self.n)
X = [[0] * W for _ in range(H)]
for h in range(H):
    start = 0
    data = Data()
    for w in range(W):
        if S[h][w] == ".":
            X[h][w] = data
            continue
        data.n = w - start
        start = w + 1
        data = Data()
    else:
        if start < W:
            data.n = W - start
Y = [[0] * H for _ in range(W)]
for w in range(W):
    start = 0
    data = Data()
    for h in range(H):
        if S[h][w] == ".":
            Y[w][h] = data
            continue
        data.n = h - start
        start = h + 1
        data = Data()
    else:
        if start < H:
            data.n = H - start
num = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        n = X[h][w].n + Y[w][h].n - 1
        num = max(n, num)
print(num)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
grid = [list(input()) for h in range(H)]


def light_up(line):
    """リストを受け取ってライトで照らせる数を返す"""
    light_up_count = 0
    for current_spot in line:
        if current_spot == "#":
            break
        light_up_count += 1
    return light_up_count


def search_grid(h, w):
    """指定されたマスに明かりを設置したときの照らされるマスを返す

    Arguments:
        h {[type]} -- 高さ
        w {[type]} -- 幅
    """

    # 障害物に置いたら0マス
    if grid[h][w] == "#":
        return 0
    # それ以外なら上下左右に照らしていく
    # 自分のマスを含むので1から開始
    light_up_count = 1
    # 上
    if h != 0:
        # 指定マスから上方向へのリストを得る
        up_line = reversed([grid[n][w] for n in range(h)])
        light_up_count += light_up(up_line)

    # 下
    if h != H:
        # 指定マスから下方向へのリストを得る
        down_line = [grid[n][w] for n in range(h + 1, H)]
        light_up_count += light_up(down_line)

    # 左
    if w != 0:
        # 指定マスから左方向へのリストを得る
        left_line = reversed([grid[h][n] for n in range(w)])
        light_up_count += light_up(left_line)

    # 右
    if w != W:
        # 指定マスから左方向へのリストを得る
        right_line = [grid[h][n] for n in range(w + 1, W)]
        light_up_count += light_up(right_line)

    return light_up_count


def check_light_up():
    # 全てのマスを走査する
    max_count = 0
    for h in range(H):
        for w in range(W):
            light_up_count = search_grid(h, w)
            if max_count < light_up_count:
                max_count = light_up_count
            # 最大値が来たらそこで終了
            if max_count == H + W - 1:
                yield max_count
    yield max_count


# 最初に得た答えを表示する
for m in check_light_up():
    print(m)
    break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w = map(int,input().split())
S=np.zeros((h+2,w+2),dtype=np.int)
for i in range(h):
    for j,s in enumerate(input()):
        if s =='.':
            S[i+1][j+1]=1
wtable=np.zeros((h+2,w+2),dtype=np.int)
htable=np.zeros((w+2,h+2),dtype=np.int)
cur=0
for i in range(1,h+1):
    for j in range(1,w+1):
        for k in np.where(S[i]<1)[0]:
            wtable[i][cur+1:k]=k-cur-1
            cur=k
S=S.T
cur=0
for i in range(1,w+1):
    for j in range(1,h+1):
        rec=0
        for k in np.where(S[i]<1)[0]:
            htable[i][cur+1:k]=k-cur-1
            cur=k
anstable=wtable+htable.T
print(np.max(anstable)-1)

Submission status: Time Limit Exceeded

Solution code:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)

a = np.zeros((h,w), dtype=np.int)
#print(yoko)

for i in range(h):
    temp = 0
    for j in range(w):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for i in range(h):
    temp = 0
    for j in range(w-1,-1,-1):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp
#print(a)
for j in range(w):
    temp = 0
    for i in range(h):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h-1,-1,-1):
        if grid[i][j]=='#':
            temp=0
        else:
            temp += 1
            a[i][j] += temp
answer=3
for i in range(h):
    for j in range(w):
        answer=max(a[i][j],answer)
#print(a)
print(answer-3)

Submission status: Time Limit Exceeded

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

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  H, W = readInts()
  S = [input() for _ in range(H)]

  pointerW = [[w for w in range(W)] for _ in range(H)]
  pointerH = [[h for _ in range(W)] for h in range(H)]
  countW = [[1 for _ in range(W)] for _ in range(H)]
  countH = [[1 for _ in range(W)] for _ in range(H)]

  for h in range(H):
    for w in range(W-1):
      if S[h][w] != '#' and S[h][w+1] != '#':
        pointerW[h][w+1] = pointerW[h][w]
        countW[h][pointerW[h][w]] += 1

  for w in range(W):
    for h in range(H-1):
      if S[h][w] != '#' and S[h+1][w] != '#':
        pointerH[h+1][w] = pointerH[h][w]
        countH[pointerH[h][w]][w] += 1

  ans = 0
  for h in range(H):
    for w in range(W):
      if S[h][w] != '#':
        c1 = countW[h][pointerW[h][w]]
        c2 = countH[pointerH[h][w]][w]
        ans = max(ans, c1 + c2 - 1)

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

h_cnt = [[0]*W for i in range(H)]
w_cnt = [[0]*W for i in range(H)]

cnt = 0
z = []

for h in range(H):
    for w in range(W):
        if S[h][w] == ".":
            cnt += 1
            z.append(w)
        else:
            for i in range(len(z)):
                w_cnt[h][z.pop()] = cnt
            cnt = 0

    if cnt > 0:
        for i in range(len(z)):
            w_cnt[h][z.pop()] = cnt
        cnt = 0


for w in range(W):
    for h in range(H):
        if S[h][w] == ".":
            cnt += 1
            z.append(h)
        else:
            for i in range(len(z)):
                h_cnt[z.pop()][w] = cnt
            cnt = 0

    if cnt > 0:
        for i in range(len(z)):
            h_cnt[z.pop()][w] = cnt
        cnt = 0

ans = 0

for h in range(H):
    for w in range(W):
        ans = max(ans,h_cnt[h][w]+w_cnt[h][w])

print(ans-1)

Submission status: Time Limit Exceeded

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

light = [[-1, -1] for _ in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        
        if light[W*i+j][0] == -1:
            tmp = 0
            tate = i
            while tate < H and S[tate][j] == '.':
                tmp += 1
                tate += 1
            for k in range(tmp):
                light[W*(i+k)+j][0] = tmp
        
        if light[W*i+j][1] == -1:
            tmp = 0
            yoko = j
            while yoko < W and S[i][yoko] == '.':
                tmp += 1
                yoko += 1
            for k in range(tmp):
                light[W*i+j+k][1] = tmp

ans = 0
for i in light:
    tmp = i[0]+i[1]-1
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split(' ')]
S = []
for i in range(H):
    S.append(input())
max_count = 0
for ix in range(W):
    for iy in range(H):
        if S[iy][ix] == '#':
            continue
        vlist = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        sum = 1 # self
        for v in vlist:
            x, y = ix, iy
            while True:
                x += v[0]
                y += v[1]
                if not ((0 <= x <= W - 1) and (0 <= y <= H - 1)):
                    break
                if S[y][x] == "#":
                    break
                sum += 1
        if max_count < sum:
            max_count = sum
print(max_count)

Submission status: Time Limit Exceeded

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

maxcount = 1
for i in range(H):
    for j in range(W):
        #print("start", i, j)
        count = 1
        if e[i][j] == "#":
            continue
        for k in range(i+1, H):
            #print(e[k][j], k, j)
            if e[k][j] == "#":
                #print(k, j)
                break
            else:
                count +=1
        #print("1 ", count)
        for l in range(1, i+1):
            #print(e[i-l][j], i-l, j)
            if e[i-l][j] == "#":
                break
            else:
                count += 1
        #print("2 ", count)
        if count + W -1 < maxcount:
            continue
        for m in range(j+1, W):
            if e[i][m] == "#":
                break
            else:
                count +=1
        #print("3 ",count)
        for n in range(1, j+1):
            if e[i][j-n] == "#":
                break
            else:
                count +=1
        if maxcount < count:
            maxcount = count
        if maxcount == W+H:
            break
    else:
        continue
    break
print(maxcount)

Submission status: Time Limit Exceeded

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

# def print_map(mp):
#     for r in mp:
#         print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]

# True = なし、 False = 障害物
for h in range(H):
    s = input()
    for w in range(W):
        mp[h] = [True if c == "." else False for c in s]

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。
# このプログラムはO(HW)だがTLE

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] is False:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] is False:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        # 重なっている中央を引くのを忘れずに
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)