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: Accepted

Solution code:
def d_lamp(H, W, Grid):
    field_horizontal = [[0] * W for _ in range(H)]
    field_vertical = [[0] * W for _ in range(H)]
    field = [[0] * W for _ in range(H)]

    for row in range(H):
        tmp = 0
        for col in range(W):
            if Grid[row][col] == '.':
                tmp += 1
                field_horizontal[row][col] = tmp
            else:
                tmp = 0
        max_val = 0
        for col in range(W - 1, -1, -1):
            if Grid[row][col] == '.':
                max_val = max(max_val, field_horizontal[row][col])
                field_horizontal[row][col] = max_val
            else:
                max_val = 0

    for col in range(W):
        tmp = 0
        for row in range(H):
            if Grid[row][col] == '.':
                tmp += 1
                field_vertical[row][col] = tmp
            else:
                tmp = 0
        max_val = 0
        for row in range(H - 1, -1, -1):
            if Grid[row][col] == '.':
                max_val = max(max_val, field_vertical[row][col])
                field_vertical[row][col] = max_val
            else:
                max_val = 0

    for row in range(H):
        for col in range(W):
            field[row][col] = field_horizontal[row][col] + field_vertical[row][col]

    ans = 0
    for row in range(H):
        for col in range(W):
            ans = max(ans, field[row][col])

    return max(ans - 1, 0)

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(d_lamp(H, W, Grid))

Submission status: Accepted

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



H,W = map(int, input().split())
Sn = [[None for _ in range(W)] for _ in range(H)]
for h in range(H):
  s = str(input())
  for w in range(W):
    if s[w] == ".":
      Sn[h][w] = True
    else:
      Sn[h][w] = False

H_cnt = [[1 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(W):
    if Sn[h][w] and w>0:
      H_cnt[h][w] = H_cnt[h][w-1]+1
    elif not Sn[h][w]:
      H_cnt[h][w] = 0
  for w in range(W-2,-1,-1):
    if H_cnt[h][w+1] > 0 and H_cnt[h][w] > 0:
      H_cnt[h][w] = H_cnt[h][w+1]

W_cnt = [[1 for _ in range(W)] for _ in range(H)]
for w in range(W):
  for h in range(H):
    if Sn[h][w] and h>0:
      W_cnt[h][w] = W_cnt[h-1][w]+1
    elif not Sn[h][w]:
      W_cnt[h][w] = 0
  for h in range(H-2,-1,-1):
    if W_cnt[h+1][w] > 0 and W_cnt[h][w] > 0:
      W_cnt[h][w] = W_cnt[h+1][w]


ans = 0
for h in range(H):
  for w in range(W):
    if H_cnt[h][w]*W_cnt[h][w] > 0:
      ans = max(ans, H_cnt[h][w]+W_cnt[h][w]-1)
print(ans)

Submission status: Accepted

Solution code:
def sol(inp=input):
    res=0
    h,w=map(int,inp().split())
    vers=[None for _ in range(w)]
    atlas=[list(inp()+'#') for _ in range(h)]+[['#']*(w+1)]
    for i in range(h):
        hol=None
        for j in range(w):
            if atlas[i][j]=='.':
                if hol is None:
                    for j_ in range(j,w+1):
                        if atlas[i][j_]=='#':
                            hol=j_-j
                            break
                if vers[j] is None:
                    for i_ in range(i,h+1):
                        if atlas[i_][j]=='#':
                            vers[j]=i_-i
                            break
                res=max(res,hol+vers[j]-1)
            else:
                hol=None
                vers[j]=None
    return '{}'.format(res) 
print(sol())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

H,W=LI()
MP=[input() for _ in range(H)]

mp_wid=[[0]*W for _ in range(H)]
mp_hei=[[0]*W for _ in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if MP[i][j] == '.':
            cnt += 1
        else:
            for k in range(cnt):
                mp_wid[i][j-k-1] = cnt
            cnt=0
    for k in range(cnt):
        mp_wid[i][-k-1] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if MP[i][j] == '.':
            cnt+=1
        else:
            for k in range(cnt):
                mp_hei[i-k-1][j] = cnt
            cnt=0
    for k in range(cnt):
        mp_hei[-k-1][j] = cnt

# for li in mp_wid:
#     print(li)
# print('')
# for li in mp_hei:
#     print(li)
res = 0
for i in range(H):
    for j in range(W):
        res = max(res, mp_hei[i][j]+mp_wid[i][j]-1)
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    h, w = get_li()
    S = get_data(h, [str])
    horizontal = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        indices = [j for j, x in enumerate(S[i]) if x == '#'] + [w]
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for j in range(a + 1, b):
                horizontal[i][j] = count
    vertical = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
        indices = [i for i, x in enumerate([S[k][j] for k in range(h)]) if x == '#'] + [h]
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for i in range(a + 1, b):
                vertical[i][j] = count
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, horizontal[i][j] + vertical[i][j] - 1)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    ans = 0
    ph = [[0] * W for _ in range(H)]
    for i in range(H):
        tmp = []
        for j in range(W):
            if S[i][j] == '.':
                tmp.append(j)
            else:
                p = len(tmp)
                for t in tmp:
                    ph[i][t] = p
                tmp = []
        if tmp:
            p = len(tmp)
            for t in tmp:
                ph[i][t] = p
            tmp = []

    pv = [[0] * W for _ in range(H)]
    for i in range(W):
        tmp = []
        for j in range(H):
            if S[j][i] == '.':
                tmp.append(j)
            else:
                p = len(tmp)
                for t in tmp:
                    pv[t][i] = p
                tmp = []
        if tmp:
            p = len(tmp)
            for t in tmp:
                pv[t][i] = p
            tmp = []

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, ph[i][j] + pv[i][j])

    return ans - 1


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))

    # H = 2000
    # W = 2000
    # S = [random.choices('.#', k=W) for _ in range(H)]
    # print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

h,w = m()

k = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
	l = list(input())
	for j in range(w):
		if l[j] != "#":
			k[i][j] = 1

kk = copy.deepcopy(k)
ma = 0
for i in range(h):
	for j in range(1,w):
		if k[i][j] != 0:
			k[i][j] += k[i][j-1]
	for j in range(w-2,-1,-1):
		if k[i][j] != 0 and k[i][j+1]  != 0:
			k[i][j] = k[i][j+1]

for i in range(w):
	for j in range(1,h):
		if kk[j][i] != 0:
			kk[j][i] += kk[j-1][i]
	for j in range(h-2,-1,-1):
		if kk[j][i] != 0 and kk[j+1][i] != 0:
			kk[j][i] = kk[j+1][i]

for i in range(h):
	for j in range(w):
		if ma <= kk[i][j] + k[i][j] - 1:
			ma = kk[i][j] + k[i][j] - 1
print(ma)

Submission status: Accepted

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: Accepted

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

countL2R = [[0 for i in range(w)] for j in range(h)]
countR2L = [[0 for i in range(w)] for j in range(h)]
countU2D = [[0 for i in range(w)] for j in range(h)]
countD2U = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            countL2R[i][j] = -1
            countR2L[i][j] = -1
            countU2D[i][j] = -1
            countD2U[i][j] = -1

for i in range(h):
    for j in range(w):
        if j > 0 and countL2R[i][j] != -1:
                countL2R[i][j] = countL2R[i][j - 1] + 1

        j = w - j - 1
        if j < w - 1 and countR2L[i][j] != -1:
            countR2L[i][j] = countR2L[i][j + 1] + 1

        if i > 0 and countU2D[i][j] != -1:
            countU2D[i][j] = countU2D[i - 1][j] + 1

        I = i
        i = h - i - 1
        if i < h - 1 and countD2U[i][j] != -1:
            countD2U[i][j] = countD2U[i + 1][j] + 1
        i = I

ans = 0
for i in range(h):
    for j in range(w):
        if countD2U[i][j] != -1:
            ans = max(ans, countD2U[i][j] + countU2D[i][j] + countR2L[i][j] + countL2R[i][j])

print(ans + 1)

Submission status: Accepted

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

s1=[[0]*w for i in range(h)]
s2=[[0]*w for i in range(h)]

for i in range(h):
    count=0
    now=set()
    for j in range(w):
        if s[i][j]=='#':
            s1[i][j]==0
            for j in now:
                s1[i][j]=count
            count=0
            now=set()
        else:
            count+=1
            now.add(j)
    for j in now:
        s1[i][j]=count
        
for i in range(w):
    count=0
    now=set()
    for j in range(h):
        if s[j][i]=='#':
            s2[j][i]==0
            for j in now:
                s2[j][i]=count
            count=0
            now=set()
        else:
            count+=1
            now.add(j)
    for j in now:
        s2[j][i]=count
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, s1[i][j]+s2[i][j]-1)
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
H, W = inpl()
S = [[0]*(W+2) for _ in range(H+2)]
for h in range(H):
    s = input()
    for w in range(W):
        S[h+1][w+1] = int(s[w] == ".")

WG1 = [[0]*(W+2) for _ in range(H+2)]
HG1 = [[0]*(W+2) for _ in range(H+2)]
WG2 = [[0]*(W+2) for _ in range(H+2)]
HG2 = [[0]*(W+2) for _ in range(H+2)]


for h in range(1, H+1):
    for w in range(1, W+1):
        WG1[h][w] = (WG1[h][w-1] + 1)*S[h][w]
for w in range(1, W+1):
    for h in range(1, H+1):
        HG1[h][w] = (HG1[h-1][w] + 1)*S[h][w]

for h in range(H, 0, -1):
    for w in range(W, 0, -1):
        WG2[h][w] = max(WG2[h][w+1], WG1[h][w])*S[h][w]

for w in range(W, 0, -1):
    for h in range(H, 0, -1):
        HG2[h][w] = max(HG2[h+1][w], HG1[h][w])*S[h][w]

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        ans = max(ans, WG2[h][w] + HG2[h][w])
print(ans-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
rc = [[0] * W for _ in range(H)]
for i in range(H):
    j = 0
    for k in range(W):
        if S[i][k] == '#':
            j = k + 1
        else:
            rc[i][j] += 1
    j = 0
    while j < W:
        rc0 = rc[i][j]
        if rc0 < 2:
            j += 1
            continue
        for k in range(j, j + rc0):
            rc[i][k] = rc0
        j += rc0
cc = [[0] * W for _ in range(H)]
for j in range(W):
    i = 0
    for k in range(H):
        if S[k][j] == '#':
            i = k + 1
        else:
            cc[i][j] += 1
    i = 0
    while i < H:
        cc0 = cc[i][j]
        if cc0 < 2:
            i += 1
            continue
        for k in range(i, i + cc0):
            cc[k][j] = cc0
        i += cc0
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, rc[i][j] + cc[i][j] - 1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    R, C = read_int_array()
    grid = [read() for _ in range(R)]
    vdp, ldp, ddp, rdp = [[0]*C for _ in range(R)], [[0]*C for _ in range(R)], [[0]*C for _ in range(R)], [[0]*C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if grid[r][c] != b'#'[0]:
                vdp[r][c] = (vdp[r-1][c] if r else 0) + 1
                ldp[r][c] = (ldp[r][c-1] if c else 0) + 1
    for r in range(R-1, -1, -1):
        for c in range(C-1, -1, -1):
            if grid[r][c] != b'#'[0]:
                ddp[r][c] = (ddp[r+1][c] if r + 1 < R else 0) + 1
                rdp[r][c] = (rdp[r][c+1] if c + 1 < C else 0) + 1

    print(max(vdp[r][c] + ldp[r][c] + ddp[r][c] + rdp[r][c] - 3 for r in range(R) for c in range(C) if grid[r][c] != b'#'[0]))



# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Mh = [[-10000000 for _ in range(W)] for _ in range(H)]
Mw = [[-10000000 for _ in range(W)] for _ in range(H)]

for h in range(H):
    w = 0
    while w < W:
        if S[h][w] == "#":
            w += 1
            continue
        start = w
        count = 0
        while w + count < W and S[h][w + count] == ".":
            count += 1
        for x in range(start, w + count):
            Mh[h][x] = count
        w = w + count


for w in range(W):
    h = 0
    while h < H:
        if S[h][w] == "#":
            h += 1
            continue
        start = h
        count = 0
        while h + count < H and S[h+count][w] == ".":
            count += 1
        for x in range(start, h + count):
            Mw[x][w] = count
        h = h + count

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, Mh[h][w]+Mw[h][w] -1)

print(ans)

Submission status: Accepted

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

yoko = [[0] * (w) for i in range(h)]


for i in range(h+1):
    cnt = 0
    start = 0
    for j in range(w+1):
        if s[i][j] == ".":
            cnt += 1
        else:
            for k in range(start, j):
                yoko[i][k] += cnt
            cnt = 0
            start = j + 1
for i in range(w+1):
    cnt = 0
    start = 0
    for j in range(h+1):
        if s[j][i] == ".":
            cnt += 1
        else:
            for k in range(start, j):
                yoko[k][i] += cnt
            cnt = 0
            start = j + 1
ans = 0
for i in range(h):
    ans = max(max(yoko[i]), ans)
print(ans - 1)

Submission status: Accepted

Solution code:
from itertools import chain

H,W = map(int,input().split())
grid = tuple(tuple(map(lambda c: c != '#', input())) for _ in range(H))

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

for i in range(H):
    s = 0
    for j in range(W):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for i in range(H):
    s = 0
    for j in reversed(range(W)):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for j in range(W):
    s = 0
    for i in range(H):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for j in range(W):
    s = 0
    for i in reversed(range(H)):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0


print(1 + max(chain.from_iterable(scores)))

Submission status: Accepted

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

rs = [[0]*W for i in range(H)]
ls = [[0]*W for i in range(H)]
ds = [[0]*W for i in range(H)]
us = [[0]*W for i in range(H)]

for i in range(H):
    tmp = 0
    for j in range(W):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            rs[i][j] = tmp
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            ls[i][j] = tmp

for j in range(W):
    tmp = 0
    for i in range(H):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            ds[i][j] = tmp
    tmp = 0
    for i in reversed(range(H)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            us[i][j] = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        tmp = rs[i][j] + ls[i][j] + ds[i][j] + us[i][j] - 3
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().strip().split())
grid = [[0 for i in xrange(w)] for j in xrange(h)]

for i in xrange(h):
    grid[i] = list(raw_input().strip())

idxl = [[-1 for i in xrange(h * w)] for j in xrange(4)]

# for left
for i in xrange(h):
    left = -1
    for j in xrange(w):
        if grid[i][j] == '#': left = j
        idxl[0][i * w + j] = left

# for right
for i in xrange(h):
    right = w
    for j in xrange(w - 1, -1, -1):
        if grid[i][j] == '#': right = j
        idxl[1][i * w + j] = right

# for up
for j in xrange(w):
    up = -1
    for i in xrange(h):
        if grid[i][j] == '#': up = i
        idxl[2][i * w + j] = up

# for down
for j in xrange(w):
    down = h
    for i in xrange(h - 1, -1, -1):
        if grid[i][j] == '#': down = i
        idxl[3][i * w + j] = down

ans = 0
for i in xrange(h):
    for j in xrange(w):
        if grid[i][j] == '#': continue
        k = i * w + j
        left = j - idxl[0][k]
        right = idxl[1][k] - j
        up = i - idxl[2][k]
        down = idxl[3][k] - i
        cur = left + right + up + down - 3
        ans = max(ans, cur)

print ans

Submission status: Accepted

Solution code:
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

class UnionFind:
    def __init__(self, n):
        self._parents = list(range(n))
        self._ranks = [0] * n
        self._size = [1] * n

    def root(self, x):
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        return self._size[self.root(x)]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self._ranks[rx] < self._ranks[ry]:
            self._parents[rx] = ry
            self._size[ry] += self._size[rx]
        else:
            self._parents[ry] = rx
            self._size[rx] += self._size[ry]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[rx] += 1

    def same(self, x, y):
        return self.root(x) == self.root(y)


def solve(H: int, W: int, S: "List[str]"):
    uf_h = UnionFind(H * W)
    uf_v = UnionFind(H * W)
    for y in range(H):
        for x in range(W):
            i = y * W + x
            phi =  y * W + (x - 1)
            pvi = (y-1) * W + x
            if 0 < x and S[y][x] == '.' and S[y][x-1] == '.':
                uf_h.unite(i, phi)
            if 0 < y and S[y][x] == '.' and S[y-1][x] == '.':
                uf_v.unite(i, pvi)

    ret = 0
    for i in range(H * W):
        ret = max(ret, uf_h.size(i) + uf_v.size(i) - 1)
    return ret


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]"
    result = solve(H, W, S)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

mod = 1000000007

h,w = map(int,input().split())
vals = []
for i in range(h):
	vals.append(input())


v_up_length = [[0 for i in range(w)]for j in range(h)]
v_down_length = [[0 for i in range(w)]for j in range(h)]
h_right_length = [[0 for i in range(w)]for j in range(h)]
h_left_length = [[0 for i in range(w)]for j in range(h)]

for x in range(w):
	for y in range(h):
		if vals[y][x]== "#":
			continue
		if x != 0:
			if vals[y][x-1] == ".":
				h_left_length[y][x] = h_left_length[y][x-1] + 1
		if y != 0:
			if vals[y-1][x] == ".":
				v_up_length[y][x] = v_up_length[y-1][x] + 1



for x in range(w-1,-1,-1):
	for y in range(h-1,-1,-1):
		if vals[y][x]== "#":
			continue
		if x != w-1:
			if vals[y][x+1] == ".":
				h_right_length[y][x] = h_right_length[y][x+1] + 1
		if y != h-1:
			if vals[y+1][x] == ".":
				v_down_length[y][x] = v_down_length[y+1][x] + 1


ans = 0
scores = [[0 for i in range(w)]for j in range(h)]
for x in range(w):
	for y in range(h):
		if vals[y][x]== "#":
			continue
		
		scores[y][x] = 1 + v_up_length[y][x] + v_down_length[y][x] + h_right_length[y][x] + h_left_length[y][x]
		
		ans = max(ans, 1 + v_up_length[y][x] + v_down_length[y][x] + h_right_length[y][x] + h_left_length[y][x])

#for i,vec in enumerate([v_up_length,v_down_length,h_right_length,h_left_length,scores]):
#	print("===============================")
#	print(i)
#	for tmp in vec:
#		print(tmp)


print(ans)

Submission status: Accepted

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

for i in range(H):
    Si = list(input())
    for j in range(W):
        if Si[j] == '#':
            S[i][j] = 1

# row
S_row = [[0]*W for _ in range(H)]
for i in range(H):
    c = 0
    for j in range(W):
        if S[i][j] == 1:
            c = 0
        else:
            c += 1
        S_row[i][j] = c
    # reverse
    for j in range(W-2, -1, -1):
        if S_row[i][j+1] > 0 and S_row[i][j] > 0:
            S_row[i][j] = S_row[i][j+1]

# col
S_col = [[0]*W for _ in range(H)]
for j in range(W):
    c = 0
    for i in range(H):
        if S[i][j] == 1:
            c = 0
        else:
            c += 1
        S_col[i][j] = c
    # reverse
    for i in range(H-2, -1, -1):
        if S_col[i+1][j] > 0 and S_col[i][j] > 0:
            S_col[i][j] = S_col[i+1][j]

# res
res = max([max([S_row[i][j] + S_col[i][j] - 1 for j in range(W)]) for i in range(H)])
print(res)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
board=[list(input())+['#'] for _ in range(h)]
board.append(['#']*(w+1))
hacum=[[0]*(w+1) for _ in range(h+1)]
wacum=[[0]*(w+1) for _ in range(h+1)]
for i in range(h):
  tmp=0
  for j in range(w+1):
    if board[i][j]=='#':
      for k in range(tmp,j):
        wacum[i][k]=j-tmp
      tmp=j+1
for i in range(w):
  tmp=0
  for j in range(h+1):
    if board[j][i]=='#':
      for k in range(tmp,j):
        hacum[k][i]=j-tmp
      tmp=j+1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,wacum[i][j]+hacum[i][j]-1)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [[1 if i == '#' else 0 for i in input()] for _ in range(H)]

Hdp = [[0] * W for _ in range(H)]
Wdp = [[0] * W for _ in range(H)]

for i in range(H) :
    start = 0
    count = 0
    for j in range(W) :
        if S[i][j] == 1 :
            for k in range(start, j) :
                Hdp[i][k] = count
            start = j + 1
            count = 0
        else :
            count += 1
            
    for k in range(start, j + 1) :
        Hdp[i][k] = count
        
for i in range(W) :
    start = 0
    count = 0
    for j in range(H) :
        if S[j][i] == 1 :
            for k in range(start, j) :
                Wdp[k][i] = count
            start = j + 1
            count = 0
        else :
            count += 1
            
    for k in range(start, j + 1) :
        Wdp[k][i] = count

ret = 0  
for i in range(H) :
    for j in range(W) :
        ret = max(ret, Hdp[i][j] + Wdp[i][j])
        
print(ret - 1)